Sign in to follow this  

Efficient collision detection of 2000 moving objects?

This topic is 4835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, In a large open arena which could potentially contain upto 2000 moving objects at any one time what would be the most efficient method for detecting collisions? I have read a few things on the forums which seem to suggest the sweep and prune method but im still not convinced. Can anyone convince me? Also I'm not entirely sure how the method works could anyone describe the process for me? Thanks. [Edited by - SpaceRaider on September 12, 2004 3:46:27 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
well, a "large open area" is begging for a spatial partitioning strategy. The problem is that you have a lot of objects. Spatial partitioning works good for large areas with lots of objects, but there is a slight amount of overhead for each object. With more objects, that overhead starts to accumulate and gets serious. With 2000 moving objects, i'd start to look at another method. If there were 1900 static objects (walls) and 100 moving objects, something like a quadtree would work incredibly well.

Share this post


Link to post
Share on other sites
Earlier this summer I had a great discussion with a couple guys about using grid partitioning versus quadtree lookup in RTS games.
(You can check out the discussion here)

At first I used the spanish hanging moss algorithm. Another user on the boards then posted this article, which is an optimized way of doing the above.

Using the second method, posted by the other user, I was able to initialize and check collision for 8000 units in 10ms (x and y coordinates only). Bruteforce took me 4216ms (I have a p4 2.4 ghz processor).

My code can be found here.

Whether it really is the most efficient or not, I don't know. But those resources should put you on track for a pretty good collision detection method.

Share this post


Link to post
Share on other sites
I read your links a bit. I think my method is slightly different. What i do is use a proper subdivided quadtree (as opposed to a raw grid). Since we are dealing with variable size objects, i get around the problem of classifying objects into overlapping sectors by placing the object into neither of the sectors it occupies... i place it into the parent sector instead. When i need a list of objects in the local space, i query the local sector, it's parent, it's parent's parent, and so on. That way i miss nothing and i do not get multiple checks for the same object.

The main problem is that you have to update the object's listing in the quadtree or grid structure everytime it moves. I haven't stress tested my collision routine much beyond a few hundred objects. It seems to get noticably slow around ~400 objects though.

I'm also not sure if the solutions you posted solve another problem: some objects that are very large or very long will occupy more than 2 sectors at a time. Some objects may span 3 or more. My system allows for this, but it's somewhat dependent on the game your are making.

Share this post


Link to post
Share on other sites
Quote:
Original post by leiavoia
What i do is use a proper subdivided quadtree (as opposed to a raw grid). Since we are dealing with variable size objects, i get around the problem of classifying objects into overlapping sectors by placing the object into neither of the sectors it occupies... i place it into the parent sector instead. When i need a list of objects in the local space, i query the local sector, it's parent, it's parent's parent, and so on. That way i miss nothing and i do not get multiple checks for the same object.

However, by placing objects into the parent nodes when they don't fully fit into the smaller child nodes can cause problems.

a) What happens when an object sits right in the middle of the map? - It will only fit into the top root node of the tree. Not good, as every object will have to test against it for collisions/rendering.

b) As objects get put into parent nodes, they are then within nodes that represent a large area/volume of space, therefore more objects may have to tested against for collisions.

Basically as you put objects up into parent nodes, you begin to lose the benefits of spatial subdivision... Which may explain why it gets slow with large numbers of objects, as more of them will be in higher nodes in the tree.

Share this post


Link to post
Share on other sites
Quote:

I'm also not sure if the solutions you posted solve another problem: some objects that are very large or very long will occupy more than 2 sectors at a time. Some objects may span 3 or more. My system allows for this, but it's somewhat dependent on the game your are making.


Easy enough to change I suppose, thought I never actually prepared for it in my implementation. But what I would do is just create a "clone" of the object in every grid it exists in. So objects will check that grid and check back at its actual locatin and size.

Also, calculating an objects location on a grid, unlike in a quadtree, is much simpler.

Just some things you might want to think about

Share this post


Link to post
Share on other sites
Good points from Hybrid and visage. I've thought of those but am willing to take the potential performance hit.

