Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm relatively new to game development and have been trying to learn how collision detection is coded. I mostly work with Actionscript 3, but I'm learning C++ on the side.

I've been wondering how "bullet hell" and top-down shooters optimize their collision detection with so many objects.

Any information/theories would be great.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

They usually handle this through spatial partitioning.

The theory is simple: would a bullet in the top-left corner of the screen need to check against the ship, in the bottom-middle of the screen? Not really; they're too far apart to possibly collide this frame.

How do we solve the problem of "figure out what objects are close enough to collide with other objects?"

Simply, with a grid:

  • Divide up the screen into arbitrary cells (eg. 100x100).
  • Place/update the position of every object into its cell (note: objects that cross cell boundaries can live in multiple cells)
  • On collision check, just get the cells an object belongs to, and check collisions against only other objects in those cells.

This is called "spatial partitioning" in 2D There are a lot of details depending on your target language. In 3D, since we're dealing with a cube, it's sometimes called "octree partitioning" (imagine the space as a 2x2x2 or NxNxN grid of cubes).

For more details, look up 2d spatial partitioning. There should be an available implementation for Flash that you can probably reuse.

share|improve this answer
    
Oh, so its like the way you would handle collision detection in a tile-based platformer? –  inzombiak Mar 12 '13 at 12:00
    
Spatial partitioning is a very general solution. You can apply it to any genre -- including a tile-based platformer (you can only collide with nearby tiles, right?) –  ashes999 Mar 12 '13 at 12:09
    
Yeah. Thanks for your answer. –  inzombiak Mar 12 '13 at 12:47
1  
Also, adding the concept of "dynamic" and "static" to your objects will helps a lot. Generally only "dynamic" objects will have a chance to collide with other objects. –  laishiekai Mar 12 '13 at 18:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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