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.

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!

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.

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.

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.