The alternative is to clone the object into the other sectors like visage said. So if an object exists in two nodes i would have to check that object against all objects in both nodes. That also decreases performance.

Share this post


Link to post
Share on other sites
there is an article in one of the graphics gems (#3? can't remember), called dynamic sphere tree. I like the concept a lot. It's like clustering objects together in a loose sphere tree. Very dynamic, and adaptable. Unfortunately, the code was a bit of a mess, and the article was very short.

I think for that kind of stuff, it's got to be anything loose. like a loose quadtree, a KDtree. Static partitioning (grid, voxels, quadtrees) for that amount of objects would impact the memory.

Sweep and prune is nice, as long as objects are well distributed. When they start to cluster a lot, or they are very large, there are lots of redundancies.

Anyway, I think I should read those discussions before posting... I'll be back.

Share this post


Link to post
Share on other sites
Thanks for the posts. I'm still a little confused though as it seems nobody agrees on the most efficient method. I guess it depends on the specific scenario.

The quadtree solution seems best to me, but in a world with 1000 guarenteed objects is this likely to slow down too much?

Oliii you mentioned the sweep and prune method, any chance you could explain how it works?

Share this post


Link to post
Share on other sites
that spanish hanging moss is nothing more than a 2D gridcell map. I can't believe the guy claimed he 'invented' it, anybody with a bit of sense would come up with the same thing on his own. [/rant]

about the second post, it's the same as the gridbased algo, but for sprites that can cover several squares.

About the redundant tests, That shifting method is insane :) I used a collision ID counter, that I increment for every object I test, and I store it into the objects I test against it. Then I avoid duplication of tests. no big deal really. You just have to remember to reset the counters and stored ID once in a while (using ints, reset it when one counter reaches 0xFFFFFFFF, which would be, ... every 10 or so days?!).

In the case of doing Collide(ObjectA, ObjectB), another thing is to make sure that ObjectB's physical address is greater than ObjectA's address. That way, you also perform the test only once per pair (you do A vs. B, and not B vs. A).

I wasn't too satisfied with it though, since it's not exactly efficient, as you do a proximity query stab for each objects, which also seems not very efficient.

So I used a gridmap like that for static objects, which aren't tested against anything, and used a sweep and prune algo for all mobile objects. Sweep-and-prune is performed as usual (mobile vs. mobile list trasversal), and mobiles are tested against the statics in the grid. Maybe I should not have bothered, but it was a good learning experience.

There is also another intriguing strategy that a friend of mine uses for his virtual city and autonomous agents PHD research. He is using a delaunay trianglulation. The whole City is mapped and trianglulated into a hierarchy of convex sectors, that's for the environment. It's used for navigation, path planning, traffic lights (set a portal as being 'blocking', 'forbidden', and other funky stuff like that). Much better than waypoints, since it's a lot more 'fuzzy'.

Then all the agents (cars, people, dogs, rats, ...) are stored into a delaunay/voronoi diagram. So each agent knows the closest agents to it, and can do avoidance by itself. The way the delaunay map is re-shaped every frame is quite complicated, but it's done localy for each agent as they move. Clever stuff, but way OTT (He is researching after all).

Back on the subject, for an RTS, I might contradict myself, but a grid-based approach would actually make sense. And it depends what you mean by collision entity. Could be a whole platoon, where the whole platoon is treated as a single collision block, and the little guys inside would not really collide with each other, or use some special faster and simpler collision code.

So in the end, the gridbased model, using a fast collision rejection algo.

Share this post


Link to post
Share on other sites
In gems 2 there are two good methods:

Sphere Trees (page 384) and Recursive Dimensional Clustering (228).

Sphere Trees work as such:
Each object is encompassed in a bounding sphere. While bounding spheres are generally known for holding extra space, the author insists that its actually good in some respects because it allows for all animations, etc for that object.

Whenever an object changes positions, it checks its distance from the center of its parent sphere. If it no longer is within the "skin" of its parent sphere, it is remove and placed into the root node of the tree. It is also placed in a FIFO queue. The parent is also placed in the queue. At each frame, all FIFOs are recomputed and reintegrated into the tree.

