2D Collision Detection

Introduction[edit]

When it comes to making games in two-dimensional space you may find yourself limited by what you can create given the built-in API. This article aims to go over a few different methods for 2D collision detection.

Prerequisites

Since this article has more than one method there are different prerequisites depending on the way you intend to approach the problem of collision detection. For the first method you will need a basic understanding of how GUI elements are positioned and their properties. The second method will require knowledge of the dot product and how to rotate vectors/points in 2D (rotation is covered in this article).

Method 1: Axis aligned shapes[edit]

An “Axis-aligned shape” is a non-rotated shape. In other words, its edges are parallel to the standard x and y axes. This means that this form of collision detection only works for GUI elements that have their rotation property set to zero.

Creating our algorithm

The goal of this method of collision is to see if the extents of each shape overlap each other.

Collision1.png

What set of rules can we come up with to check if the shape 1 and shape 2 overlap?

  1. If the x-value of the top-left corner of the first shape is less than the x-value of the top-right corner of the second shape.
  2. If the x-value of the top-right corner of the first shape is greater than the x-value of the top-left corner of the second shape.
  3. If the y-value of the top-left corner of the first shape is less than the y-value of the bottom-left corner of the second shape.
  4. If the y-value of the bottom-left corner of the first shape is greater than the y-value of the top-left corner of the second shape.

Note: The XY grid that these 2D GUIs use is different from the coordinates the rest of ROBLOX uses. The (0, 0) position is in the upper left corner of a GUI element. In this grid right is positive in the X direction and down is positive in the Y direction.

It is encouraged that you use the above picture along with the rules (and potentially your fingers!) to draw out why this works.

Writing our code

Alright, so we have the theory behind this simple collision method. How do we translate it over to code? Well doing the test is pretty simple once we have the corners, so how do we get the corners?

In this tutorial we will be using the AbsolutePosition and AbsoluteSize properties as they take our GUI’s size and position and convert it entirely into pixels. We can’t use a combination of scale and offset as they are two different units and therefore cannot be compared.

With this in mind we know that for any given axis-aligned GUI we can get the corners with a function such as:

function getCorners(gui)
	local topLeft = gui.AbsolutePosition;
	local size = gui.AbsoluteSize;
 
	local corners = {
		topLeft = topLeft;
		topRight = topLeft + Vector2.new(size.x, 0);
		bottomRight = topLeft + Vector2.new(size.x, size.y);
		bottomLeft = topLeft + Vector2.new(0, size.y);
	};
 
	return corners;
end;


So with our understanding of how we get corners we now apply our two tests and hooray! We have a simple function for testing collision on axis-aligned shapes:

function collides(gui1, gui2)
	local g1p, g1s = gui1.AbsolutePosition, gui1.AbsoluteSize;
	local g2p, g2s = gui2.AbsolutePosition, gui2.AbsoluteSize;
	return ((g1p.x < g2p.x + g2s.x and g1p.x + g1s.x > g2p.x) and (g1p.y < g2p.y + g2s.y and g1p.y + g1s.y > g2p.y));
end;
 
-- Example in use:
 
local f1 = script.Parent:WaitForChild("Frame1");
local f2 = script.Parent:WaitForChild("Frame2");
 
game:GetService("RunService").RenderStepped:connect(function()
	local doesCollide = collides(f1, f2);
	f1.BorderColor3 = doesCollide and Color3.new(1, 0, 0) or Color3.new(0, 1, 0);
	f2.BorderColor3 = doesCollide and Color3.new(1, 0, 0) or Color3.new(0, 1, 0);
end);


Collision3.gif

Note: This method of collision does not account for negative sized GUI

Taking the next steps: Minimum translation vector

If we wanted to have our script automatically reposition the shapes then we would be looking for the minimum amount that we would have to move our shapes to have them no longer collide. This amount is called the minimum translation vector (MTV) and it's pretty useful!

