Spatial Partitioning

I guess it’s a pretty small group of people who get excited about “spatial partitioning,” but I think it’s one of the most interesting pieces of code to write in a game. There are lots of ways to do it, and the best choice for your game depends on lots of different factors.

For Ladon, I considered a few different methods. A quad-tree seemed like the best approach, at first, but I was able to do a little better with a slightly customized approach. There’s a great demo of how a quad-tree works here. As you move your mouse over the rectangles, you can watch it highlight the ones that might be touching your “player” object. And, if you watch those red lines appear and disappear, you can see how the quad-tree divides up space into smaller areas to reduce the number of things you have to test on each frame.

What I noticed with Ladon is that there are a lot of objects on the screen when things start to get hectic… The player’s ship has several tiles that all need to be checked against all the bad guys and all the bad guys’ bullets. Each enemy is made up of a few tiles that all need to be checked against the player and the player’s bullets. Using just a brute-force approach, with no partitioning, there are easily tens of thousands of collision tests to do in every frame.

In fact, even in this very simple scene I’ve been using for development, there are five player tiles, nine objects that you can shoot at, and roughly 45 bullets on the screen if you hold down the fire button for a few seconds. So, even in this drastically simplified scene, there about 450 collision tests required:

5 tiles x 9 spheres = 45 collision tests
45 bullets x 9 spheres = 405 collision tests
Total = 450 collision tests

The conclusion I came to here is that in a really busy scene, when collision testing really matters, the whole quad-tree will essentially be full. And a completely full quad-tree becomes nothing more than a simple grid. So, I decided to just punt all the complexity of a quad-tree, which has to constantly subdivide itself as things move, and replace it with a simple grid.

The results are really encouraging. In this simple scene, the number of collision tests done on every frame drops from around 450 to less than 10 in almost every case. The only trade-off is the small overhead of having to populate the grid on each frame. That only has to be done once for each object. So, with the exact same scene as above, the amount of work done on each frame becomes:

5 tiles = 5 grid inserts
9 spheres = 9 grid inserts
45 bullets = 45 grid inserts
~10 objects that fall into the same grid cell = 10 collision tests
Total = ~60 grid inserts and ~10 collision tests

And that is roughly a 10X improvement in performance. I’ll have to add some legitimate benchmarking at some point so that I can compare the two methods in real time.

A quad-tree has a lot of flexibility that this grid system doesn’t, though. A quad-tree lets you choose how many objects are allowed to be in the same cell before it subdivides itself, as well as the maximum number of subdivisions. My flat grid approach’s only configuration option is the size of the cell. I think that’s all the flexibility I need, though!

Check out version 0.0.2.1 here.

Latest version here.

Leave a Reply

Your email address will not be published.