A container for accessing contents by 2d/3d coordinates

Question

There are a lot of games that can generally be viewed as a bunch of objects spread out through space, and a very common operation is to pick all objects in a sub-area. The typical example would be a game with tons of units across a large map, and an explosion that affects units in a certain radius. This requires picking every unit in the radius in order to apply the effects of the explosion.

Now, there are several ways to store objects that allows efficiently picking a sub-area. The easiest method is probably to divide the map into a grid; picking units in an area would involve selecting only the parts of the grid that is affected, and do a fine-grained coordinate check grid tiles that aren't 100% inside the area.

What I don't like about this approach is answering "How large should the grid tiles be?" Too large, and efficiency may become a real problem. Too small, and the grid takes up tons of memory if the game world is large enough (and can become ridiculous if the game is 3d). There may not even be a suitable golden mean.

The obvious solution to the above is to make a large grid with some kind of intelligent subdivision, like a pseudo tree-structure. And it is at this point I know for sure I am far into premature optimization. (Then there are proper dynamic quad/octrees, but that's even more complex to code and I'm not even confident it will perform any better.)

So my question is: Is there a standard solution to the above problem? Something, in the lines of an STL container, that can just store any object with a coordinate, and retreive a list of objects within a certain area? It doesn't have to be different than what I described above, as long as it's something that has been thought out and deemed "good enough" for a start.

Bonus points if there is an implementation of the algorithm in Python, but C would also do.

Answer 1

The first step to writing a practical program is accepting that choices for some constants come from real-world considerations and not transcendent mathematical truths. This especially applies to game design/world simulation type coding, where you'd never get anywhere if you persisted in trying to optimally model the real world. :-)

If your objects will all be of fairly uniform size, I would just choose a grid size proportional to the average object size, and go with that. It's the simplest - and keep in mind simplicity will buy you some speed even if you end up searching over a few more objects than absolutely necessary!

Things get a big harder if your objects vary greatly in size - for example if you're trying to use the same engine to deal with bullets, mice, humans, giant monsters, vehicles, asteroids, planets, etc. If that's the case, a common accepted (but ugly) approach is to have different 'modes' of play depending on the type of situation you're in. Short of that, one idea might be to use a large grid with a binary-tree subdivision of grid cells after they accumulate too many small objects.

One aside: if you're using floating point coordinates, you need to be careful with precision and rounding issues for your grid size, since points close to the origin have a lot more precision than those far away, which could lead to errors where grid cells miss some objects.

Answer 2

Here is a free book available online that will answer your question. Specifically look at Chapter 18 on collision detection and intersection.

Answer 3

I don't know anything about games programming, but I would imagine (based on intuition and what I've read in the past) that a complete grid will get very inefficient for large spaces; you'll lose out in both storage, and also in time, because you'll melt the cache.

STL containers are fundamentally one-dimensional. Yes, things like set and map allow you to define arbitrary sort relationships, but it's still ordered in only one dimension. If you want to do better, you'll probably need to use a quad-tree, a kd-tree, or something like that.