# Designing Efficient 2D Collision for Topdown Shooter

This makes it the first time I'm posting here, so apologies if I stumble over beloved conventions.

Currently, I'm trying to figure out how I want to handle collisions for a large number of entities on screen (a bullet hell, top-down shooter). I've done a prototype of the game with some friends in the past before and we reached about 300 circular entities (a point with a radius "hitbox") checked against 3 every 1/60 seconds before considerable performance drops. The implementation was cringe worthy; due to lack of experience and a very stringent deadline, we didn't have time to do anything but a brute force distance check with each entity, making 900 pythagorean calculations per game loop.

This time I'd like to approach it with some intelligence. Since I'm simply checking for collision and not retaining any kind of directional information, I've managed to come up with two strategies. Unfortunately, they have their benefits and drawbacks:

1. Localized Checking - Essentially, creating a 2D array and checking only cells that the 3 entities exist in. The problem with this is that edge cases become an issue - say, if an allied entity is on the edge of a cell and an enemy entity is on the adjacent edge of an adjacent cell, I should have to check both, meaning there would be additional adjacent cell checks. While I can overcome this with a mandated "all cells that share a vertex" check and reduce the size of the cells to [standard entity radius * 2], it restricts the size of entities or forces me to use a separate system of checking for larger-than-standard entities. Obviously, avoiding this would be ideal.

• More importantly, while this drastically lowers calculations made during collision detection, the reassignment of an entity to another cell due to movement would create a computational step on all moving entities (most of them) during each iteration of the game loop. Furthermore, an additional call must be made to move an object from one cell to another when it has to migrate into another cell, which will be much more common as the cell size drops. This is not ideal.
2. Mathematical Checking - The theory goes that if we think of bullet patterns not as separate entities but as mathematical formulas expressed as the intersection of equations (linear, quadratic, etc.) and a sinusoidal function (determining position of an entity based on the y position on that function), checking would be simplified to 3 entities against the sum of all formulas present. Unfortunately, I lack the mathematical background to do this. Furthermore, designing bullet patterns becomes a giant headache, so the cost of designing levels rises (and I am of the opinion that the most expensive work is that performed by humans).

• What's more, if we take a basic curved formula such as a hyperbola, it is incredibly difficult to keep entities perfectly circular along the curves. Without a really good grasp of math, entities would appear oblong or pinched as the entity moves across the curve. This is extremely difficult to graphically represent without doing it dynamically, which would limit the visual vocabulary I am able to utilize. Also not ideal.

I'm not exactly sure how I'd like to proceed with this. Any thoughts out there? Standards that I've managed to miss?

-
Collision space partitioning (the 2d version of an oct-tree) is probably the answer. Groups bullets into sections and only tests against bullets in the same section. – ashes999 Feb 5 '12 at 3:17
That seems to be it, but I'll need to make movement efficient then. As it stands, I can probably calculate all of the partitions an entity must travel through based off of initial values, but the act of moving them through partitions won't be cheap, considering this has to be done per entity... No way around this, is there? – Rufei Feb 5 '12 at 3:36

I can't leave comments yet but have you looked into Box2D for collision detection? I'm not sure what environment you're working in but it's been ported for different platforms. I takes a little time to learn but I personally think it's worth the time.

-
I haven't prior to, but a quick glimpse at it tells me that it's useful for detecting collisions between a wide variety of bodies and retaining information regarding the collision (such as velocity in). As for deciding what subset of collisions do not need assessment, I haven't seen any immediate indication. Correct me if it does that. – Rufei Feb 5 '12 at 3:30
Nevermind - it seems that Box2D has a b2DynamicTree class that manages shapes in a dynamic, hierarchical AABB tree. It also has built in support for raycasts and region queries. I feaer it might be nearly the same cost as collision space partitioning, since movement would probably invoke a maddening amount of rotations, especially in worst case scenarios (say, two enemies spawning entities diagonally across the screen in a manner orthogonal to each other). Seems like I have to just run a mockup of this... – Rufei Feb 5 '12 at 3:48
There is collision filtering that might work for what you are indicating. box2d.org/manual.html#_Toc258082972 – Chuck D Feb 5 '12 at 15:07
Thanks, it does help as well. I'll have to give Box2D a thorough read, seeing as it does what I need it to do. Here's to hoping it's efficient. – Rufei Feb 5 '12 at 15:34

If your rate of fire is high, bullet speed fast and the target movement speed is relatively slow. A simple optimisation would be to use your original method with a larger collision circle that represents the maximum movement of the target in the time of flight of the bullet and exclude every bullet that fails the test from further physics checking. If a large portion of shots miss by a considerable distance this could speed things up a bit without a great deal more code.

-
If I did that, I'd end up making at least a single pythagorean calculation on every bullet per frame. Ideally I would have some type of container to hold bullets in that would indicate as a general rule of thumb if an object needs assessment in the first place, but there is that overhead cost of migrating said objects between buckets. (Of course, let me know if I am understanding your solution incorrectly.) – Rufei Feb 5 '12 at 15:38
Only in the worst case scenario that every bullet is being fired close to the target(s). The way I'm suggesting does the pythagorean calculation on firing and then does two range checks on the return value from the calculation. One to check if it's hitting and then one against a larger value to check if it could hit. If it can't hit then it has no further physics checks performed on it. So that every bullet that is never going to hit something has only has one physics check and if it is visible for say three or four frames, this method saves two or three physics checks. – Tristan Feb 5 '12 at 23:18
As for the migration between buckets in your firing method I'd separate your rendering and physics lists and add all fired bullets to the rendering list but only adding those that pass the larger range check to the physics list. So in further physics updates you iterate through only the items on the physics list. (Of which excluded bullets are not featured but they still appear on the render list so they are visible to the players but not to the physics engine) – Tristan Feb 5 '12 at 23:23