Sign in to follow this  
Taco2003

Searching through a linked list

Recommended Posts

Taco2003    122
For the little game I'm working on now I have my objects stored as a linked list. I'm just wondering how would I go about determining if I push an object and it collides with another object, how do I determine where those two objects are contained within the list. eg the list: Object 1, Object 2, Object 3, Object4, etc If I push my object one, and it collides with object 4, how would I determined that its object one colliding with object 4 and not 2 and 3. Hope that makes some sense

Share this post


Link to post
Share on other sites
Pipo DeClown    804
Just parse through the whole list and skip the object itself:

while(list_not_end)
{
if(current_object != object_self)
{
do_collision_test();
}
}


Of course this could get heavy when you have a lot of objects in the list. The best way to do collision is by NOT doing (all of) it. You need to find a way to first check if the objects are anywhere near enough of each other, which makes it necessary to perform the test.

Share this post


Link to post
Share on other sites
Inmate2993    222
The colliding object is the one you do the reference against. It sounds weird, but lets say you just want to know which objects collide with which, and aren't too worried about who caused the collision, you'd do something like this:

object * i, * j;
i = list_head;
while(i)
{
j = i->next();
while (j)
{
if ( collision( i, j ) )
{
correct_trajectory( i, j );
}
j = j->next();
}
i = i->next()
}

This isn't terribly efficient, but this should give you and idea about how to work such a system. Because it was i and j that collided, everything else in the list has nothing to do with the collision, because they're not the ones being considered at the moment. Also note that once i has considered itself against everything else, you don't have to consider it from the reverse, so the number of checks is less than a O(n^2). Its still complex though.

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