Monday, June 13, 2016

Collision detection optimization for a top down shooter


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

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...