Calculating it for axis-aligned shapes is a pretty straight-forward logically. We simply want to look at each edge of shape1, get the distance between that edge and shape2's opposite edge, and then out of all those comparisons we want to find the smallest distance and move our shape.

function collidesMTV(gui1, gui2)
	local g1p, g1s = gui1.AbsolutePosition, gui1.AbsoluteSize;
	local g2p, g2s = gui2.AbsolutePosition, gui2.AbsoluteSize;
	-- check for collision first
	local doesCollide, mtv = ((g1p.x < g2p.x + g2s.x and g1p.x + g1s.x > g2p.x) and (g1p.y < g2p.y + g2s.y and g1p.y + g1s.y > g2p.y));
	-- since we know they collide, find mtv
	if doesCollide then
		-- find distances between shape1's edge and shape2's opposite edge
		local edgeDifferences = {
			Vector2.new(g1p.x - (g2p.x + g2s.x), 0); -- left
			Vector2.new((g1p.x + g1s.x) - g2p.x, 0); -- right
			Vector2.new(0, g1p.y - (g2p.y + g2s.y)); -- top
			Vector2.new(0, (g1p.y + g1s.y) - g2p.y); -- bottom
		};
		-- get the smallest difference
		table.sort(edgeDifferences, function(a, b) return a.magnitude < b.magnitude; end);
		mtv = edgeDifferences[1];
	end;
	-- provide collision boolean and mtv
	return doesCollide, mtv or Vector2.new();
end;
 
-- example
 
local f1 = script.Parent:WaitForChild("Frame1");
local f2 = script.Parent:WaitForChild("Frame2");
 
game:GetService("RunService").RenderStepped:connect(function()
	local doesCollide, mtv = collidesMTV(f2, f1);
	if doesCollide then
		f1.Position = f1.Position + UDim2.new(0, mtv.x, 0, mtv.y);
	end;
end);


Collision4.gif


Prerequisites to Method 2: Corners of a rotated shape[edit]

Right, so this is where things get a bit more complicated. In the previous method we were only able to detect collision when the shapes were not rotated. With the next method we will be able to detect collision between rotated shapes, but only if we have their rotated corners!

Understanding the math

There are a few problems/things we have to consider when getting the corners of a shape:

  1. The size and position of a GUI object remain the same regardless of the rotation of a shape. This means the shape still positions itself from the top-left corner as if no-rotation was applied. Similarly the position properties of the shape will provide a non-rotated value.
  2. When a shape is rotated it does so via the center of the shape. This means we have an origin of rotation.

Luckily for us there is a way to rotate a vector around the origin. It is a little difficult to get your head around, but with basic trigonometry and a pen and paper you will get it in no time! Let’s check an example:

Colllision5.png

Let’s say I wanted to rotate point P by R degrees. The key to performing this rotation is to visualize the point staying still, the axis rotating, and then finding where the point’s x and y values lie along the new rotated axis:

Collision6.png

Let’s go over the steps with the visual aid:

Remember SOHCAHTOA We can use this for right angle triangles to solve for either a missing angle or length as long as we have at least two pieces of information.

We know that the new x-value (Xb) on our rotated axis is just the summation of length A to B (AB) + length B to Xb (BXb). We also know that length B to Xb is the same length as Xa to D (XaD).

Similarly we know that the new y-value (Yb) on our rotated axis is just the length of A to F (AF) - length Yb to F (YbF). We also know that length Yb to F is the same length as G to Ya (GYa).

With this in mind we can use some basic trigonometry to solve for Xb and Yb:


Collision23.png


Alright, now we have to find a way to apply this new found knowledge to GUI. The first problem we have is that the equation we just derived is limited to rotating around an origin point of (0, 0). This isn’t a huge problem but we need to think about our information in its current form.

If we got the corners like we did in method one and directly applied our rotation to them then we’d be rotating the shape around the entire 2D plane (almost like the hand on a clock). Rather what we want to do is get our corners relative to the origin of (0, 0) with some simple subtraction so that it acts as the center of our shape:

Collision7.png Collision8.png