Unlike quadtrees and octrees, no sphere can over belong to more than one node on a tree. What is true for a SuperShere is true for its children (if it is outside the viewing range, so are its children.)


Recursive Dimensional Clustering is quite different. It claims, by the way, do be able to do collsion detection between 10,000 objects it 478 ms on a Pentium II 400Mhz machine. So, this might be something you want to check out. Here is how it works. First, it lines each object up by their first axis. You create a "bounding list", with each objects "open" and "close" location. Using something like quicksort, you order this list by axis location, lowest to highest. Next, we go through and create groups based on bracketed units.

For example:

{A,OPEN,7}{A,CLOSED,13}{B,OPEN,17}{C,OPEN,22}{D,OPEN,23}{B,CLOSED,23}{C,CLOSED,28}{D,CLOSED,29}

A would be in group 1. B, C and D would be in group 2.
Because A is a single unit, it can be tossed.

These groups are then passed to the Y-axis sort. In our case, B, C, and D must be analyzed in the Y case. Again, A doesn't need to be. So lets then say that when analyzed in the Y case, B becomes its own group and C and D get grouped again.

B gets tossed, C and D move on.

C and D are sent to the Z access, and do the same thing.

However, for any units to collide, they must be a group for all three steps. So the final steps for RDC are:

1) Start with the X axis
2) Construct a linked list of object bounderies in this dimension
3) Sort that list by boundry position, from lowest to highest
4) Find groups using the open/close bracket method
5) For each group found, repeat steps 2-5 in the other dimension(s) until the group no longer gets subdivided and all dimensions have been analyzed for that unique group.






Okay, so that should be plenty of methods to choose from. Rock on.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii

About the redundant tests, That shifting method is insane :) I used a collision ID counter, that I increment for every object I test, and I store it into the objects I test against it. Then I avoid duplication of tests. no big deal really. You just have to remember to reset the counters and stored ID once in a while (using ints, reset it when one counter reaches 0xFFFFFFFF, which would be, ... every 10 or so days?!).


Insane in a good way ;) Did you look at the math the guy did? I mean...it works. I personally wouldn't have even thought of it!

As for your method...I dont really like having to store those extra variables and keep track of them. Too much possibility for error I guess. I mean, what if you do forget to reset the counters and stored IDs? That would get pretty messy after a while (even if it is 10 days!) :D

Anyway, I dont know whats up with that guy claiming he invented the Hanging Moss Algorithm. I was doing it without even knowing it was actually a thing. I mean...it is just common sense.





I really like your friends method there though. Really, really impressive. But a word to the wise...when nobody knows that your friend exists, claim it as your own [wink]

-Visage

Share this post


Link to post
Share on other sites
True, it's clever, But I would never try to do such thing, as there is always a simpler solution for that kind of problems. But, kudos...

If you don't like that ID storing thing, which may looks hacky in a way but works really well, you can always store the objects tested in a bucket, and add new objects you test to that bucket. If alreay in there, don't test. That was the first solution I used, but it was far from optimal.

Anyway, if it is fast, and you understand the method he describes, you can try it.

about that dimensional clustering, that's another flavor of sweep and prune, in a complicated word. That's almost what I used for my mobiles in the world, with the hanging gardens of Babylon for the statics.

I used a 2D clustering, along X and Z. Enough for a racing game. It's quite cool and works well, as I said for nice, well distributed small objects, like spaceships, cars, humans and projectiles. And I suspect that particular method would aso work well if large objects were introduced. The special method I used would not cope well with that.

It's also particularly good if objects move relatively slowly. All you have to do is shift the object along the sorted lists, and recompute the touched groups.

Well worth a try. And I don't believe the 500ms (1/2 second?!?). It must be much faster than that with good optimisations, even on a pentium II, and for 10,000 objects.

The disadvantage of it is that it is not suited for very long ray-tracing (for things like A.I. vision), whereas the sphere tree and the hanging shrubs are much better at it.

Share this post


Link to post
Share on other sites
I am just telling you what the article said. Dont kill the messenger ;)

