Collision is probably one of the firsts challenges a game developer face up. Today I'm gonna talk about the most common collision detection and response in 2D games with AABB techniques.
AABB stands for Axis Aligned Bounding Box. That means every entity in our game can be represented as rectangles or circles for a better collision detection. This shapes are Axis Aligned, so we don't take account the rotation of the entities for the computations.
In this interactive example you can test the different types of collisions between shapes. Click the buttons to change the yellow shape and move it around with the mouse. It will turn red when collide with any green shape. You can change between Box, Circle and Line.
The functions used to made this example are the same explained in this article.
This methods is most than enough for 2D games and a very useful practice for begginers. In case that you need add rotation in your game, search for OOBB (Object Oriented Bounding Box). The calculations will be a more complex compared to AABB.
Also you can use a physics engine like Box2D. Integrate it in your game engine and let it do all the work.
Let's begin with a simple collision example:
In this image, two entities A,B are colliding. How we detect that two rectangles overlap? Simple geometry.
struct Box
{
float x;
float y;
float width;
float height;
}
bool AABB_BoxBox(Box A, Box B, Box &intersect)
{
float Axmin = A.x;
float Axmax = A.x + A.width;
float Aymax = A.y + A.height;
float Aymin = A.y;
float Bxmin = B.x;
float Bxmax = B.x + B.width;
float Bymax = B.y + B.height;
float Bymin = B.y;
// Collision check
if(Axmax < Bxmin || Axmin > Bxmax ) return false;
if(Aymax < Bymin || Aymin > Bymax ) return false;
// Get the intersection rectangle
intersect.x = std::max(Axmin, Bxmin);
intersect.y = std::max(Aymin, Bymin);
intersect.witdh = std::min(Axmax, Bxmax) - intersect.x;
intersect.height = std::min(Aymax, Bymax) - intersect.y;
return true;
}
This function will return TRUE if the two Boxes are colliding and also give us the intersection rectangle as a result of the collision (red rectangle). This will be very useful for the next step.
Now we can detect if two boxes collide, but what is the appropiate response to that?
Move A? Move B? Move A,B apart? The solution varies depend on what kind of entities are colliding. For example let's say A is the Player and B is a rock (or any impassable terrain). We will move A back until no collision happen. But let's make things more interesting and move A and B apart in opposite directions.
const float M_PI_DIV_180 = 3.14159265359 / 180.f;
struct Point
{
float x;
float y;
}
// Returns the angle for A to go to B (0-360.f)
float Angle_PointToPoint(Point A, Point B)
{
float alfa = (( 114.59493f * (atan2( (B.y - A.y), (B.x - A.x) ))) * 0.5f);
// if we only want positive angles
if (alfa < 0) return 360 + alfa;
return alfa;
}
// Distance between two points D = sqr( (x2 - x1)^2 + (y2 - y1)^2 )
float Distance_PointPoint(Point A, Point B)
{
return sqrt( pow((B.x - A.x), 2) + pow((B.y - A.y), 2) );
}
For this collision response we will need a helper function to calculate the angle between the two Boxes center.
And another one to calculate the distance between two points.
...
Box A = Player.getHitbox();
Box B = Object.getHitbox();
Box intersect;
if (AABB_BoxBox(A, B, intersect))
{
// center points of each rectangle
Point PA = Point(A.x + A.width / 2, A.y + A.height / 2);
Point PB = Point(B.x + B.width / 2, B.y + B.height / 2);
// get the angle and convert to radians
float alfa = Angle_PointToPoint(PA, PB);
// the angle returned is A to B
// we need to move to the opposite direction, add 180 degrees
alfa += 180;
float rads = alfa * M_PI_DIV_180;
// Hypotenuse of intersect rect [c^2 = a^2 + b^2]
float force = sqrt(intersect.width*intersect.width +
intersect.height*intersect.height);
// if the object can't move -> move the player
if (!Object.isMovable())
{
Player.move(std::cos(rads) * force, std::sin(rads) * force);
}
// move the player and the object in opposite directions
else
{
// each entity move half the way in opposite directions
float dx = std::cos(rads) * force / 2;
float dy = std::sin(rads) * force / 2;
Player.move( dx, dy);
Object.move(-dx, -dy);
}
}
...
This way we can apply one collision response or another depending on the properties of the entities itself. The same logic would apply to walls, enemies... For bullets, when we detect the collision between a bullet and a wall -> destroy the bullet. If collide with an enemy -> apply damage to enemy and destroy bullet.
Detection is the easiest part of collision. Applying the proper response will depend on your game and what kind of behaviour want when two entities collide.
You can even complicate things even more adding acceleration, rebound, attraction, repulsion... Don't be afraid to add new features to your game, be sure to update your collision code if needed.
All this stuff is basically math. Geomatry and Trigonometry. There are a lot of blogs, forum posts, articles with this subject and collisions.
To end this article I will post a bunch of AABB collision functions between Boxes, Circles, Lines and Points.
I hope you will find them useful :)
struct Point
{
Point() { x = y = 0; }
Point(float px, float py) { x = px; y = py; }
Point operator+(const Point &A)
{
return Point(x + A.x, y + A.y);
}
Point operator-(const Point &A)
{
return Point(x - A.x, y - A.y);
}
Point operator*(float f) const
{
return Point(x * f, y * f);
}
float x;
float y;
};
struct Line
{
Line(float x1, float y1, float x2, float y2)
{
Ax = x1; Ay = y1;
Bx = x2; By = y2;
}
float Ax;
float Ay;
float Bx;
float By;
};
struct Box
{
float x;
float y;
float width;
float height;
};
struct Circle
{
// x,y are the center
float x;
float y;
float radius;
};
// Returns the distance between two Points
float Distance_PointPoint(Point A, Point B)
{
return sqrt(pow((B.x - A.x), 2) + pow((B.y - A.y), 2));
}
bool AABB_BoxBox(Box A, Box B)
{
float Axmin = A.x;
float Axmax = A.x + A.width;
float Aymax = A.y + A.height;
float Aymin = A.y;
float Bxmin = B.x;
float Bxmax = B.x + B.width;
float Bymax = B.y + B.height;
float Bymin = B.y;
if (Axmax < Bxmin || Axmin > Bxmax) return false;
if (Aymax < Bymin || Aymin > Bymax) return false;
return true;
}
bool AABB_BoxPoint(Box B, Point P)
{
return (P.x >= B.x) && (P.x < B.x + B.width) &&
(P.y >= B.y) && (P.y < B.y + B.height);
}
bool AABB_BoxCircle(Box B, Circle C)
{
float Dx = C.x - std::max(B.x, std::min(C.x, B.x + B.width));
float Dy = C.y - std::max(B.y, std::min(C.y, B.y + B.height));
return (Dx * Dx + Dy * Dy) < (C.radius * C.radius);
}
bool AABB_LineLine(Line A, Line B)
{
Point b = Point(A.Bx, A.By) - Point(A.Ax, A.Ay);
Point d = Point(B.Bx, B.By) - Point(B.Ax, B.Ay);
float DotDPerp = b.x * d.y - b.y * d.x;
// if DotdPerp == 0, it means the lines are parallel
if (DotDPerp == 0) return false;
Point c = Point(B.Ax, B.Ay) - Point(A.Ax, A.Ay);
float t = (c.x * d.y - c.y * d.x) / DotDPerp;
if (t < 0 || t > 1) return false;
float u = (c.x * b.y - c.y * b.x) / DotDPerp;
if (u < 0 || u > 1) return false;
return true;
}
bool AABB_BoxLine(Box B, Line L)
{
float Xmin, Xmax, Ymin, Ymax;
Xmin = B.x;
Xmax = B.x + B.width;
Ymin = B.y;
Ymax = B.y + B.height;
if (L.Ax < Xmin && L.Bx < Xmin) return false;
if (L.Ay < Ymin && L.By < Ymin) return false;
if (L.Ax > Xmax && L.Bx > Xmax) return false;
if (L.Ay > Ymax && L.By > Ymax) return false;
// check every side of the rectangle
if (AABB_LineLine(L, Line(Xmin, Ymin, Xmax, Ymin))) return true;
if (AABB_LineLine(L, Line(Xmin, Ymin, Xmin, Ymax))) return true;
if (AABB_LineLine(L, Line(Xmax, Ymin, Xmax, Ymax))) return true;
if (AABB_LineLine(L, Line(Xmin, Ymax, Xmax, Ymax))) return true;
return false;
}
bool AABB_CircleCircle(Circle A, Circle B)
{
float dx = B.x - A.x;
float dy = A.y - B.y;
float R = A.radius + B.radius;
return (dx*dx + dy*dy <= R*R);
}
bool AABB_CircleLine(Circle C, Line L)
{
// Circle centre point
Point P(C.x, C.y);
float APx = P.x - L.Ax;
float APy = P.y - L.Ay;
float ABx = L.Bx - L.Ax;
float ABy = L.By - L.Ay;
float magAB2 = ABx*ABx + ABy*ABy;
float ABdotAP = ABx*APx + ABy*APy;
float t = ABdotAP / magAB2;
// Closest point to the line L from Circle center
Point W;
if (t < 0) W = Point(L.Ax, L.Ay);
else if (t > 1) W = Point(L.Bx, L.By);
else W = Point(L.Ax + ABx * t, L.Ay + ABy * t);
float dist = Distance_PointPoint(P, W);
// if the distance is less than the circle radius
return dist < C.radius;
}
bool AABB_CirclePoint(Circle C, Point P)
{
float dx = std::abs(P.x - C.x);
float dy = std::abs(P.y - C.y);
float R = C.radius;
return (dx*dx + dy*dy <= R*R);
}
AVAILABLE ON STEAM