# 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.

## 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 on other sites
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 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.

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 103
• 11
• ### Forum Statistics

• Total Topics
632976
• Total Posts
3009672
• ### Who's Online (See full list)

There are no registered users currently online

×