LÖVE

What's the best way to do square-based collisions on a bullet-fest 2D game?

Basically I need to check the next collisions:

- Player collides enemy
- player collides enemy bullet
- player bullet collides enemy

The problem here is that the game will have many objects, so i want some method to avoid thing like
That is, for's inside for's i think are unavoidable for situations where there are a group of objects that can collide with elements into another group of objects.

So what I'm asking is what is the best (most efficient) way to do this, having into account that what I'm doing could be ported to android, that is less powerful than PCs.

[EDIT]

And when i'm talking about "crowded situations" i mean "situations where there could be 20 enemies, 100 enemy bullets and 20 player bullets", those for's could be a true processor time black hole...

Hi,

I'm inclined to think that it is always better to start with simple logic.
If it works, but not fast enough, you can start thinking of ways to improve/faster it.
So, here is a simple way to proceed, first. I'm not saying it is the best, though.

The idea would be breaking collision checking in small for loops.
On the top of that, there are lots of tricks that can be used to reduce the number of collisions checks. But that would be very dependant of the gameplay, though.

If most of the time, ennemies are near each other, you can think of a way to group them, and then keep track of a bounding box that surrounds the whole group. Then each loop, the player will be tested only against this very bounding box. And if this collision test happened to be true, you can start loop trough the complete set of ennemies to identify exactly whom the player is actually colliding with.
Same goes for the bullets...

Also, the way collision checking is done is quite important. If you're dealing with simple AABBs (bounding rectangles), that won't matter so much. But if collision checking is a quite complicated process because you're dealing with more complex shapes , you might want to break the previous logic in two steps: make simple AABBs checks to find possible colliding pairs, and collect them. Then out of the loop, use the exact collision checking algorithm to detect if there's really collision and run the ad hoc logic.

[Disclaimer: Overthinking here (took too much coffee)]
I am also thinking of a way to cluster the space, yet it is not proven to be the efficient solution here.
The general idea is the partition the space in virtual grid, where each cell would be a square larger than the largest entity in the game (width or height, actually). Then each update loop, compute the x, y cell coordinate for each moving entity, and skip collision check when the player's x,y grid coordinates are different than the other entity tested against the player (i.e they are not in the same grid tile). It may be interesting actually if all entities have approximately the same size (I mean player and ennemies) and also if the grid is reasonably huge...

What you wrote in your code is what i'm doing actually with a simple AABBs algorithm but I like to plan things before problems appear. Low efficiency is a problem that will happen later on, but I don't think it's due to the AABBs method, I think it's due to the way of calling this method.
I'm not using complex shapes and square based bounding box is ok.

The problem comes mostly when i need to do double for's, for example in playerBullets vs Enemies.

Your big square bounding box idea would be ok but the enemies will be changing position relatively fast and not necessarily in a linear way, even most of the time they will move in circular or arcs. I can't think a way to group them without have to recalculate the group bounding box every frame.

The only solution I can think now is to use some cell-based method, but the problem here is that I will lost time calculating the cell position for many enemies and player bullets.


Basically the question is not "should I use AABBs"? Its "how to avoid nested FOR's with thousands of iterations each frame"? "Is there any method to only check some specific collisions and discard other possible checks that we could know they will not happen"?

There is no free lunch. What cycle time you save using a collision pruning algorithm will more than make up what you lose doing it. For 1000 object pair brute force checking will require 1000^2/2 checks! If you're worried about performance lost with cell based collision pruning, don't. Go for the cell based method. Here's an example to get you started: (Also known as a "spatial hash") http://vrld.github.com/HardonCollider/r ... patialhash

dreadkillz wrote:There is no free lunch. What cycle time you save using a collision pruning algorithm will more than make up what you lose doing it. For 1000 object pair brute force checking will require 1000^2/2 checks! If you're worried about performance lost with cell based collision pruning, don't. Go for the cell based method. Here's an example to get you started: (Also known as a "spatial hash") http://vrld.github.com/HardonCollider/r ... patialhash

I will take a look at your suggestion.

But By now, I found a way to save processor time using AABBs algorith and nested for's

The problem comes with the nested for's, so I concluded that checking collisions every frame is futile if we already know that an object is actually colliding with another one.

This is, If we know that XXXX is colliding with YYYY, then we should stop checking for collissions.

I didn't implemented this, but I think it could save a lot of unnecessary calculations.
And it can be used with whatever method is used for collision calculations.


What I thought is a trigger variable that can be either TRUE or FALSE.
We start the app setting it to TRUE (reason will be clear soon)

Now we check two objects if they collide, lets call them A and B.

If A collides with B, we set our trigger to TRUE.

While our trigger is TRUE we don't run the collision detection as normal, we just call another method "M" to check if A is still colliding with B.

If both are still colliding, we are only doing a simple math operation without any for or any iteration thing in our method M.
But if we found that A is no longer colliding with B, we set the trigger to FALSE, and then we can go and check all collisions.


Although this method doesn't saves us time during "normal" collision detection, we can really save time by not checking them unnecessarily.


But anyway I will check out your new method. Thanks.

If you're going to have more than a few dozen objects looking to perform some collision detection, you're going to need to implement some Broad Phase collision detection. The simplest version is called the Spatial Hash, and I can outline the algorithm:

1. Create a 2d array of lists, with a width/height that is either the same or some scale less than the world the player can fit in. Meaning, if the player can travel from (0,0) to (1024, 1024), make your 2d array that's 64x64, so that each cell in the array is 16 pixels wide. This is the "Spatial Hash"
2. For every object that can collide, add them to the list in the Spatial Hash that corresponds to their location. A bullet at (257, 257) would go in cell (16, 16).
3. When an object moves, remove them from the Spatial Hash cell they were in, and then add then to the cell that they will be in.
4. When the time comes to check for collisions, go through each cell and pick each item. For performance reasons, you don't have to iterate every bullet, you could just check the player.
4a. Get the width/height of each item in the cell you're in
4b. Loop through the surrounding cells that correspond to the size of the item. If your bullet is 3x3, and it's at (257,257), it'll be overlapping cells (15, 15), (16, 15), (15, 16), (16, 16).
4c. Compare the item to the other items in the cells that they overlap for collision.

The net effect of this algorithm is that each item is only comparing itself against nearby items, which greatly reduces the number of collision checks that need to be made. So, if you're only checking if the player is overlapping bullets, and the player is at (96, 96), then it won't be compared against bullets that are elsewhere on the playfield, just in surrounding cells in the spatial hash.

Understand, though, that this is a heuristic. If all bullets are coming from a single enemy, and he's firing directly at the player, then this algorithm fails, since all of the bullets will be in the same cell together, which means you need to do a full check against all objects.

Just to mention that I have an implementation for spatial hash.
See here, there's also a demo available.
You can also find another one here, for Marrekpie.
There's also a spatial hash implementation in HardonCollider.
You might also want to take a closer look at dreadkillz work, featuring a different technique, SAP (Sweep and prune).