As for your two possible methods: what about the wasted memory? Also, if you use the object bucket method (which I know you said yuo werent...), dont you find that about 8000th object that the bucket is gettnig enormous, and searching through it is almost as costly as just running through the entire list?

As for the IDs: Dont you need to run through the IDs for the object you are checking the IDs of the object it "may" be colliding with to check if one has the other in their ID list? Again, doesn't this create major slow down once the number of objects increases and you are getting down to your last few objects? Though, it is probably only true for the initial test: once the game gets going these ID checks only need to be done when a unit moves.
But what happens when me and my allies move our 1000 unit army across a map to battle another 1000 unit army. Thats a lot of unit IDs being tracked.


Just some thoughts on that method...

Share this post


Link to post
Share on other sites
I'm not intending to kill anyone. If I sounded grumpy, it was probably my usual monday morning strop.

"As for the IDs: Dont you need to run through the IDs for the object you are checking the IDs of the object it "may" be colliding with to check if one has the other in their ID list?"

I just can't make up that sentence :)))

I stopped using the bucket anyway. As you pointed out, it's pointless when objects tend to cluster.

the collision counter is a global variable. in short, it falls down to this...


bool CCollisionGrid::GetCellsCoveredByObject(CObject& ObjA, int& xmin, int& ymin, int& xmax, int& ymax)
{
// whatever you fancy
//....
}

bool CCollisionGrid::TestObjectAgainstGrid(CObject& ObjA)
{
int iCounter = IncrementGlobalCollisionCounter();

if (iCounter == 0)
ResetAllObjectsCollCounters(0xFFFFFFFF);

ObjA.SetCollCounter(iCounter);

int xmin, ymin, xmax, ymax;

if (!GetCellsCoveredByObject(ObjA, xmin, ymin, xmax, ymax))
return false;

bool bCollided = false;

for(int i = xmin; i <= xmax; i ++)
{
for(int j = ymin; j <= ymax; j ++)
{
bCollided |= TestObjectAgainstCell(ObjA, i, j);
}
}
return bCollided;
}

void CCollisionGrid::TestObjectAgainstCell(CObject& ObjA, int x, int y)
{
bCollided = false;

CObjList& xList = *(GetCell(x, y).GetObjList());

for(int i = 0; i < pxList->NumElements(); i ++)
{
CObj& ObjB = *(xList.GetObject(i));

int ObjCollCounter = ObjB.GetCollCounter();

if (ObjB.GetCollCounter() == ObjA.GetCollCounter())
continue;

if (&ObjB <= &ObjA)
continue;

ObjB.SetCollCounter(ObjA.GetCollCounter());

bCollided |= TestForCollisions(ObjA, ObjB);
}

return bCollided;
}



can't be any simpler.

The ID is just like flagging the objects as "tested already", but you don't have to reset the flags every tests. Only every couple of hour or so (0xFFFFFFFF / (10,000 objects * 60 fps_per_sec * 3600 seconds_per_hour);

the cells covered by the object can also be pre-processed and stored in the object itself. It's like a double book-keeping.

Share this post


Link to post
Share on other sites
Interesting discussion. Let's talk more about the grid method.

Say I've got a map consisting of 128x128 tiles. Each tile contains a pointer to the first object in that tile, and each object has a next pointer so you can have more than one object in a tile (e.g., a bush, a rock, and a mobile).

So to check collision between objects I simply do a test of the surrounding 8 tiles...

123
4.5
678

...for the presence of anything "solid" (e.g., walls, other mobs, etc.) I then do a bounding sphere check on each solid and if I find I'm inside it, we've collided.

Now that means I'm only doing 8 single tile checks per, with extra (bounding sphere) checks if there are possible collisions. Sounds pretty fast, right?

Can someone tell me why I'd want to do it any other way?

Thanks in advance, and take care.

Share this post


Link to post
Share on other sites
Quote:
Original post by Heaven
Can someone tell me why I'd want to do it any other way?


You might consider:

- what happens if the object is larger than the tile/sector size?

- what if the object is not perfectly inside a tile but is crossing several tiles?

- what if an object is bigger or longer than 3 tiles across? Do you check 16 tiles now? 25?

