Collision detection vs maybe 100 or so objects

[Charleh]

Hi all,

Just wondering if any of the pros could give me advice on which collision detection routine I should use for plenty of objects

They are just basic bounding circles in 2D that represent the bad guys, but I want to have plenty of them coming towards you from all sides -

There may be a time when the screen is almost filled with them and they are all coming at you, so I want to try and keep the number of objects high and the game smooth

Currently I've implemented RDC (recursive dimensional clustering) which might be ok, but when more bad guys clump together the subdivisioning 'power' is wasted and brute force checking takes over - before the bad guys clump the collision can take between 0/5 ms depending on if I throw a lot of objects at it - more bad guys clumping starts slowing it down

It might be ok once the game is nearer completion, but at this early stage I want to benchmark how many objects I can get on screen which are checking each other for collision.

Should I use a different technique? Or maybe a combination of techniques?

Any ideas?

[dandylion13]

Hello,

Here's what I've noticed in my own recent projects:

Display is usually a bigger bottleneck than the math, especially if you only have a small number of moving particles, such as a 100 or so. Are you blitting or using Sprites? If you blit, you'll get an immediate 4-5 times performance improvement, at least.

You could try a simple spatial grid, but it's unlikely you'll see any improvement unless you're pushing around more than 100 or so objects. The problem is that the various methods of spatial partitioning (quadtrees, sweep tests etc.) themselves need quite a bit of overhead to run, and are built using your own interpreted AS3.0 code. Brute force *might* actually be faster overall for 100 objects or less, because it runs super-fast math routines directly in the player. But you'll have to test, of course! :)

...rumblesushi, are you out there? You'll set us straight, I'm sure ;)

[rumblesushi]

Use a grid broadtree, cut into as small a segments as you can, and make sure your collision routine is as fast as possible, square root approximations within the grid cell, and make sure your collision resolve is fast too and not littered with function calls and/or unnecessary calculations for when many multiple objects do collide. 100 objects or so, even colliding with each other shouldn't have any impact on performance if done something like this.

[Charleh]

So basically spatial partition and then brute force anything thats close enough to collide? I suppose rather than a tree structure I could use a static map

I don't do much in the collide apart from 'push' the objects apart slightly, seeing as you are going to be overwhelmed a lot of the time I wanted the ability to push your way through the bad guys - yeah you might take a beating but you can get out of a stick situation - so basically there's not much processing going on during collision response

I haven't needed the 'actual' distance between the objects yet so there's no sqrt, but it might creep in a bit later so I'll use root approximations, is a table with interpolation quicker than iterative calculation?

I've tried all the optimisation tips for my RDC implementation but it suffers when too many objects get together as it drops the objects into one massive group and brute forces them all.

Maybe I should try RDC with a spatial partitioning method or spatial partitioning on its own - what's the math...

If there are 100 objects and they clump together you will get 10000 collisions (100x100) as RDC cannot seperate the objects on either axis - when the objects are all seperated you get almost 0 collision checks - which is nice...but I'm expecting objects to clump together quite a bit

If there are 100 objects and I use a simple grid cell partitioning method and the grid cells pick up say a maximum of 10 objects in each cell the worst case scenario is probably about 1000 collisions 10 * 10 * 10 - does that sound right?

So how do I deal with objects overlapping multiple cells - do I collide with objects in both sets of cells when an object occupies a cell boundary? I'm guessing I just build a list of objects in each cell (adding ones that overlap boundaries to more than one cell) using the object bounds and then run brute force collision objects in a cell

Wonder if I can combine that with RDC or would the overhead be too big with small numbers of objects?

I'll have to see what performance is like, but thanks for the suggestion

[justkevin]

Put some profiling code in place so you know how much time is being spent during actual collision detection, in case that's not the actual bottleneck.

Also, you try a collision detection algorithm like this (pseudocode from memory, may not compile):



if(this.x + radius < target.x - target.radius) return false;
if(this.x - radius > target.x + target.radius) return false;
if(this.y + radius < target.y - target.radius) return false;
if(this.y - radius > target.y + target.radius) return false;

.. more accurate test here ..

[Charleh]

Put some profiling code in place so you know how much time is being spent during actual collision detection, in case that's not the actual bottleneck.

Also, you try a collision detection algorithm like this (pseudocode from memory, may not compile):



if(this.x + radius < target.x - target.radius) return false;
if(this.x - radius > target.x + target.radius) return false;
if(this.y + radius < target.y - target.radius) return false;
if(this.y - radius > target.y + target.radius) return false;

.. more accurate test here ..


Yeah I've profiled the test already and I've got 0ms for spaced out objects but 20 - 30 ms for lots of objects clumping - this is because the RDC groups the objects together if they are closely spaced making one massive processing sink that eats up all the processor time because of the brute force checks.

