I'm working on a 3D space simulation game in C++.

I've read that in many cases games use spatial indexing (hashing) that allows to quickly detect collisions, find out what entities to draw and so forth.

Is this really necessary for my game, considering that collisions between entities can happen, but are very rare? Is there any viable (and simpler) alternative?

up vote 5 down vote accepted

No, you don't have to. Remember that spatial subdivision is an optimisation. That means it isn't necessary until you've proven that there is no way your game can run fast enough without it. And optimisations are always prioritisable; what could be optimised with an octree, you might be able to optimise at a lower level, or in another way, so that no spatial subdivision is required. Prematurely optimising is a bad thing. If you've never written a game that required octrees before, chances are you won't have a sense of at what level they actually become a necessity.

Broadly speaking, you're not going to be capable of the same level of processing (read: number of entities in your world) without it, if only for physics purposes. Literally, because of the recursive nature of quad- and octrees, they improve performance by (an) order(s) of magnitude. So you'll probably have to be happy with a relatively simpler world as a result in the meantime (or per se).

Really, spatial subdivision is not such a tough concept to grasp. If you take quadtrees (2D) as a simple example, you can write very basic demo to get familiar with them, using a typical "balls bouncing around screen" type demo as a basis for learning how quadtrees work, and how to apportion collisions using them. You can then directly transfer your knowledge to octrees (3D). That would be my recommended path to a beginner in these.

Anyway, for now, just keep going using a uniform grid, and if things begin to grind, and you've already optimised a good amount in other areas, then look into spatial hashing.

The fact that collisions are rare is mostly irrelevant - it's how often you need to check for them that matters. The optimisation is to reduce the number of object-to-object checks you have to make, not to reduce the cost of each check.

I totally agree with Nick Wiggill and would stress that spatial hashing is an optimisation, nothing more. Don't do it until you need it. However, I also agree with him that it's not such a tough concept to grasp, and you can go a long way simply with a uniform grid. eg. grid_x = universe_x % GRID_WIDTH, repeat for all dimensions. This partitions the space into several cubes, and it's easy to keep a list of ships inside each cube of space. Then, when checking collisions, you only need to check a ship against other ships in that cube and the ones in adjacent cubes. (Providing ships can all fit entirely inside a cube - if not, start with bigger cubes.)

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.