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.
Answer
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.
No comments:
Post a Comment