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

  • \$\begingroup\$ This is why we have quad-trees \$\endgroup\$
    – Alec Teal
    Commented Sep 22, 2015 at 20:18

1 Answer 1


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.

  • \$\begingroup\$ Thanks for the in depth answer. This is what i needed to know \$\endgroup\$
    – philipp
    Commented Sep 23, 2015 at 7:16
  • 1
    \$\begingroup\$ Circles aren't expensive to compute? They are often used because they take up less space to define than boxes (center + radius, even in 3D, boxes require at least 2*Dim_count), and testing if something is inside a circle is just testing if the distance between the center and your object is less than the radius. No trig involved. Also sqrt can be avoided with just using distance squared. AABB checking is a considerably more expensive calculation, with the advantage that you can eliminate more empty space if your object does not fill the space radially (ie a log, or a 2x4). \$\endgroup\$
    – Krupip
    Commented Feb 3, 2020 at 16:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .