3
\$\begingroup\$

I'm creating an Android game that relies heavily on collision detection for a couple of players (at least up to 4). I researched hierarchical structures that could speed up the process. Because I have worked with hierarchies of axis aligned bounding boxes for ray tracing in uni, the sweep and prune algorithm is currently my favorite choice.

However, I had the idea to use bounding boxes not only for the obstacles in a level, but also some boxes containing as much of the free space in the scene as possible. If the player's character stays within one of those during his movement between two frames no further intersection tests should be necessary. Could this approach reduce the number of intersection checks where a player's character intersects one or more axis aligned boxes but not the objects within?

I highly doubt I am the first person who thought of this, yet I didn't find something like it online. So, is there a good reason not to do this? My best guess for why it isn't done is that there is no good rule to find applicable bounding boxes for empty spaces in between. But if they are precomputed before the game I don't see this as a problem. Maybe they could be bounding spheres instead. Those could be grown from an obstacle's surface until it touches obstacles in at least three points, like so:

Bounding volume hierarchy

Any advice would be greatly appreciated

\$\endgroup\$
  • \$\begingroup\$ This is why we have quad-trees \$\endgroup\$ – Alec Teal Sep 22 '15 at 20:18
3
\$\begingroup\$

You're talking about broad-phase collision detection—a system that lets you return early when clearly no collision is happening. I've previously written this overview of collision optimisation.

Such systems typically use a spatial indexing scheme. Popular choices in games include grid-based spatial hashing, quadtrees and k-d-trees. All make different efficiency tradeoffs, so the right choice depends on your needs.

For example, here is an illustration of N's grid-based partitioning, as detailed in Metanet Software's excellent tutorial:

N game tile map, with overlaid information of edge type
ⓒ Metanet software (source page)

All moveable and immoveable objects in their system occupy a square tile. Only objects contained within the same square tile need to be checked for collision. They also describe the tradeoffs of their approach in section 3.


I'd recommend against your particular idea, unless circle-shaped empty spaces are of special importance in your game. I don't know of (and can't imagine) a useful spatial indexing scheme based on circles that could easily be partitioned recursively. Circles also tend to be expensive to compute with, as related equations involve trig and square roots.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the in depth answer. This is what i needed to know \$\endgroup\$ – philipp Sep 23 '15 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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