Jump to content
  • Advertisement
Sign in to follow this  
Taco2003

Searching through a linked list

This topic is 4763 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

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
Advertisement
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!