Sign in to follow this  
RealmRPGer

Collision Detection elimination: Use grids?

Recommended Posts

I was wondering what the best/most preferred method of large-scale collision detection elimination there is? As in, quickly dispensing objects that are half a screen away from calculations. About the only thing I can think of is seperating the game into grids, but of what size and, more importantly, will updating all those grid lists be costly? AWhat about objects that are in one grid, but will be moving out of it this frame: are they technically in BOTH grids? Do you only check against the grid "you" are in, or do you have to check all 8 surrounding grids (which would be a pain)?

Share this post


Link to post
Share on other sites
What you're looking for is a spatial tree. Quadtrees and Octtrees are popular, as they're quite simple to implement and use.

Being a pessimistic sort, I'd personally recommend just brute-forcing things to start with. You can always retro-fit a spatial tree in later if you find that collision starts being a bottleneck. Just using simple bounding volumes for complex objects is often good enough.

Share this post


Link to post
Share on other sites
So, what, with the brute force method I do checks like thus:

if( me.RightEdge < you.LeftEdge
&& me.TopEdge > you.BottomEdge
....
)

?

Just seems like a lot of checks. Plus I have to check against EVERY object that exists.

Share this post


Link to post
Share on other sites
Yes, a brute force method would simply check every object against other object. If you're using simple bounding objects (like axis-aligned boxes or spheres) then the tests will be ridiculously fast. You'll be surprised at just how many objects you can handle without doing anything particularly clever.

At the very least I'd do the brute force method first. Then when you've got your collision detection working and objects reacting to each other you can optimise it at a later point (where 'later' might be straight after, or in a couple of months time when you actually know you'll need it).

Spatial trees are essentially optimisation techniques, and you always create a working version before trying to optimise it.

Share this post


Link to post
Share on other sites
If the OP doesn't mind I'd like to push in a related question. What if when using either of two methods (grid or brute force) object A's movement intersects both B's and C's ? How do you know which one to calculate first? If we just iterate through an array and do the A-B Collision first, but in reality C was closer to A, then that collision will be completely missed? And if we start brute forcing to first calculate time required for collision, then act on collisions again wouldn't that require n^2 time for time checks and even more to calculate the next collisions after the first collision is done?

Share this post


Link to post
Share on other sites
Brute force benefits from full-on optimisations. Since it's an extremely repetitive and simple task, if you align your data according to what's best from the hardware perspective, organise your instructions and cache usage, use registers carefully, it can be EXTREMLY fast.

Of course, it's a different exercise than higher level optimisations.

brute force, unoptimised...


for(int i = 0; i < num_spheres; i ++)
{
for(int j = i+1; j < num_spheres; j ++)
{
Vector Diff (spherepos[i] - spherepos[j]);
float diff2(Diff.x * Diff.x + Diff.y * Diff.y + Diff.z * Diff.z);

float rad = (sphererad[i] + sphererad[j]);
float rad2 = rad * rad;

if (diff2 < rad2)
{
DoCollisionCheck(i, j);
}
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Verminox
If the OP doesn't mind I'd like to push in a related question. What if when using either of two methods (grid or brute force) object A's movement intersects both B's and C's ? How do you know which one to calculate first? If we just iterate through an array and do the A-B Collision first, but in reality C was closer to A, then that collision will be completely missed? And if we start brute forcing to first calculate time required for collision, then act on collisions again wouldn't that require n^2 time for time checks and even more to calculate the next collisions after the first collision is done?


Yeah, but usually, it;s a trade-off. Your objects have to move ridiculously fast or have very shallow collisions to have a case like that. Personnaly, I would not worry about it, in a game context. IF you do want to make sure you have the absolute earliest collisoin first, you can reduce collision checks by time, and process the earliest.

say, you do A-B, then A-C, but C should take precendence over B, you do check the two cases, A-B and A-C, but do not act on them right away, just record the earliest. Then you apply the collision response, and then you have to retest all objects against A again... Until no other collisions are detected.

Quake3 works a bit like that. One by one, It traces one object against all others, take the earliest trace result, move the object to that position, apply response to that object, trace again.

Share this post


Link to post
Share on other sites

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