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]

collision detection

might be useful. I didn't see anything about "sweep and prune" on that page, though.

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.

^^^^^

sorry that was me.

the forum is behaving weirdly today, indeed

- leiavoia

lol, care for a 4th attempt?

testing 123

seems my cookies are messed up. I'm logged in and yet not !?

[ my sincere apologies for ruining your thread BTW. ]

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.

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.

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.