# The Developer’s Cry

Yet another blog by a hobbyist programmer

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.

## 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.