The check you've given me doesn't really solve any issues as it's just putting a bounding box around each object and checking intersection - the problem I have is the partitioning of the objects to cut down on checks in the first place - I'm going to try a 1D and 2D sweep and prune and if that isn't quick enough I may try a dynamic grid or a fixed grid

I was thinking about creating a grid cell where an object is and then bucketing other objects that fall into the grid cell together - if I run through the object list linearly I can bucket objects or create cells if a bucket for that area doesn't already exist, though I'm thinking this might be slow

Other idea is to create a static grid and use array math with a grid size to calculate where each object is - then collide objects that share grid cells

Anyway, looks like I'll be experimenting - I'll post the results when I finish tonight! :)

[Valaran]

Im not sure this is completely what you're after but I think this tutorial deals with explaining how to deal with broad-phase collision detection in terms of grids:

http://www.metanetsoftware.com/technique/tutorialB.html

Theres also a very nice source on SAT aswell if thats interesting.

Edit: I see you replied before I posted, your last idea is pretty much exactly like what I linked, with some little extension perhaps.

[Charleh]

Im not sure this is completely what you're after but I think this tutorial deals with explaining how to deal with broad-phase collision detection in terms of grids:

http://www.metanetsoftware.com/technique/tutorialB.html

Theres also a very nice source on SAT aswell if thats interesting.

Edit: I see you replied before I posted, your last idea is pretty much exactly like what I linked, with some little extension perhaps.

I've tried the grid method but it seems about the same - I used a 32/32 grid and bit shifted the x/y positions of objects to get them into the grid cells but the bounding circles overlap the cell boundaries when the enemies are clumped so you still get a lot of checks - it's the brute forcing of lots of close objects. I can work out if the objects are moving towards each other using dot products which might speed things up a bit but I've seen engines done in flash with over 1000 particles moving about and colliding with a good 30 fps or more....

How do they do it!!?!?!?

[Valaran]

Well, a properly tuned RDC or quadtree should be doing the trick, if units are grouping up like you say, and its not the collision response being heavy, Im guessing you're simply not letting the RDC, or quadtree (or whatever) divide enough. I saw the question of rendering method aswell, but never an answer. If not blitting, I guess you could speed things up by doing just that, although killing one bottleneck with reducing another one seems a bit off, even to me :(

A quad-tree example, is this enough performance?

http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

I think there should be sources in his motor2 (more current ones).

[rumblesushi]

From what I've seen RDC is not particularly efficient for collision detection etc and has a decent amount of overhead itself.

Quadtrees are good, but in some cases a grid is better, and I love the simplicity of a grid and the fact that there is almost no overhead of it running at all.

Use smaller grid nodes, use flags to eliminate double checking, cap the amount of collisions at 1000, and possibly stagger collisions if it reaches over 1000, put them in a queue, and only process N number per frame.

A grid with small enough nodes, no double checking, and a capped amount of collisions should be at least as efficient as a quadtree. If you have them all bunched together, you're going to face the same thing, overlapping many cells etc.

[dandylion13]

I've seen engines done in flash with over 1000 particles moving about and colliding with a good 30 fps or more....

How do they do it!!?!?!?

http://www.adobe.com/devnet/flash/articles/blitting_mc.html

[Charleh]

http://www.adobe.com/devnet/flash/articles/blitting_mc.html

