One and one are eleven

Oh C++, why art thou so hard? Thou giveth us nought but grievance and pain. Often I've cried out because C++ just wouldn't play nice. The language is too hard to learn, and it couldn't do anything you could do in plain C. But I've actually started to like C++. I have come to appreciate it a lot. I suppose it ages like fine wine. C++11 brings a lot of good to the table, well, as long as your compiler is up to par.

Rather than go over all the features of C++11 (there's enough of that on the web to go 'round), I want to show you a neat trick. Lo and behold.

template <typename... Tpack>
void go(Tpack&&... args) {
    std::function<void()> func = std::bind(std::forward<Tpack>(args)...);
    std::thread(trampoline, func);
}

This defines a go() function that allows you to fire up any function (with arguments!) as a thread. The thing with Tpack is a variadic template, which is a type-safe kind of varargs. The call to std::bind turns it into a std::function object, which is a kind of functor. std::thread creates a new thread and launches a trampoline function that will invoke the function functor for us. Okay, the actual implementation is a little different, I have simplified it here for the sake of example. For one thing, you should catch the std::system_error exception that is thrown in case the operating system fails to launch the thread.

So now we can easily run any function as a thread. Next, I wanted go() to accept my custom Functor class as well. Normally you would go about that doing that like so:

void go(const Functor&);
void go(Functor&);

Guess what, it didn't work! The result was a (not so) glorious Segmentation fault. Tracing it revealed that the compiler was favoring the go(Tpack&&...) variant over the specific Functor functions. But no worries, template specialization to the rescue:

// specialized templates for passing in a Functor
// const Functor& is only used for const functions or
// explicitly const Functors
// in most cases go(Functor&) is used
template <>
inline void go<const Functor&>(const Functor& f) {
    do_something_with(f);
}

template <>
inline void go<Functor&>(Functor& f) {
    do_something_with(f);
}

This weird looking stuff is C++ dark magick, written in the black of night by the light of a candle. If you look past all the confusing glyphs, it's simply telling the compiler to call the right function for what kind of argument we have.

All of this wasn't quite possible to this extent before C++11. Other than impressing your girlfriend with this trickery (not!), C++11 comes with a most important change: the move constructor. This is something you MUST learn. It's hard to believe, but before eleven it was not possible to simply return instances from a function, because the destructor would kick in — you would return a copy and the original object would be destroyed. C++11 fixes this long standing problem by handing you the opportunity to move the content of the original to the copy, allowing you to return objects, like in any sane programming language. Actually, the move constructor is much more important than showing off template and thread trickery, but Brian and me really wanted to bring you the go() function this time.

The Yearly Countdown

End of year, December 31st. Every year millions of families world-wide gather round the tv-set just before midnight to watch the clock tick tick tick away the final seconds of the year. The clock strikes twelve and we yell “Happy New Year!” while outside fireworks burst, lighting up the sky.

It's about time

For some years already I run a desktop widget that counts down the year. I made it with Dashcode when I was just messing around on a boring January day. After nearly a year, I found an interesting bug: it started counting up in the next year..! Just like a regular clock does.

Anyway, it's fun saying things like “99 days left!” out of the blue and see people reacting “what was that all about?”.

The year 2012 had a leap second so there was another bug: it was off by a second. This was totally unnecessary had I implemented it properly ... Just saying that dealing with time can be tricky.

Two minutes to midnight

Counting down the days until year+1 Jan 1 00:00:00 is fun and not hard to do. Be mindful though that the naive implementation of doing sleep(1) in a loop is plain wrong. You will find your family and friends yelling out Happy New Year a split second before the counter reaches zero. Why is that? The thing is, you forgot about milliseconds, microseconds, and nanoseconds. This is illustrated by the following timeline:

23:59:56.852 countdown program start
             sleep 1
23:59:57.852 sleep 1
23:59:58.852 sleep 1
23:59:59.852 sleep 1
00:00:00.000 Happy New Year! on tv
00:00:00.852 countdown program reacts too late

Here, the program starts at an offset of 852 milliseconds causing it to react too late; it practically misses the strike of midnight. 852 milliseconds feels like almost a full second, so the countdown program just isn't good enough.

A better way to do it is to use either usleep() or nanosleep() to sleep fractions of a second and round it off to an (near) exact tick of a second.

Sleep with one eye open

Although you can do nanosecond sleeps, the practical accuracy of your software clock is about 15 milliseconds. This is because of timeslicing in multitasking operating systems. Really? Well, yes and no. Modern computers have a High Precision Event Timer (HPET) that can be used to do more accurate timing of events. This is entirely meant for doing things like performance measurements and not so much for wallclock time keeping.

No time to waste

A countdown timer is pretty neat and not so hard to write. It gets more fun when you add a big LED display in OpenGL graphics. I suppose it's too late now to get it approved in the App store and get rich before 2014 starts, but we can always try again next year.

Best wishes! and if you want to read more about high precision timing, see this excellent blog post by another code monkey:

http://tdistler.com/2010/06/27/high-performance-timing-on-linux-windows

C++ shared_ptr (or really C++ standard mess)

The C++ shared_ptr is a pointer to an allocated instance that ensures the instance is deleted after the last shared_ptr to the object goes out of scope (or is explicitly deleted). It's a great mechanism for doing some behind-the-scenes automated memory management. You can point multiple shared_ptr's to the same object and not have too much difficulty in managing the memory of the object that it's pointing at.