Then once we’ve rotated those adjusted corners we do some addition to get the points relative to the real center of the shape again.

One final important thing to remember is that positive x and y values in vector2 reference a point in the top right quadrant. Positive x and y values for UDim2 positions on the other hand references points in the bottom right quadrant. Because we are rotating vector2 values we might think that we want to rotate clockwise. However, because we are translating those points into UDim2 we actually want to rotate counter-clockwise to get the proper UDim2 values.

Writing our code

Right so now that we understand what we have to do to get our rotated shape let’s put it into a one size fits all function:

function getCorners(frame)
	local corners, rot = {}, math.rad(frame.Rotation); -- we use radians
	local center = frame.AbsolutePosition + frame.AbsoluteSize/2; -- where the center is
	-- where the corners would be with no rotation  
	local world_cords = {
		Vector2.new(frame.AbsolutePosition.x, frame.AbsolutePosition.y); -- top left
		Vector2.new(frame.AbsolutePosition.x + frame.AbsoluteSize.x, frame.AbsolutePosition.y); -- top right
		Vector2.new(frame.AbsolutePosition.x + frame.AbsoluteSize.x, frame.AbsolutePosition.y + frame.AbsoluteSize.y); -- bottom right
		Vector2.new(frame.AbsolutePosition.x, frame.AbsolutePosition.y + frame.AbsoluteSize.y); -- bottom left
	};
	-- calculate with rotation
	for i, corner in ipairs(world_cords) do
		-- using our rotation method on corners made relative to origin and then added back to the original center
		local x = center.x + (corner.x - center.x) * math.cos(rot) - (corner.y - center.y) * math.sin(rot);
		local y = center.y + (corner.x - center.x) * math.sin(rot) + (corner.y - center.y) * math.cos(rot);
		corners[i] = Vector2.new(x, y);
	end;
	return corners;
end;


We can do a simple test. See if the corners are accurate on a transparent rotating shape:

Collision9.gif

Awesome we can get the rotated corners of our shapes!

Method 2: Separating axis theorem (SAT)[edit]

Now that we have a way to get the corners of a shape we can approach some more advanced methods for 2D collision.

Separating axis theorem is a method that can check if two convex polygons are intersecting. A convex polygon is simply any shape that you can draw any line through and it will only cross the shape twice. For our sake we are only using rectangles, which are convex shapes.

Understanding the math

The idea behind SAT is that if you can draw a line between the two shapes then there isn’t collision.

Collision10.png

The premise is simple enough that anyone can do it pretty easily by hand, but how do we translate this over to something we can test mathematically? The answer is to project our corners onto all unique surface normals of our two shapes.

Collision11.png

If we know where the blue lines and red lines lie along pinkish-purple line, then we just have to see if those points overlap with each other. If they don’t we know there’s no intersection. If they do then we have to check the other axes.

In other words, if I had my shapes in a dark room and walked around them would I ever see a gap in their shadows on the opposite side of the room’s wall? If yes then the shapes aren’t colliding. Otherwise they are:

Gaps (no collision):

Collision12.gif

No gaps (collision):

Collision13.gif

Now obviously in the above example we’re looking at the shadows cast from every angle around the two shapes. Not only is that inefficient, it’s also unnecessary. As mentioned above we only need to cast shadows on the unique surface normals of our shapes.

Writing the code

First off, what is a normal? A normal is a unit vector that is perpendicular to the surface (as shown in purple):

Collision14.png

How do we get a perpendicular vector? Quite easily, just swap the x and y value and multiply one of the values by negative one. So for example, say we have Vector2.new(0, 1) and we want a perpendicular vector2. Simply swap x and y leaving us with Vector2.new(1, 0) and then multiply x or y by -1 giving us either Vector2.new(-1, 0) or Vector2.new(1, 0). So in function form:

function getPerpendicular(vec)
    return Vector2.new(vec.y, -vec.x).unit;
end;


