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.
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:
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.
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:
I'd like to add my two cents here since I'm working on something similar.
I'll admit that spatial partitioning is very important to learn and is quite useful for most 2D games. Especially for ones that are very open world. However if your making your game like space invaders or touhou (which is what i'm doing now) then I'd encourage you to do some math before you start. And just to make sure we are all on the same page it's very very very much faster to write to ram than it is to read from it (which is the backbone of spatial hashing/oct trees/bsp's).
Now take this scenario into account:
Say you only have one player and the said player has no allies. And on top of that enemy bullets don't collide with anything besides the player(accept maybe the outer window area for cleaning).
I don't think this would be a good place to use anything besides something "close" to brute force collision (basically something not hash related). And here's why: Say you were able to split the window (or world) into 100 total blocks/chunks/hash's. Now lets say that there's about 1k total enemy bullets on the screen and they are fairly evenly spread out. That means we would likely check about 9 blocks around the player so take that 9 and divide it from 1k. That's likely to mean you get around 100 collision checks per frame/game tick.
Now I'll admit that's a huge cutback and the more blocks you use the greater the cutback at the expense of your ram (which if you're binding the game to just the window space like most than this is perfectly acceptable).
However we are only checking all those bullets against a single player (or maybe the other way around but that's not important). So lets take into account the expense of UPDATING the spatial table.
Usually this isn't very expensive for static objects but for ones that move around this means that each object will need to grab at least one extra piece of data from the ram to update the hash array. Assuming the above is true than your just basically adding at least 1k extra calls to RAM just to save around 900 calls.
However I think maybe the array/array location is stuffed into a register or kept in the L3 cache for the entire game somehow. Some input would be nice as I'm not an expert at this. But what I'm trying to say is that it's likely a better idea to use a hash table for something like player bullets and enemy positions. Especially if your making it where there can be at least 50 or 100+ enemies at a time and if you are using a LOT of player bullets. Think about it. if you had 100 enemies at a time and there's usually about 20 player bullets on screen at a time than this would mean that doing this brute force style would mean your doing about 2k collision checks at a time. what if you could have it to where each player bullet checks about 1/10 of that using spatial hashing? That would knock that 2k down to about 200 while only updating the hash table about 120 times(100 enemies + 20 player bullets). This would give a savings of about 2k-320 = 1680 calculations:) So the thing to take away is that hash's can be very useful but they shine the most when you are checking more of a variety. As apposed to having just one group of things checking with a single other thing.
Again if anyone has more info on exactly how much cost it is to update the hash table in c++ or any other language/settings please share as it's always nice to have such knowledge under your belt.
