ProgrammingChips

In 2D games, collision detection between moving rectangles prevents them from passing through each other

1: Swept AABB

When implementing a 2D game yourself, if you use the AABB method for collision detection, you may encounter a problem where bullets pass through objects and are not detected as hits at high movement speeds. While this isn't usually a big deal, I looked into ways to write a solution. A simple solution is the "Swept AABB" method introduced on GameDev. This method is designed for horizontal and vertical legacy rectangles and does not support rotated rectangles, etc. The link to the GameDev article is
https://gamedev.net/tutorials/programming/general-and-gameplay-programming/swept-aabb-collision-detection-and-response-r3084/

The Swept AABB method detects collisions between a moving rectangle and a stationary rectangle, but I wrote a method that subtracts the movement speeds of two moving rectangles and treats one of them as if it were stationary.(C Language)

  
#include <algorithm>
#include <cmath>
#include <limits>

constexpr float EPSILON = 1e-6f;

struct Vec2 {
    float x;
    float y;
};

struct AABB {
    float x;
    float y;
    float w;
    float h;
    float vx; // Movement amount per frame
    float vy; // Movement amount per frame
};

/////////////////////////////////////////////////////////////////////////
// AABB function
bool AABBvsAABB(const AABB& a, const AABB& b) {
    return !(a.x + a.w <= b.x ||
             a.x >= b.x + b.w ||
             a.y + a.h <= b.y ||
             a.y >= b.y + b.h);
}

/////////////////////////////////////////////////////////////////////////
// SweptAABB
bool SweptAABB(
    const AABB& a,
    const AABB& b,
    float& outTime,
    Vec2& outNormal
) {
    //Already overlapping
    if (AABBvsAABB(a, b)) {
        outTime = 0.0f;
        outNormal = {0.0f, 0.0f};
        return true;
    }

    //Relative movement (1 frame)
    float vx = a.vx - b.vx;
    float vy = a.vy - b.vy;

    float xEntry, yEntry;
    float xExit,  yExit;

    //X
    if (std::fabs(vx) < EPSILON) {
        xEntry = -std::numeric_limits<float>::infinity();
        xExit  =  std::numeric_limits<float>::infinity();
    } else if (vx > 0.0f) {
        xEntry = (b.x - (a.x + a.w)) / vx;
        xExit  = ((b.x + b.w) - a.x) / vx;
    } else {
        xEntry = ((b.x + b.w) - a.x) / vx;
        xExit  = (b.x - (a.x + a.w)) / vx;
    }

    //Y
    if (std::fabs(vy) < EPSILON) {
        yEntry = -std::numeric_limits<float>::infinity();
        yExit  =  std::numeric_limits<float>::infinity();
    } else if (vy > 0.0f) {
        yEntry = (b.y - (a.y + a.h)) / vy;
        yExit  = ((b.y + b.h) - a.y) / vy;
    } else {
        yEntry = ((b.y + b.h) - a.y) / vy;
        yExit  = (b.y - (a.y + a.h)) / vy;
    }



	float entryTime, exitTime;

	if (xEntry > yEntry)
	{
		entryTime = xEntry;
	}
	else {
		entryTime = yEntry;
	}
	if (yExit > xExit)
	{
		exitTime = xExit;
	}
	else {
		exitTime = yExit;
	}


    //Collision detection (within frame only)
    if (entryTime > exitTime ||
        entryTime < 0.0f ||
        entryTime > 1.0f) {
        return false;
    }

    //Normal (Stable)
    if (xEntry > yEntry) {
        outNormal.x = (vx < 0.0f) ? 1.0f : -1.0f;
        outNormal.y = 0.0f;
    } else {
        outNormal.x = 0.0f;
        outNormal.y = (vy < 0.0f) ? 1.0f : -1.0f;
    }

    outTime = entryTime;
    return true;
}

///////////////////////////////////////////////
//Usage examples

float t;
Vec2 normal;
AABB a, b;
a.x = 0;
a.y = 0;
a.w = 100;
a.h = 100;
a.vx = 30;
a.vy = 0;
b.x = 100;
b.y = 0;
b.w = 100;
b.h = 100;
b.vx = 40;
b.vy = 0;

if (SweptAABB(a, b, t, normal)) {
    // Move to just before the collision
    a.x += a.vx * t;
    a.y += a.vy * t;

    // Stop normal movement
    if (normal.x != 0) a.vx = 0;
    if (normal.y != 0) a.vy = 0;
} else {
    // If nothing hits, move fully
    a.x += a.vx;
    a.y += a.vy;
}

  
  

2: M3 Method

This is a coding method that a Japanese IT person introduced on YouTube. The code in the video is in JavaScript, so it may be a little difficult even for Japanese people. The URL for the video is https://www.youtube.com/watch?v=FkD-intv7IE
This method combines the widths of two rectangles to determine a single rectangle and point, and considers the movement of the rectangle as a hexagon. Mathematical transformations are used to simplify the formula.
The content seems to be a type of SweptAABB, which removes division from the calculation.
Porting from JavaScript was difficult, so I will skip it here.