Right, so now that we understand this, how do we actually get the unique surface normals of our shape? Well, it’s pretty easy since we have the corners of our shape. Simply subtract two connected corners and get the perpendicular unit vector. Also keep in mind that we only need the unique axis, meaning that we do not need the negative version of the same surface normal. This is particularly relevant for rectangles since each edge has an opposite with exact opposite surface normal, we do not need this. As such our code is as follows:

function getAxis(shape1Corners, shape2Corners)
    local axis = {};
    axis[1] = getPerpendicular(shape1Corners[1] - shape1Corners[2]);
    axis[2] = getPerpendicular(shape1Corners[1] - shape1Corners[4]);
    axis[3] = getPerpendicular(shape2Corners[1] - shape2Corners[2]);
    axis[4] = getPerpendicular(shape2Corners[1] - shape2Corners[4]);
    return axis;
end;


We can simplify this even more since we are using rectangles. Since the edge vectors in unit form of the top and bottom of the shape are the same as the surface normals of the left and right edges and vice versa we can get rid of the getPerpendicular function entirely:

Collision15.png

Notice the blue arrows travel in the same direction as the purple ones, so we simply subtract and then normalize:

function getAxis(shape1Corners, shape2Corners)
    local axis = {};
    -- it doesn't matter if the vector's x and y values are positive or negative (just no repeats via opposite vectors)
    axis[1] = (shape1Corners[2] - shape1Corners[1]).unit;
    axis[2] = (shape1Corners[2] - shape1Corners[3]).unit;
    axis[3] = (shape2Corners[2] - shape2Corners[1]).unit;
    axis[4] = (shape2Corners[2] - shape2Corners[3]).unit;
    return axis;
end;


One more thing we need to cover regarding axis! Later on if we want to calculate the minimum translation vector we're going to need to do some vector math involving the axis. As such it is important that we don't pick our axis arbitrarily. For this article we will be picking our axis so that they always go from corner1 to the connected corners:

function getAxis(c1, c2)
	local axis = {};
	axis[1] = (c1[2] - c1[1]).unit;
	axis[2] = (c1[4] - c1[1]).unit;
	axis[3] = (c2[2] - c2[1]).unit;
	axis[4] = (c2[4] - c2[1]).unit;
	return axis;
end;


Awesome! Now that the axes are out of the way it’s time to focus on projections. For review please read vector projections here.

So in in order to get the corners projected onto our axis we simply loop through and project with the dot product. One thing we have to be careful of, is to keep this value in scalar form. If we were to convert this into a vector then our only measure of length would be magnitude, but magnitude is always positive and that means we lose valuable information when checking if these values overlap.

Once we have all the scalars, we then need to see if there’s overlap. Recall this picture:

Collision11.png

