Sign in to follow this  

Linked Lists and Collision Detection

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

So I thought I had asked my last question for tonight but it appears I have not. As stated in my earlier posts, I have implemented a linked list system of collecting all my characters(the player, enemies, terrain, etc) in my 2d world. And it works great. Everything renders as planned. My problem comes with collision detection now. I am familiar with collision detection and know how to test for such but my problem lies in the way I am supposed to test each object against every other object. First thing that popped into my mind was to create a nested loop. As soon as I thought of that I immediately thought it was going to be a bad idea just because nested loops can kill performance if there are too many items within them. I guess I am more or less curious if there is a better way to do it than nested loops. I can't seem to think of any other way of checking every item against every other item. I will say that I am running into a problem with looping through my lists and it appears that I may not be able to nest linked list loops. Im not sure at this point so I wanted to get everyones opinion and see if that turns on a lightbulb upstairs. Thanks again!

Share this post


Link to post
Share on other sites
You've got a couple of options:

1) The most common is the quadtree (2D) or octree (3D). They are just ways of dividing your world into sections. Then you only have to search for objects in the same section for collision. Google for a better explanation; it can also be called octtree, btw.

2) A nested loop is simple and effective. I've used that for hundreds of objects with no slowdown. The most important idea is to have good trivial rejection. Make sure every object has a bounding sphere or bounding box. Also, make sure you don't check every object vs. every other object. For example, check the 1st object against every other object, then check the 2nd object against every object EXCEPT the 1st, etc.

3) Another fairly simple optimization is to sort all your objects by their position.x. This will eliminate a lot of checking if its done intelligently. I've heard of an algorithm that uses 2 lists containing all the game objects. One is sorted by x and the other is sorted by y. Then the lists are cross-referenced and a lot of rejection is done. This is much like the quadtree, but it is built on a per-frame basis.

Hope that helps.

Share this post


Link to post
Share on other sites
Octtree is the only way to go about doing this. You could have a separate linked list for each node which mentions the render objects. You need to only run a collision test on that particular linked list. Also you can perform a nested loop as its computation will not be very expensive.

Share this post


Link to post
Share on other sites
Wrap your objects in some kind of bounding volume. IE wrap the object in a bounding box, wrap the box in a sphere. So now you check against the sphere, if they are colliding check against the boxes, etc... That can save abit of time, but you still the same number of pairwise tests.

To reduce the number of tests by using a spactial partiationing technique like OctTree, quadTree, BSPTree,etc.

I would probablly use a quadtree for 2D, you will probablly want to have two trees, one for dynamic data the other for static.
http://www.gamedev.net/reference/articles/article1303.asp

Share this post


Link to post
Share on other sites
There is another algorithm you may want to check:

-Make a list of possible collision pairs
-For each pair get the time of the first possible collision (the distance between the 2 objects and the maximum speed of each will give you the time)
-Reject pairs that will never collide (ex. 2 static objects, 2 non changing direction moving in different ways, two temporary objects to far away to meet within their lifetime)
-Make a priorityTree (google it for the implementation, also called heap)

-Per frame
- get from the priorityTree nodes untill the node you get has a time higher than your current time
- test collision for the extracted node(s)
- update possible collision time
- put node back into the priorityTree

:) It's a bit more complicated, but I used it and it gave me great results. I have a 3D world with 3D collision tests and I have no frame drops with 500-1000 objects in world (without space partitioning), some of them fast moving.

Of course, you can combine this with some space partitioning and you may get even better results.

Share this post


Link to post
Share on other sites
I was wondering if Blade02 could explain his algorithm, i think i will use that; i would be able to do that with my engine and it sounds like it would be the most efficient. if there's a website or some code to show, that would help, thanks.

Share this post


Link to post
Share on other sites

This topic is 4246 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.

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