Optimized Collision Grid

Monkey Forums/Monkey Programming/Optimized Collision Grid

Tibit(Posted 2012) [#1]
Anyone know an optimized collision check for thousands of objects on screen? Like a Grid based system?

If not, anyone who can give some guidelines, tips or wisdom on how to "best" build one? Or links?


Nobuyuki(Posted 2012) [#2]
how are you checking it now? Best thing I know is to do an initial sweep to exclude objects from more complex collision detection by first doing an axis-aligned bounding box overlap test, then doing a second collision loop with your "actual" detection, if that second form of detection is more expensive. Put objects to sleep if they're outside of the game's camera range by a certain margin, too, and don't check those objects.

Objects which compare collisions against each other can avoid testing for the same collision twice by referencing each object by a number, then having a nested loop whereby the second object to be compared is always a greater number than the first, if I remember correctly.


edit: beyond that, you can speed up the AABB collision detection by removing conditionals from your loop where possible, as well as making assumptions based off axis distances from box to box. Logical operators can be your friend here.

[monkeycode]
'Warning: Uses integers for speed
Function DoBoxesIntersect:Bool(ax%, ay%, awidth%, aheight%, bx%, by%, bwidth%, bheight%)
Return (Abs(ax - bx) * 2 < (awidth + bwidth)) And
(Abs(ay - by) * 2 < (aheight + bheight))
End Function
[/monkeycode]


Nobuyuki(Posted 2012) [#3]
Now, for grid-based collision, having some sorta bitmask or 2d array may or may not be faster depending on how many objects need to test against this. Depending on the game, updating the mask could be a larger cost than just doing AABB tests on everything. However, for collisions with objects against a tilemap, a bitmask or array would be useful.

A priori collision detection is probably better for your health than an a posteriori one, although it's not always feasible to implement this in your engine in all cases. Before doing your movement calculations, what you would do is you'd check your object's position in the next frame against the bitmask/array's collision value in there, and if the next position is occupied by a collision tile, either stop the movement, or do a more sophisticated collision check, or process the change in movement from there.

Each object to check against the mask/array has to have their coordinates converted to the format which exist in it. For a 2d tile array, that usually just involves floored division. For a 1d bitmask, it involves that, modulus, and to push/pop stuff in and out, bitwise operators.

Long story short: If you have thousands of sprites (bullet hell shooter?), it's still going to be slow to do all these calculations, but if you have a bunch of non-sprite objects you need to test collisions against, having a tilemap of simple collision metadata's going to make it a lot easier to check against, since you won't be checking 50 zillion tiles individually. I don't have enough experience on limited hardware to know whether or not actively updating a bitmask with thousands of sprites on it would actually boost efficiency over a properly-looped series of AABB tests or not.


Nobuyuki(Posted 2012) [#4]
one more thing, since this is outside my field of expertise, but you can reduce the number of checks hypothetically by implementing your data in a quadtree structure. The wiki article knows more than I do, but I haven't taken the time to read/understand it in a comprehensive way.

http://en.wikipedia.org/wiki/Quadtree

If it is true that you have thousands of sprites, all of which need to be checked for collision against one another, and are mostly the same size or can be broken down into equally sized chunks at a large enough scale in a sparse map, then you can reduce the number of checks needed by implementing this. The performance gain may not be as large as you'd hope for, though, compared to other, easier-to-implement optimizations I mentioned earlier such as not performing collisions on objects that are outside your camera range, even if they're still being checked to see if they're in camera range.

There is also a technique I've heard of when looking this up for you called spatial hashing, which may be something to look into:

http://www.gamedev.net/page/resources/_/technical/game-programming/spatial-hashing-r2697


Tibit(Posted 2012) [#5]
Thanks guys!

Ok let me give more information.

Right now I do a distance check, pytagoras. I could optimize this by removing the Sqr() and check for radius*radius, however the problem in performance comes from scale I think.

Is an AABB so much faster than Circle? I tought a grid was a must to optimize this?
[monkeycode]
'Untested, but something like this is what I do, but using the vector class:
Function DoCirclesIntersect:Bool(ax%, ay#, ar#, bx#, by#, br%)
Local dx# = (ax - bx)
Local dy# = (ay - by)
Return (dx*dx + dy*dy) < (ar*ar + br*br)
End Function[/monkeycode]

Problem
So even with 25-150 something monsters and lots of bullets the games starts to get slow.

I want 1000 to 3000 enemies (or as high as possible anyway)

I should probably create a measurable performance test (I'll do that and get back with exact numbers). We did find out that html5 and flash can easily draw 3000 jumping teddy bears with high fps, 6000 with slight lag - so the rendering should not be the case I guess?

Assume 100 monsters and 100 bullets, that means for each bullet I loop the monster list 100 times and check collision. Total collision check 10k?

I did just realize EachIn creates an enumerator object. I'll go back and test with arrays instead. That might be the right place to look now that I think about it?

Anyhow, more information on Grid based optimization is appreciated! :D


Tibit(Posted 2012) [#6]
@Nobuyuki - great link about spatial hasing. That might be what I'm looking for.

I also found this XNA Article on the subject: http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

I'll test to implement something like that.


Gerry Quinn(Posted 2012) [#7]
Another method along the same lines might be to divide the screen into small squares, and have objects in each cell check for collisions with objects in 1 - 4 squares total, depending on where the object is in its square. If it's in the middle, it only cares about objects in the same square, if it's near a corner it has to check its own square and the three that touch it at that corner.


Tibit(Posted 2012) [#8]
Gerry do you know any links to resources on that? Or what the technique is called?

I was thinking along those lines myself, however I feel like the grid size in comparison to the entities is probably of great importance. The grid should probably be many times bigger than the sprite. I guess only dividing the screen into 4-16 sections could be enough even for quite large maps, with even spread of units it should reduce the hit checks a lot.

In theory. If 100 monsters are checked against 100 monsters (crowd collision) then we have 10k checks. Plus we have bullets and terrain, let us say 50 more objects resulting in 5k more checks.

With even spread over 9 gridcells. In avg that is 11 units/square. That means in each cell we check 11 units against 11 = 121 checks. That x9 = 1089 checks.

So with only 9 cells 15k checks is reduced to 1k checks. Plus some extra for borders. But this must work.


OvineByDesign(Posted 2012) [#9]
Another good technique which we use is spacial hashing :-

http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/


NoOdle(Posted 2012) [#10]
quad trees can be also be used for used for speeding up collision checking on lots of objects. Heres an article that might help explain how they work, I believe the source is also included if you wanted to have a peek before implementing your own. http://www.kyleschouviller.com/wsuxna/quadtree-source-included/


Gerry Quinn(Posted 2012) [#11]
Hi Tibit,

I don't know what the technique is called. I haven't used it myself but I thought up the algorithm in connection with an open-world RPG concept.

I agree that the grid size is important, but I think it should probably be small compared to the screen, otherwise there is not much benefit. It must be at least twice the size of the sprite on each dimension (assuming the sprites are all the same size). That way a sprite can only be colliding with sprites whose centres are in the same square or the four nearest ones.

[A sprite in a nearby square can jut into this square by its own radius, and the sprite we are testing can be another radius away, so a sprite in a square is safe from collisions with any square whose nearest border is more than a sprite size away.]

So I would make the squares only about three or four times the diameter of the largest sprite. And if there are some very large sprites I would treat them as special cases rather than make the squares very large.

You can always make it a variable and see what gives the best performance.

Also, if you are checking all collisions every frame, you should only check each pair of sprites once. The easiest way to do this is to only test each sprite against sprites that come after it (in whatever sequence you happen to have them ordered). So 100 monsters is only 99 + 98 + 97 +... = 4950 collisions. The squares algorithm doesn't make any difference to this.


matty(Posted 2012) [#12]
Yes...use a grid, only check for collisions when something moves, only check an entity's own grid square and the surrounding grid squares, make the grid squares comparable size to your entities, also only update the grid square when something moves in/out of it...should be able to have lots of entities running around at once..I use this technique all the time.


wiebow(Posted 2012) [#13]
Here is a quadtree I have made for blitzmax. You can convert it to Monkey pretty easily I guess, or I might have a go myself. :)

http://code.google.com/p/noisycode/source/browse/#hg%2Fwdw.mod%2Fquadtree.mod


Ferdi(Posted 2012) [#14]
FYI, if I am not wrong, Flixel Monkey uses quadtree to check for collision, last time I read the code.

Oh yep, it is in flxg.monkey, and look for the function "Function Overlap:Bool".

There are some neat stuff in there. devolonter did a great job on it.


Gerry Quinn(Posted 2012) [#15]
It might even be most efficient to make the squares only slightly larger than a sprite and always check nine squares. Easier to code too.


NoOdle(Posted 2012) [#16]
It might even be most efficient to make the squares only slightly larger than a sprite and always check nine squares. Easier to code too.

wouldn't this fail if one of the sprites was much larger than the grid square? It could reside outside of the grid but extend far enough to intersect with the sprite in question.


Gerry Quinn(Posted 2012) [#17]
Yes. The grid squares must be as large as the largest sprite. It will work best if all sprites are similar in size, which should often be the case.

If there are some large sprites, I would treat them as special cases. You could place them first in your sprite list (so smaller sprites will never have to worry about them) and test collisions against sprites in an appropriate number of squares (e.g. they might need testing against ordinary sprites in 25 squares and big sprites in 49 squares).

The grid algorithm is really designed for the case where you have hundreds of little sprites swarming around.


Tibit(Posted 2012) [#18]
The code to the spatial hasing example in XNA does not seem to work :(

Would have been great to convert that otherwise.

Yes, I'll look into making a simple fixed size grid I think. But how do I do with the arrays, if I have one array per cell - I guess that I can size the array according to the size of the cell in relation to how many units can occupy it at once.

And always check all border cells. Seems sensible :)

Tough in this game my enemies are different in size, and that is pretty cool. But I assume the biggest ones can still match the cells.


Dima(Posted 2012) [#19]
simple quad tree could be the game world divided into a grid of huge cells like 6x6, then each huge cell contains another set of smaller 6x6 cells, etc... until you reach desired granularity. You could potentially represent huge worlds with complex interactions but have to watch garbage collectors.


Gerry Quinn(Posted 2012) [#20]
If you wanted to be fancy, you could make a decent sized array for each cell, plus an overflow list for when the array is full. If your lists get used often, make the arrays bigger.

I think sprite size ordering is the way to go if you have a big range of sizes. Perhaps sprites of a certain size use a pseudo-grid that is bigger than the standard grid, i.e. each big grid cell contains a square block of ordinary cells lumped together. Easy enough to code without actually using large cells.


Tibit(Posted 2012) [#21]
Dima that sound like a great way for really large worlds. Atm my world is quite small (slightly larger than screen).

Still haven't found a perfect solution here. I'll report back if I do.

And Thanks everyone for the input so far.