So we want to get the largest and smallest scalars of each of our shape (since together they represent the end points of the shape's "shadow") and then see if they overlap. If there are any gaps we instantly know the shapes do not collide. However, if there are no gaps and we’ve checked the overlapping scalars on all axis then we know the two shapes are colliding!

function dot2d(a, b)
    -- dot product for vector2
    return a.x * b.x + a.y * b.y;
end;
 
function collide(shape1, shape2)
    local c1, c2 = getCorners(shape1), getCorners(shape2); -- corners
    local axis = getAxis(c1, c2); -- axis
    local scalars = {};
    for i = 1, #axis do -- iterate every axis
        for i2, set in pairs({c1, c2}) do
            scalars[i2] = {}; -- empty the prior axis scalars if they exist
            for _, point in pairs(set) do
                -- project corner onto axis, store in table to distinguish 2 shapes
                table.insert(scalars[i2], dot2d(point, axis[i]));
            end;
        end;
        -- get the largest and smallest projected scalars of each shape
        local s1max, s1min = math.max(unpack(scalars[1])), math.min(unpack(scalars[1]));
        local s2max, s2min = math.max(unpack(scalars[2])), math.min(unpack(scalars[2]));
        -- if they don't overlap then no collision!
        if s2min > s1max or s2max < s1min then
            return false;
        end;
    end;
    -- finished checking all axis, there was always overlap so they must collide
    return true;
end;
 
-- example
 
local f1 = script.Parent:WaitForChild("Frame1");
local f2 = script.Parent:WaitForChild("Frame2");
 
game:GetService("RunService").RenderStepped:connect(function()
	f1.Rotation = f1.Rotation + 1;
	f2.Rotation = f2.Rotation - 1;
	local doesCollide = collide(f1, f2);
	f1.BorderColor3 = doesCollide and Color3.new(1, 0, 0) or Color3.new(0, 1, 0);
	f2.BorderColor3 = doesCollide and Color3.new(1, 0, 0) or Color3.new(0, 1, 0);
end);


Fantastic! We now have a method for checking if rotated shapes collide:

Collision16.gif

Taking the next steps: Minimum translation vector

Once again, we may want our shapes to automatically readjust their position if there is collision. We can also calculate the MTV with SAT collisions. The process is actually even easier than axis-aligned shapes because we have most of the information already.

All we need to do is find the minimum overlap distance and then apply it to our axis (make sure to account for proper direction). It's as simple as that:

function collide(shape1, shape2)
	local c1, c2 = getCorners(shape1), getCorners(shape2);
	local axis = getAxis(c1, c2);
	local scalars, mtv = {}, Vector2.new(math.huge, math.huge); -- huge magnitude
	local a = nil;
	for i = 1, #axis do
		for i2, set in pairs({c1, c2}) do
			scalars[i2] = {};
			for _, point in pairs(set) do
				table.insert(scalars[i2], dot2d(point, axis[i]));
			end;
		end;
		local s1max, s1min = math.max(unpack(scalars[1])), math.min(unpack(scalars[1]));
		local s2max, s2min = math.max(unpack(scalars[2])), math.min(unpack(scalars[2]));
		if s2min > s1max or s2max < s1min then
			return false, Vector2.new(); -- mtv is nothing because there isn't collision
		end;
		-- we are getting the overlap of shape 1 on shape 2 which means we apply the mtv onto shape 2
		local overlap = s1max > s2max and -(s2max - s1min) or (s1max - s2min);
		if math.abs(overlap) < mtv.magnitude then
			-- overlap might be negative to account for proper direction
			mtv = axis[i] * overlap;
		end;
	end;
	return true, mtv;
end;
 
-- example
 
local f1 = script.Parent:WaitForChild("Frame1");
local f2 = script.Parent:WaitForChild("Frame2");
 
game:GetService("RunService").RenderStepped:connect(function()
	f1.Rotation = f1.Rotation + 1;
	f2.Rotation = f2.Rotation - 1;
	local doesCollide, mtv = collide(f2, f1);
	if doesCollide then
		f1.Position = f1.Position + UDim2.new(0, mtv.x, 0, mtv.y);
	end;
end);


Collision17.gif


Supplementary: line segment intersection[edit]

Alright, this last algorithm is more or less supplementary as it's not exactly ideal for the purposes of collision alone, but if you working in 2D you may find it useful to use with the other methods discussed for a bit more information about a shape's surroundings.

Understanding the math

Collision18.png

So let's say we have two lines, each line is essentially defined as a connection between two points (a to b, c to d). This form is alright, but since we are working with vectors we want to get our information in a form that is a bit more relevant to us. This is actually pretty easy to do with vector subtractions:

Collision19.png

Now if these two line segments do in fact intersect then we know that that there are some scalars, t and u, that when multiplied against r and s respectively equal to each other: That is our intersection point.

Collision20.png

Okay, so we have the equation setup, but we are somewhat stuck at this point. Normally the goal would be to solve algebracially for the unknown, but we have two unknowns! So, what do we do? Well, this is where things get tricky. What we are actually going to do is define the 2D cross product as:

function cross2d(a, b)
	return a.x * b.y - a.y * b.x;
end;
 
-- You might notice that this is actually just the z-value of what we would get if crossed these two vectors as 3D vectors.
function alternateCross2d(a, b)
	-- take note, the x and y values of the calculated cross will be zero
	return Vector3.new(a.x, a.y, 0):Cross(Vector3.new(b.x, b.y, 0)).z;
end;


One interesting propery of this that we want to take note of is that when we 2D cross any vector with itself the result is 0.

local v = Vector2.new(129290.31478, -342.232);
print(cross2d(v, v)); -- result: 0


With this in mind, all we have to do is apply this new definition to the equation we figured out above and solve for one of the variables:

Collision21 2.png

So, with this in mind we know that if we run this calculation and t and u are both between 0 and 1 (since we'd multiply it by our additive vectors) then we know the two lines intersect! That's all there is to it!

Writing the code

function lineIntersect(a, b, c, d)
	-- get it in our additive vector form
	local r = (b - a);
	local s = (d - c);
 
	-- we use this again so only calc once
	local d = r.x * s.y - r.y * s.x; 
	local u = ((c.x - a.x) * r.y - (c.y - a.y) * r.x) / d;
	local t = ((c.x - a.x) * s.y - (c.y - a.y) * s.x) / d;
 
	-- if they do intersect return where
	return (0 <= u and u <= 1 and 0 <= t and t <= 1) and a + t * r;
end;
 
print(lineIntersect(
	Vector2.new(0, 0), -- a
	Vector2.new(3, 3), -- b
	Vector2.new(3, 0), -- c
	Vector2.new(0, 3)  -- d
)); 
-- result: Vector2.new(1.5, 1.5)
 
print(lineIntersect(
	Vector2.new(0, 0), -- a
	Vector2.new(3, 3), -- b
	Vector2.new(3, 0), -- c
	Vector2.new(6, 3)  -- d
));
-- result: false


Awesome, now it's just a matter of applying this to our code. Luckily we have the corners figured out already so it's just a matter of comparing the line-segments that make up two shapes.

function lineIntersect(a, b, c, d)
	-- get it in our additive vector form
	local r = (b - a);
	local s = (d - c);
 
	-- we use this again so only calc once
	local d = r.x * s.y - r.y * s.x; 
	local u = ((c.x - a.x) * r.y - (c.y - a.y) * r.x) / d;
	local t = ((c.x - a.x) * s.y - (c.y - a.y) * s.x) / d;
 
	-- if they do intersect return where
	return (0 <= u and u <= 1 and 0 <= t and t <= 1) and a + t * r;
end;
 
function getSegments(corners)
	local segments = {};
	for k, corner in pairs(corners) do
		local ncorner = corners[k + 1 <= #corners and k + 1 or 1];
		table.insert(segments, {corner, ncorner});
	end;
	return segments;
end;
 
function collide(shape1, shape2)
	local s1, s2 = getSegments(getCorners(shape1)), getSegments(getCorners(shape2));
	for _, segment in pairs(s1) do
		for _, segment2 in pairs(s2) do
			local v = lineIntersect(segment[2], segment[1], segment2[2], segment2[1]);
			if v then
				return v;
			end;
		end;
	end;
	return false;
end;
 
-- example
 
local f1 = script.Parent:WaitForChild("Frame1");
local f2 = script.Parent:WaitForChild("Frame2");
 
game:GetService("RunService").RenderStepped:connect(function()
	f1.Rotation = f1.Rotation + 1;
	f2.Rotation = f2.Rotation - 1;
	local doesCollide = collide(f1, f2);
	f1.BorderColor3 = doesCollide and Color3.new(1, 0, 0) or Color3.new(0, 1, 0);
	f2.BorderColor3 = doesCollide and Color3.new(1, 0, 0) or Color3.new(0, 1, 0);
end);


Collision22.gif

You might notice that this method is lacking when one shape is larger than the other due to their edges not colliding, hence why it's not exactly optimal as a collision method. That being said, it's not impossible to adjust this method to fix this problem, but that will not be covered in this article.

See also[edit]