The shared_ptr first appeared in the boost library. Once upon a time we would write:

    #include <boost/shared_ptr.hpp>

    boost::shared_ptr<T> ptr;

Later, a committee found shared_ptr so cool, they said “we want that too” and incorporated it into the C++ library. The shared_ptr became part of the TR1 extension (first Technical Report), and we would write:

    #include <tr1/memory>

    std::tr1::shared_ptr<T> ptr;

For about a decade, work on the next C++ standard continued under the name C++0x. At some point, the gcc team at GNU recognized that TR1 would soon become part of the next C++ standard. So they already incorporated TR1 into the std namespace, but you would have to invoke the compiler with a special flag because it wasn't quite standard yet:

    #include <memory>

    std::shared_ptr<T> ptr;

    g++ -std=c++0x

Not that long ago, the new standard arrived as ‘C++11’. The compilers and library were updated. There was more to C++11, and it was a new standard after all, so GNU added a new flag:

    #include <memory>

    std::shared_ptr<T> ptr;

    g++ -std=c++11

At this very moment, things should have been good now since we have C++11. In practice however, we're in bad luck. Every platform ships their own ‘current’ version of the compiler, and it works differently every time. Older compilers choke on C++11, and newer compilers that prefer C++11 choke on the TR1 stuff. In order to write C++ code that actually compiles across multiple platforms, you have to:

• use autoconf (yuck)
• use ugly ifdefs to get the correct includes
• use typedefs, or hack the std namespace, or import entire namespaces
• use the correct compiler flags, and mind which flag to use for what version of g++

It's either this or telling people “Your compiler is too old!”.
We can only hope that time passes quickly and that TR1 will soon be out of the picture, only a vague memory of an obscurity in the distant past. Until then, ...

The quad-tree

Six years ago (which seems like an eternity already) I made a 2D arcade shooter in which you walk around the screen, zapping monsters. Each level is just one screen, and once you clear it, it's on to the next one. For collision detection, it checked every monster against the player, and every bullet against every monster. The game ran fine – especially on today's computers with near infinite power – but in terms of efficiency, it's quite bad to do that many collision tests. To make things better, I followed the good advice of the game programming gurus and added in a quad-tree.

Objects can only collide when they are near each other. So if an object is far away, you don't even want to test whether it might collide. Furthermore, if a group of objects is far away, you don't want to test for collisions with any member of that group. A quad-tree enables skipping large amounts of objects, thus bringing down the number of collision tests to perform.

The quad-tree is a space partitioning “device”; it divides 2D space up in compartments, automatically grouping objects together. It helps you select only the relevant group of objects for a possible collision and keeping the count of collision tests down to a minimum.

This post is not a tutorial on quad-trees, see below for a link to a good tut at gamedev.net. I had some additional thoughts on quad-trees.

Considerations

People often resort to using a uniform grid, also known as binning. With this technique, imagine putting a regular grid over the screen and adding objects to the bin (grid cell) that they are in. It's easy, but this is a poor solution that has all kinds of issues. For example when an object is on a cell boundary, it can be in multiple cells at the same time. If an object is so large that it spans many cells, there will be a big problem. If the player is at the edge of a cell, you'll have to check the adjacent cell as well. If the player is at the edge of the world, take care not go out of bounds. All in all this technique just isn't very good, and it wastes memory when the world is large but sparsely populated. The quad-tree however, is elegant and efficient and works in all cases.

Some people seem to think that a quad-tree can only deal with fixed size problems, i.e. the root node should be able to hold all objects that are in the world. This is so not true (!) If your quad-tree implementation uses arrays, you are doing it wrong. It is much more efficient to chainlink objects together using pointers. Like so:

    q.objlist => obj1.neighbor => obj2.neighbor => NULL

This scales dynamically, without cost, without growing arrays or allocating any extra memory at all.

Other uses for quad-trees

The quad-tree is ideal for static geometry like wall segments. Since the walls don't change, you can generate the quad-tree only once when loading the level and keep it around for testing against while the game is running. For moving walls and destructible environments it's probably easiest to use a separate, second quad-tree. (* If you are a graficks wizard clever, you may use BSP trees for this purpose. Quad-trees are much easier to use though.)

Another ideal use of quad-trees is for view frustum culling in 3D engines. If a node falls outside the view, then all of its leaves will not be visible either, culling a large number of vertices at once. This is typically used in terrain rendering, but also works for other kinds of scenes.

Taking it one step further, you can use the same technique for doing occlusion culling. From a nearby object you can create an occlusion frustum. The nodes that are in the occlusion frustum area are not visible and can be culled away. If it's a large building or a mountain that is in the view, it will pay off to do this little extra work. Occlusion culling is an advanced topic, and I'm not convinced that modern games actually do this.

It's trivially easy to extend the quad-tree code to an octree for use with 3D data.

Quad-trees in science

Cosmologists like doing simulations of colliding galaxies. This involves simulating gravitational forces between large numbers of stars (or bodies). Because each and every body interacts with each other body, this is called an n-body problem. One way of implementing such a simulation is the Barnes-Hut algorithm, which uses a quad-tree to group bodies together. Barnes-Hut may treat groups of bodies as a single body by using its center of mass, and thus having a single gravitational force. It's easy to see how the use of a quad-tree greatly speeds up such a simulation.

Links

• Quadtrees for collision detection at GameDev.net
• Barnes-Hut algorithm by Ventimiglia & Wayne, who teach at Princeton University (not game programming class)
• Barnes-Hut simulation at Wikipedia, with cool pictures