- what happens if the object is travelling extremely fast and crosses sectors between frames? Which sector is it really in?

- What if memory is a concern?

- What if you had 2000 objects to check? ;-) 2000 x 9 sectors per check = 18,000 sector checks per frame, not even starting on the object checks. Ouch!


As you can tell, i'm just trying to be stimulatingly difficult.

Share this post


Link to post
Share on other sites
Quote:
- what happens if the object is larger than the tile/sector size?
- what if the object is not perfectly inside a tile but is crossing several tiles?
- what if an object is bigger or longer than 3 tiles across? Do you check 16 tiles now? 25?


leiavoia knows the solution, but I'll attempt to make it clerer for people not used to collision detection :)

Your object will have a sort of bounding rectangle, in world space. something like

CRect
{
float Xmin, Ymin, Xmax, Ymax;
int MinCellX, MinCellY, MaxCellX, MaxCellY;
};


your grid will have something similar.

CGrid
{
float Xmin, Ymin, Xmax, Ymax;
int NumCellsX, NumCellsY;

CCell* axCells;
};


So what you want, is the MinCellX, MinCellY, ... of the CRect structure, which defines the area covered on the Grid.

MinCellX, MinCellY, ... is basically a mapping of the Xmin, Ymin, ... counterpart in world space, mapped into grid space. It's actually called a linear mapping, and it's not difficult.

- First you need to find the 'percentage' CRect::Xmin represents in the range [CGrid::Xmin, CGrid::Xmax]. It's gonna be a ratio number, in the range [0, 1].

- You do that for Xmax, and CRect::Ymin in the range [CGrid::Ymin, CGrid::YMax], and finally for CRect::Ymax...

- once you got those values, which would stretch from 0 to 1, then you need to convert those ratios in grid coordinates. For example, a ratio of 0 will give you a grid coordinate of 0. A ratio of 1 will give you a grid coordinate of NumCellX.

- To be extra sure about what is being covered, you round the lower bounds to the integer below, and the higher bounds to the integer above.


// step 1 & 2 :
//-------------
float ratio_xmin = (Rect.Xmin - Grid.Xmin) / (Grid.Xmax - Grid.Xmin);
float ratio_ymin = (Rect.Ymin - Grid.Ymin) / (Grid.Ymax - Grid.Ymin);
float ratio_xmax = (Rect.Xmax - Grid.Xmin) / (Grid.Xmax - Grid.Xmin);
float ratio_ymax = (Rect.Ymax - Grid.Ymin) / (Grid.Ymax - Grid.Ymin);

// step 3 :
//---------
float grid_xmin = ratio_xmin * NumCellsX;
float grid_ymin = ratio_ymin * NumCellsY;
float grid_xmax = ratio_xmax * NumCellsX;
float grid_ymax = ratio_ymax * NumCellsY;

// step 4 :
//---------
Rect.MinCellX = floor(grid_xmin);
Rect.MinCellY = floor(grid_ymin);
Rect.MaxCellX = ceil(grid_xmax);
Rect.MaxCellY = ceil(grid_ymax);



That will calculate the cell coverage of an object on the map.


Quote:
- what happens if the object is travelling extremely fast and crosses sectors between frames? Which sector is it really in?


There are two solutions. Make a bigger bounding rectangle, to account for the displcament. Or trace the bounding rectangle onto the map. The easiest is the first one. And nothing should really that far. The grid is supposed to be rather large in size, with large cells. An object that is displaced as far as a whole cell size in one frame should not happen very often, if at all.

Quote:
- What if memory is a concern?

Then switch to another method. This is the main drawback of a gridcell approach. It's memory intensive. For example, a 128x128 grid gives you 16,000 cells. You can expect that each object covers 2.5 cells at a time on average (many will cross the boundary of cells. some occupying 4, some 2, some maybe more if they are large). for 10,000 objects, that's 50,000 references of objects in the lists (one object pointer, plus one pointer to the next node). all being pointers (cell probably only need to store a head pointer), the size will be already 64K + 320K = 384K.