I'm blitting everything, that's not the issue - I have a manager that loads XML files that contain the definition of all game animations and textures, these are loaded into a dictionary and grabbed on object instantiation. With object pooling I can keep the overhead low on creating objects (it's not implemented yet) - I just want to know how 1000 objects can be bunched together and checking for collisions yet the frame rate be smooth and consistent!

I found a flash demo on DeviantArt that had over 1000 particles colliding and reacting to physics with no slowdown (I think I had over 4000 on the screen at one point and it was fluid). These particles can all be spread out or bunched and it doesn't seem to make a difference to the frame rate.

I can get around 50 objects on the screen using grid/rdc and it will start slowing - there is no way mine is as quick as it could be, or that RDC is the way to go



Well, a properly tuned RDC or quadtree should be doing the trick, if units are grouping up like you say, and its not the collision response being heavy, Im guessing you're simply not letting the RDC, or quadtree (or whatever) divide enough.


I don't think this is the issue - RDC doesn't divide, it un-divides. It starts off in the best state - no objects colliding, and then starts to clump objects together based on their bounds. The more objects clump, the more collision checks need to be carried out.

The grid method doesn't seem to be that quick at the moment either and seems to have a constant overhead for recalculating the grid which gives it the same speed as the RDC - of course I've not optimised it yet (as the grid is cleared down every physics step)

Also a limitation of the static grid is that it needs to be a fixed size - the bigger the grid the more cells it needs and the more loop time is needed. This also means that objects can't move to 'any' location, they must stay in the grid bounds

A dynamic grid might be the thing I try next

This is my static grid implementation in pseudocode (I'm at work so I don't have the code here)

Init:
Creates a 1D array of gridcells which is gridwidth * gridheight (say 100*100 - so 1000 elements)

Build grid members step:
For each collidable object get the bounding box corners
Check each corner of the bounding box and bitshift the x/y position by whatever the grid cell size requires (using 32*32 grid cells seems ok so I bitshift 5), use the x/y values with a little bit of math to get the grid position in the 1D array. This should be pretty quick
Append the object on the object list of the grid cell

Collide grid members step:
Check each cell of the grid - if there are objects to collide, brute force these objects (usual brute force algorithm, test each object against all those below it in the list)
Clear grid cell members ready for next physics step (saves writing another loop and we don't need the grid cell any more as it's been processed)

Now I know that I could probably make some speed increases - but I can't get over the fact that, with 1000 objects in a list, things are gonna be slow - what happens when I want the grid to be 200*200?

I might be able to use a quadtree - but doesn't restructuring a quadtree take up a lot of processor time?

I've had a look at polygonal labs before, but I've not tried the quad implementation on that site. I might give it a go.

edit: Just thought of something reading this back, I'm looping through 1000 grid objects after each check - I could just push the populated grid cells to an array and run a loop on this array saving a lot of time. I'll try that when I get home, if not - quadtree!

[rumblesushi]

You could try a quadtree and see if that works better, but why does your grid have any overhead?

On the code that runs for each particle/object etc, find which nodes it occupies, add it to the "currObjects" array of that node or nodes, remove it from the old ones if necessary, and bob's your uncle. The overhead should be absolutely minimal, especially for just 100 objects.

As per Valaran's link, make the grid segments slightly bigger than your object, so that no more than 4 nodes can be occupied at once, and with significant pushback from the collision resolvement you shouldn't come anywhere near the 10,000 collision checks of brute force. Especially if you make sure you don't have any duplicate collisions.

[Charleh]

You could try a quadtree and see if that works better, but why does your grid have any overhead?

On the code that runs for each particle/object etc, find which nodes it occupies, add it to the "currObjects" array of that node or nodes, remove it from the old ones if necessary, and bob's your uncle. The overhead should be absolutely minimal, especially for just 100 objects.

As per Valaran's link, make the grid segments slightly bigger than your object, so that no more than 4 nodes can be occupied at once, and with significant pushback from the collision resolvement you shouldn't come anywhere near the 10,000 collision checks of brute force. Especially if you make sure you don't have any duplicate collisions.

Yes my nodes are bigger than the objects they contain, and drawing the nodes I can see that the max nodes occupied is 4

I think the problem is mostly that I am looping over the 1000 nodes even though only 6 or 7 are occupied, and this loop takes the processing time up - I shall be adding occupied nodes to a new list and testing this list instead of the full node list.

As for removing objects from nodes, I'm also looping over all 1000 nodes and clearing them - this might be slowing it down (because esentially I'm creating a new array object for these nodes every physics step). I shall tweak and change this too

Collision resolution also checks if objects are headed towards each other using dot products so there should be minimal overhead in this part.

Also bear in mind, my PC at home is getting a bit long in the tooth, but if I can make it run well on that, then it will run great on better PCs!

I'll let everyone know what the results are

[rumblesushi]

That's certainly one thing that must be slowing it down.

You shouldn't loop over the grid cells at all, in fact that's what I love about grids, the fact that you can have a MASSIVE grid without needing to loop through the nodes.

I don't have an example of a large volume of moving objects using a grid, but I'm using a grid for this demo. Per polygon collision with a few thousand polygons, plus a few boulders, and it's very fast, has no impact on performance at all.

http://rumblesushi.com/snowscape.html

[Charleh]

That's certainly one thing that must be slowing it down.

You shouldn't loop over the grid cells at all, in fact that's what I love about grids, the fact that you can have a MASSIVE grid without needing to loop through the nodes.

I don't have an example of a large volume of moving objects using a grid, but I'm using a grid for this demo. Per polygon collision with a few thousand polygons, plus a few boulders, and it's very fast, has no impact on performance at all.

http://rumblesushi.com/snowscape.html

Ended up gridding it, can get at least a few hundred objects on screen now with no noticeable slowdown! Cool :)

So basically I'm just adding to grid cells using a bit of bitshifting to calc the target grid cell and then looping on the active cells. Works a treat.

I haven't even optimised it yet but I'm sure I can get at least 10-20% more out of it once I've cleaned it up a bit.

[dandylion13]

Great, glad you got it solved.
The humble spatial grid saves the day again! :)