Sign in to follow this  
lezebulon

How to parse collision objects

Recommended Posts

lezebulon    100
Hello :)
This is my first post and I'm not sure where to post it.

Anyway, I'm coding a 2D top-view engine.
There is a 32x32 grid used for drawing the backgrounds, but sprites are free to move pixel per pixel in this engine.

So, each of my entities has a rectangle bounding box, now my question is, how do I optimize the collision detection ?
I don't want to parse my whole map and test if each bounding box is colliding with each bounding box.
What I have in mind is having each entity knowing the tiles (32x32) its occupying, and also having a list for each tiles of every entity that's on.
So basically, what I'd do would be :
- for each tile my entity 1 is stepping on
- get the list of entities on that are on that tile too
- check if this entity intersect with entity 1

But I think it's kinda complicated (I need to update every list at each frame) and I think there already exist methods that are much better than mine.

Any ideas ? I'm doing this in C#

Share this post


Link to post
Share on other sites
voguemaster    183
hi,

I'd recommended doing reading on persistent sweep and prune, its the most efficient algorithm I have seen for AABB intersections, albeit it is mainly used as a broadphase only algorithm.

I've used it as the collision detection for a 2D vertical shooter and it works very well.

If you're a beginner in the field of collisions you may want to start with something simpler like using a grid. Divide your "world" to a grid with fixed size cells. Every frame you update an entity's position and you must update on which cell/s it is on.

Once you have that info you can easily test, within each cell, only those entities that reside inside the cell for collision.

If you need to test collisions with the environment, just have some dummy entities that don't get drawn but are only used as the collision proxy for the graphics.

Finally, a debugging tip - to be able to debug collisions its sometimes easier to see it with your eyes so drawing the boxes might help you gain insight on whats going on.

Share this post


Link to post
Share on other sites
fng    154
Hi lezebulon,

additionally it might be helpful to write automated tests for your collision detection, i.e. some test cases for which you know that it will collide or not. You then run these tests from time to time, to make sure that your collision detection works as expected. You can search for test driven development on how to do that best in C#.

Good luck!

Share this post


Link to post
Share on other sites
lezebulon    100
Quote:
Original post by voguemaster

If you're a beginner in the field of collisions you may want to start with something simpler like using a grid.


I've read a bit on SAP algorithm and I'm not sure why it'd be faster to compute than a fixed grid-based algorithm... can someone explains me why?

Share this post


Link to post
Share on other sites
voguemaster    183
Well, consider that for a grid you have to:

1. Once a box's position changes, update on which cells it resides.
2. Once the entire grid is updated, you test collisions for all boxes. Basically, boxes get tested against boxes that reside in the same cell. Overall you still always test for ALL boxes, but the number of pairs is less than O(n^2) of course.

In a SAP implementation:

1. Once a box's position changes, you automatically, because of the nature of the update, obtain pairs of intersection of that box with any other box. If a box's edge has changed position and this causes a new collision with another box, you know it on that instant and can add that pair (barring some optimizations).

2. Once the entire SAP is updated you have a set of pairs already, no need to do anything else.


In both cases you always update all boxes (for example) but in the SAP implementation, the update itself at the moment it is done determines if a collision with another box occurs at O(1).

In the grid case you just have to do more work - after updating the positions for the boxes, partition them to the proper cells or perform some other smart update and only then you can test collisions, which always amounts to testing ALL boxes.

In the SAP case, if a box's position has changed but its possible that nothing happens more than that and in that case, no other test need to be done.

Share this post


Link to post
Share on other sites
lezebulon    100
Ok thanks
But now I am wondering how flexible this solution is for more diverse collision tests.

For instance, let's say that from point (x,y) I fire a bullet in direction <v1,v2>
Is there any way, using SAP, to determine what object it will hit first (if any)? The solution I'd like to avoid would be to make a "moving" bullet box and check for collisions as it moves...

Share this post


Link to post
Share on other sites
Buckeye    10747
If your collision algorithm is relatively efficient, you could use a moving collision box.

If your bullet can be simulated with a ray, you could use ray-box intersection tests (intersecting with adjacent cells) for culling, followed by ray-shape intersection tests if a ray-box test determines a hit.

Share this post


Link to post
Share on other sites
voguemaster    183
Umm,

What do you want to avoid having the bullet's box move and then detect collisions ? It works really well.

In fact, if your SAP is anything like what Pierre Terdiman explains in his article, or what Bullet uses as a broadphase then you don't need a continuous collision detection algorithm even for fast moving projectiles.

The concept of updating a box's edge in the sorted array means that it isn't possible for a fast moving projectile to "pass through" other objects. The first time its edge exchanges places with a corresponding edge of another box, a collision pair is created and you know about the collision.

Now it all depends on how you record your collisions or if you allow this pair to be deleted if the projectile keeps moving in that same frame.

I know you can study Bullet's C++ implementation and it has a C# port. I wrote a Java port of the SAP algorithm, albeit with slight variations and a completely different pair manager BTW. It also doesn't use structs as the bullet implementation because I needed it to work well in J2ME and allocation of many objects is not a great thing during gameplay.

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