Each object structure contains a rectangle (4 floats), 4 chars (MinCellX, MinCellY, ...), a pointer to the collision object itself (you should really dissassociate the grid partitioning with your collision system). that's 20 bytes. Times 10,000 = 200K. Granted, you do not need to store the Xmin, Xmax... in the object, since there should be a bounding box present in the collision object attached to the rectangle. So, 40Kbytes.

all in all, you can expect to be using 512K of memory for the partitioning system. On a PC, it might not seem much, but on a console, it means that you could have stored at least a couple of extra textures in memory, or half a dozen of high quality sounds. It's about 2% of the memory. On mobile technologies, it's a probably a no-no. Even compressed, it's still gonna take a fair bit of memory.

Quote:
- What if you had 2000 objects to check? ;-) 2000 x 9 sectors per check = 18,000 sector checks per frame, not even starting on the object checks. Ouch!


2000 x 9 is still better than 2000x2000 :)
Mapping the object onto the grid should give a coverage of 2, 2.5 top in average. So for 10,000 objects, it's 25,000 checks. A lot, but relatively unnavoidable. Whatever method you use, doing a per-object test will always be costly. You have to reduce the number of objects to test first first.

Note that the grid mapping does not have to be done every frame for each objects. And when objects move on the map, you do not have to remove the objects from every lists and add them again. YOu can just update the cells that are not covered anymore, and the cells that are newly covered. Ect... There will be an awful lot of optimisations that will come into play.

This is however one of the fastest methods, and it's straight forward, so you should give it a go. And also, consider ways of taking units as a whole entity, rather than small agents for collision avoidance between each members of the units.

For genreral collision detection, the clustering would definitely be my weapon of choice, but it's a bit more complicated, and can be attempted if the other system really bogs you down.

Share this post


Link to post
Share on other sites
Quote:
Original post by leiavoia
- what happens if the object is larger than the tile/sector size?

Not likely. We're talking archers, swordsmen, cavalry units, etc. Your typical medieval RTS fare. Each tile is big enough to fit one unit.

Quote:
Original post by leiavoia
- what if the object is not perfectly inside a tile but is crossing several tiles?

It's still linked to one of the 9 tiles we're checking, and will generate a hit when checking for collidable objects.

Quote:
Original post by leiavoia
- what if an object is bigger or longer than 3 tiles across? Do you check 16 tiles now? 25?

Not going to happen. See above.

Quote:
Original post by leiavoia
- what happens if the object is travelling extremely fast and crosses sectors between frames? Which sector is it really in?

This better not happen or there're going to be failures in game mechanics. Heh.

Quote:
Original post by leiavoia
- What if memory is a concern?

Every tile in the map already has a linked list to indicate what objects are stored in it. We're just utilizing the existing framework for collision detection. The only EXTRA data I'd be dealing with would be a byte or two for radius of bounding sphere.

Quote:
Original post by leiavoia
- What if you had 2000 objects to check? ;-) 2000 x 9 sectors per check = 18,000 sector checks per frame, not even starting on the object checks. Ouch!

Does that really take that much time though? I have no clue, but as someone already mentioned it's going to be a whole lot faster than 2000x2000 checks.

Thanks for your difficult stimulation. :) I'm convinced that this is the way to go, for an RTS at least. I just don't see the necessity of quad trees and all of that when a simple grid check will work fast and efficiently.

Take care.

Share this post


Link to post
Share on other sites
Ah, well for a simple RTS-like game, you can simply cross your fingers on a few of the what-if's.

The difference between a true quadtree and a grid is speed and flexability (isn't is always?). The quadtree can handle things in a more universal way, with less what-if's. The grid approach is less flexable, introduces more potential ambiguities, but is faster if done right. To sort objects into a grid simply requires a truncated division of the gamespace and x/y coords. A quadtree sort requires you to compare the geometry of the object to sort and the spacial node to sort into. And you may have to do it several times to drill down to the right node. I haven't worked much with a real grid as i went with a quadtree right from the get-go because it seemed to be more like what i wanted for my game (a 2D Metroid-like).

Share this post


Link to post
Share on other sites

This topic is 4835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this