Fast 2D Collision Detection in XNA

As shown in the YouTube video in the post Fast collision detection in XNA, I made a quick way of doing near pixel perfect collision detection in XNA that does not get slowed down by rotating the object. This algorithm first checks the bounds of the object that scales based on the rotation of the content(as shown in Re-scaling a rectangle based on the rotation of it’s content), before checking for line intersection (see Determining if two lines intersect).

The whole idea is to generate lines around the object as this is much faster then checking pixel by pixel and can easily be rotated as they only consist of two points. This is done only once when first loading the image.

Tracing the outlining of the object using 5 segments

Tracing the outlining of the object using 5 segments


Once the outlining has been traced, we generate lines between them to give us the approximate outlining. In this case 5 segments has been used to better illustrate what is being done. The mesh we end up with should look something like this:

Generating lines between each outlining point

Generating lines between each outlining point

When we have these lines, it is then checked against each other if the bounding boxes should overlap. Based on the object, the number of points traced can be adjusted to suit your needs. The code includes functions for generating both the outlining and the inner grid (only one is needed). When the object is rotated, the lines are rotated around the object origin to stay concurrent. This recalculation is only needed if the bounding boxes overlap of course.

This solution works like a charm and is much faster than traditional pixel-perfect collision and can achieve nearly the same results by specifying more segments. It can be optimized however: Instead of tracing vertically and horizontally, the lines can be traced from the same outer points but towards the origin instead.

Tracing against the origin

Tracing against the origin

As always, feel free to use, modify and distribute this code in any project.

Source

XNA Collition Detection.zip

2 Comments

  • RedBlade says:

    This is a really great idea! Your tutorials that come along with this are amazingly easy to understand. Most tutorials always have too much, (and/or) too little information, and it becomes overburdening. Thank you for sharing this information.

  • Student of life says:

    Thank you so much for this. I have been trying to learn a better collision detecting algorithm.
    After I study your code so I can understand exactly what is going on, I need to find a way to apply it to spritesheet.

Leave a Reply

Your email address will not be published. Required fields are marked *