The Developer’s Cry

 Yet another blog by a hobbyist programmer

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