Searching through a linked list
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
Just parse through the whole list and skip the object itself:
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.
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.
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:
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement