This article describes how to detect the collision between two moving (2D) polygons. It’s not the first tutorial on the topic, however, the tutorials on the net tend to be a bit too complex for a relatively simple problem. The source codes I could find also had too many abbreviations that I don’t get, or were crippled with C optimizations. So here, I’ll try to keep it as simple as possible. In any case, it should be possible to include the functions presented here to your C# projects quite straightforwardly. The technique can be used to detect collisions between sprites as an alternative to pixel-perfect collisions which are usually too slow.

• Download the .NET / C# source code
• Download the .NET demo

Background

To detect if two polygons are intersecting, we use the Separating Axis Theorem. The idea is to find a line that separates both polygons – if such a line exists, the polygons are not intersecting (Fig. 1). The implementation of this theorem is relatively simple, and could be summed up in this pseudo code:

• For each edge of both polygons:
  • Find the axis perpendicular to the current edge.
  • Project both polygons on that axis.
  • If these projections don't overlap, the polygons don't intersect (exit the loop).

This can be easily extended to deal with moving polygons by adding one additional step. After having checked that the current projections do not overlap, project the relative velocity of the polygons on the axis. Extend the projection of the first polygon by adding to it the velocity projection (Fig. 2). This will give you the interval spanned by the polygon over the duration of the motion. From there, you can use the technique used for static polygons: if the projections of polygons A and B don’t overlap, the polygons won’t collide. (NB: However, remember that if the intervals do overlap, it doesn’t necessarily mean that the polygons will collide. We need to do the test for all the edges before knowing that.)

Once we have found that the polygons are going to collide, we calculate the translation needed to push the polygons apart. The axis on which the projection overlapping is minimum will be the one on which the collision will take place. We will push the first polygon along this axis. Then, the amount of translation will simply be the amount of overlapping on this axis (Fig. 3).

That is it! Now, each time a collision occurs, the first polygon will nicely slide along the surface of the other polygon.

Figure 1: Projections of the polygons onto an axis.

Figure 2: Projections for moving polygons.

Figure 3: Find the minimum interval overlapping, then calculate the translation required to push the polygons apart.

Using the code

The PolygonCollision() function does all of the above, and returns a PolygonCollisionResult structure containing all the necessary information to handle the collision:

// Structure that stores the results of the PolygonCollision function

public struct PolygonCollisionResult {
    // Are the polygons going to intersect forward in time?

    public bool WillIntersect;
    // Are the polygons currently intersecting?

    public bool Intersect;
    // The translation to apply to the first polygon to push the polygons apart.

    public Vector MinimumTranslationVector;
}

Two helper functions are used by the PolygonCollision function. The first one is used to project a polygon onto an axis:

// Calculate the projection of a polygon on an axis

// and returns it as a [min, max] interval

public void ProjectPolygon(Vector axis, Polygon polygon,
                           ref float min, ref float max) {
    // To project a point on an axis use the dot product

    float dotProduct = axis.DotProduct(polygon.Points[0]);
    min = dotProduct;
    max = dotProduct;
    for (int i = 0; i < polygon.Points.Count; i++) {
        dotProduct = polygon.Points[i].DotProduct(axis);
        if (d < min) {
            min = dotProduct;
        } else {
            if (dotProduct> max) {
                max = dotProduct;
            }
        }
    }
}

The second one returns the signed distance between two given projections:

// Calculate the distance between [minA, maxA] and [minB, maxB]

// The distance will be negative if the intervals overlap

public float IntervalDistance(float minA, float maxA, float minB, float maxB) {
    if (minA < minB) {
        return minB - maxA;
    } else {
        return minA - maxB;
    }
}

Finally, here is the main function:

// Check if polygon A is going to collide with polygon B.

// The last parameter is the *relative* velocity 

// of the polygons (i.e. velocityA - velocityB)

public PolygonCollisionResult PolygonCollision(Polygon polygonA,
                              Polygon polygonB, Vector velocity) {
    PolygonCollisionResult result = new PolygonCollisionResult();
    result.Intersect = true;
    result.WillIntersect = true;

    int edgeCountA = polygonA.Edges.Count;
    int edgeCountB = polygonB.Edges.Count;
    float minIntervalDistance = float.PositiveInfinity;
    Vector translationAxis = new Vector();
    Vector edge;

    // Loop through all the edges of both polygons

    for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
        if (edgeIndex < edgeCountA) {
            edge = polygonA.Edges[edgeIndex];
        } else {
            edge = polygonB.Edges[edgeIndex - edgeCountA];
        }

        // ===== 1. Find if the polygons are currently intersecting =====

        // Find the axis perpendicular to the current edge

        Vector axis = new Vector(-edge.Y, edge.X);
        axis.Normalize();

        // Find the projection of the polygon on the current axis

        float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;
        ProjectPolygon(axis, polygonA, ref minA, ref maxA);
        ProjectPolygon(axis, polygonB, ref minB, ref maxB);

        // Check if the polygon projections are currentlty intersecting

        if (IntervalDistance(minA, maxA, minB, maxB) > 0)\
            result.Intersect = false;

        // ===== 2. Now find if the polygons *will* intersect =====

        // Project the velocity on the current axis

        float velocityProjection = axis.DotProduct(velocity);

        // Get the projection of polygon A during the movement

        if (velocityProjection < 0) {
            minA += velocityProjection;
        } else {
            maxA += velocityProjection;
        }

        // Do the same test as above for the new projection

        float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
        if (intervalDistance > 0) result.WillIntersect = false;

        // If the polygons are not intersecting and won't intersect, exit the loop

        if (!result.Intersect && !result.WillIntersect) break;

        // Check if the current interval distance is the minimum one. If so store

        // the interval distance and the current distance.

        // This will be used to calculate the minimum translation vector

        intervalDistance = Math.Abs(intervalDistance);
        if (intervalDistance < minIntervalDistance) {
            minIntervalDistance = intervalDistance;
            translationAxis = axis;

            Vector d = polygonA.Center - polygonB.Center;
            if (d.DotProduct(translationAxis) < 0)
                translationAxis = -translationAxis;
        }
    }

    // The minimum translation vector

    // can be used to push the polygons appart.

    if (result.WillIntersect)
        result.MinimumTranslationVector =
               translationAxis * minIntervalDistance;

    return result;
}

The function can be used this way:

Vector polygonATranslation = new Vector();

PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity);

if (r.WillIntersect) {
  // Move the polygon by its velocity, then move

  // the polygons appart using the Minimum Translation Vector

  polygonATranslation = velocity + r.MinimumTranslationVector;
} else {
  // Just move the polygon by its velocity

  polygonATranslation = velocity;
}

polygonA.Offset(polygonATranslation);

Reference

• GPWiki – Polygon Collision
• Olivier’s code junkyard

Ray casting is a technique widely used in 3D environments. It consists in casting a “ray” from a given position in a given direction. The algorithm will then tell you things like where a collision happened, what was the normal of the surface, etc. In this article, I will describe a way of implementing a similar technique in a 2D tile-based environment. Implementing this technique in your game engine can give you benefits like pixel-perfect collision detection.

Download the .NET / C# source code

Download the .NET demo

For this article, I won’t go into the details for loading or drawing a 2D scene. I will focus on the 2D ray casting technique. All the code described here can be found in the Scene and Tile classes.

The Tile class

To implement this technique, our Tile class will need to have two main properties: Bitmap and SolidityMap. The Bitmap property simply contains the graphic representation of the tile. The SolidityMap property is a 2D array which will tell us which part of the tile is solid and which is not. This array can be built from the bitmap using the alpha value of each pixel – if the pixel is transparent, it can be crossed, otherwise it’s solid (Fig. 1).

Figure 1: Tile bitmap and solidity map.

public class Tile {

    private Bitmap bitmap;
    private bool[,] solidityMap;

    public void BuildSolidityMap() {
        solidityMap = new bool;

        for (int x = 0; x < bitmap.Width; x++) {
            for (int y = 0; y < bitmap.Height; y++) {
                // if the pixel is not transparent set
                // the solidity map value to "true"

                solidityMap[x, y] = bitmap.GetPixel(x, y).A != 0;
            }
        }

        // We will need some additionnal processing here if the tile is
        // transformed in some way
        // (like horizontally or vertically flipped)
        // This code is in Tile.cs

    }

    public bool[,] SolidityMap {
        get { return solidityMap; }
    }

    public Bitmap Bitmap {
        get { return bitmap; }
        set { bitmap = value; }
    }

}

Checking if a pixel can be crossed or not

Before doing any ray casting, we need to be able to find out if a given pixel of the scene can be crossed by a ray. I won’t go into the details as it is now quite obvious how to implement it using our SolidityMap property:

// Find out if the given pixel is traversable.

// X and Y are the scene pixel coordinates

public bool IsPointTraversable(int x, int y) {
    // Get the tile coordinates from the pixel coord.

    int tileX = (int)Math.Floor((float)x / (float)tileSize);
    int tileY = (int)Math.Floor((float)y / (float)tileSize);

    // If the point is out of bound, we assume it's traversable

    if (tileX < 0) return true;
    if (tileX >= horizontalTileCount) return true;
    if (tileY < 0) return true;
    if (tileY >= verticalTileCount) return true;

    Tile tile = GetTile(tileX, tileY);

    // If the tile is blank the point is traversable

    if (tile == null) return true;

    // Get the coordinates of the point within the tile

    int localPointX = x % tileSize;
    int localPointY = y % tileSize;

    // Return "true" if the pixel is not solid

    return !tile.SolidityMap[localPointX, localPointY];
}

Casting a ray using the Bresenham algorithm

The core of our ray casting functions will be the good old Bresenham algorithm, which after 44 years is still the fastest way to plot a (non-antialiased) line from A to B. There are plenty of resources on the net to implement it. Here I’ve chosen to implement the optimized version described on Wikipedia. The function takes two points as input, and will return the list of all the points crossed by that line. This function is not completely optimized – it would be better to calculate in advance the number of points the line will contain so that we can use a fixed-size array instead of a list. It should improve the speed quite significantly, especially for the longer lines. Anyway, here is the function:

// Swap the values of A and B

private void Swap<T>(ref T a, ref T b) {
    T c = a;
    a = b;
    b = c;
}

// Returns the list of points from p0 to p1 

private List<Point> BresenhamLine(Point p0, Point p1) {
    return BresenhamLine(p0.X, p0.Y, p1.X, p1.Y);
}

// Returns the list of points from (x0, y0) to (x1, y1)

private List<Point> BresenhamLine(int x0, int y0, int x1, int y1) {
    // Optimization: it would be preferable to calculate in

    // advance the size of "result" and to use a fixed-size array

    // instead of a list.

    List<Point> result = new List<Point>();

    bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
    if (steep) {
        Swap(ref x0, ref y0);
        Swap(ref x1, ref y1);
    }
    if (x0 > x1) {
        Swap(ref x0, ref x1);
        Swap(ref y0, ref y1);
    }

    int deltax = x1 - x0;
    int deltay = Math.Abs(y1 - y0);
    int error = 0;
    int ystep;
    int y = y0;
    if (y0 < y1) ystep = 1; else ystep = -1;
    for (int x = x0; x <= x1; x++) {
        if (steep) result.Add(new Point(y, x));
        else result.Add(new Point(x, y));
        error += deltay;
        if (2 * error >= deltax) {
            y += ystep;
            error -= deltax;
        }
    }

    return result;
}

Finally, the actual ray casting function

The RayCast() function will perform the ray casting. The ray will be cast from a given Position in a given Direction, and with the specified RayLength (Fig. 2), and will return a RayCastingResult class to allow us to handle the collision in the game.

Figure 2: Position, Direction, and RayLength parameters

// Class returned by the RayCast() method

public class RayCastingResult {
    // Does the ray collide with the environment?

    private bool doCollide;
    // And if so, at which position?

    private Vector position;

    public bool DoCollide {
        get { return doCollide; }
        set { doCollide = value; }
    }

    public Vector Position {
        get { return position; }
        set { position = value; }
    }
}

In the RayCast() method, we will start by retrieving the list of all the points crossed by the ray using the Bresenham algorithm:

List<Point> rayLine = BresenhamLine(position,
      position + (direction.GetNormalized() * rayLength));

Then, we will loop through all these points, starting from the specified position, for the whole length of the ray or until we find the collision point. Once we find that point, we exit the loop and return the RayCastingResult instance.

while (true) {
    Point rayPoint = rayLine[rayPointIndex];
    if (!IsPointTraversable(rayPoint.X, rayPoint.Y)) {
        result.Position = Vector.FromPoint(rayPoint);
        result.DoCollide = true;
        break;
    }

For more details, here is the full RayCast() method:

public RayCastingResult RayCast(Vector position,
       Vector direction, float rayLength) {
    RayCastingResult result = new RayCastingResult();
    result.DoCollide = false;

    // Exit the function now if the ray length is 0

    if (rayLength == 0) {
        result.DoCollide = IsPointTraversable((int)position.X,
                                              (int)position.Y);
        result.Position = position;

        return result;
    }

    // Get the list of points from the Bresenham algorithm

    List<Point> rayLine = BresenhamLine(position,
       position + (direction.GetNormalized() * rayLength));

    if (rayLine.Count > 0) {
        int rayPointIndex = 0;

        if (rayLine[0] != position) rayPointIndex = rayLine.Count - 1;

        // Loop through all the points starting from "position"

        while (true) {
            Point rayPoint = rayLine[rayPointIndex];
            if (!IsPointTraversable(rayPoint.X, rayPoint.Y)) {
                result.Position = Vector.FromPoint(rayPoint);
                result.DoCollide = true;
                break;
            }
            if (rayLine[0] != position) {
                rayPointIndex--;
                if (rayPointIndex < 0) break;
            } else {
                rayPointIndex++;
                if (rayPointIndex >= rayLine.Count) break;
            }
        }
    }

    return result;
}

Performance

Doing this kind of pixel-perfect ray casting might seem a bit over kill, however, I found it’s usable and fast in a game environment when used reasonably. The most important is to use the ray length parameter properly, and to set it to the minimum possible value. For instance, if over a frame, a bullet is moving from A to B, don’t cast a ray through the whole scene, but instead limit the length of the ray to |B-A|.

In most cases, the ray is going to cross several empty tiles (which translates to many quick tile == null tests). Once we find a non-empty tile, in the worst case, we will have 23 values to test in the SolidityMap array (for 16×16 pixel tiles). The only case when it might be a problem is when trying to cast a long ray in a scene with tiles with many holes (Fig. 3). But again, setting the ray length to a proper value should get rid of the problem.

Figure 3: Worst case scenario. None of the tiles crossed by the ray is empty, and they all have a big hole in the middle.