Sign up ×
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

2 Answers 2

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
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

I wrote some articles on this awhile back. There are lots of different solutions to this problem, and the best answer depends on what sort of data you are using. A good general purpose solution is to use Zomorodian and Edelsbrunner's collision detection algorithm, which I implemented here:

You can read more about it and related approaches on the following pages:

share|improve this answer

Your Answer


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.