Skip to content

Analytical Geometry: Collision

Jump to bottom
Luan Orlandi edited this page Apr 14, 2017 · 12 revisions

This page will explain some concepts in the field of analytical geometry, and also how these concepts was structured in the code.

The focus here will be the collision of objects. If you skipped the movement part, please return there. Some subjects will appear again, but concepts will not be repeated.

Rectangle

Rectangles are polygons with 4 vertices. To represent one, we can just store all these vertices positions, and for this we may use 4 vectors to create 1 rectangle.

Fail to load image :(

But there is a better way to do it, just using 2 vectors.

Storing one vertex and the rectangle's center position is enough to represent one. It can be any vertex, but to maintain a pattern we will always save the top right vertex position.

However, the vertex position can't be in reference to the origin, but to the rectangle's center. See the imagine below:

Fail to load image :(

Note that the rectangle rotation is not considered in this way. We will only use rectangles with horizontal and vertical edges.

The three other vertices can be obtained by changing the signal in each coordinate.

Maybe you are still not convinced that storing 2 vectors instead of 4 can be a better approach, because the first way (4 vectors) looks more simple.

Imagine a object moving and that rectangle it's his box collision. The first approach requires that all 4 vectors be updated each time the object moves. The second approach requires that just 1 be updated, the rectangle's center (remember that the top right vector is in reference to the center, so we don't need to update it).

Creating rectangles

With the vectors already defined, we can use them to create rectangles. See the code below:

Rectangle = {}
Rectangle.__index = Rectangle

function Rectangle:new(c, v)
	local R = {}
	setmetatable(R, Rectangle)
	
	R.center = Vector:new(c.x, c.y)
	R.size = Vector:new(v.x, v.y)
	
	return R
end

-- create 2 rectangles with the same shape, but different positions
local size = Vector:new(1, 2)
local A = Rectangle:new(Vector:new(1, 1), size)
local B = Rectangle:new(Vector:new(1, -2), size)

Collision

Object collision in games is never calculated with the real object shape, this would result in a bad performance, because a user device can't handle so much calculations.

A very well know solution for this is use invisible objects to handle the collision. This object have a much simple shape, like circles, triangles or rectangles.

Here we use rectangles. A collision can happen with a point or another rectangle.

Rectangle with Point

To check a collision of a point with a rectangle we first need 2 vertices of the rectangle, the top right (PA) and bottom left (PB).

For the point to be inside, it needs to be between the vertical edges (PA.x, PB.x) and horizontal edges (PA.y and PB.y). Look the image below:

Fail to load image :(

The code for this:

function Rectangle:pointInside(p)
	local PA = Vector:new(self.center.x + self.size.x, self.center.y + self.size.y)
	local PB = Vector:new(self.center.x - self.size.x, self.center.y - self.size.y)

	if PA.x > p.x and PB.x < p.x then
		if PA.y > p.y and PB.y < p.y then
			return true
		end
	end
	
	return false
end

Rectangle with rectangle

To check a collision of a rectangle with another rectangle we first need 2 vertices of each rectangle, the top right (PA and PC) and bottom left (PB and PD).

For the rectangle have intersection, the rightmost vertical edges (PA.x and PC.x) must be higher than the leftmost vertical edges (PB.x and PD.x). The same for horizontal with the top (PA.y and PC.y) and bottom edges (PB.y and PD.y). Look the image below:

Fail to load image :(

The result in code for this is similar to the point collision:

function Rectangle:intersection(b)
	local PA = Vector:new(self.center.x + self.size.x, self.center.y + self.size.y)
	local PB = Vector:new(self.center.x - self.size.x, self.center.y - self.size.y)
	
	local PC = Vector:new(b.center.x + b.size.x, b.center.y + b.size.y)
	local PD = Vector:new(b.center.x - b.size.x, b.center.y - b.size.y)

	if PA.x > PD.x and PB.x < PC.x then
		if PA.y > PD.y and PB.y < PC.y then
			return true
		end
	end
	
	return false
end

Improved Collision

In some cases, just a rectangle for an entire object is enough for the collision. But the better is the precision, the better is the realism in collision.

Area

To get more precision we can create an area by adding many rectangles to cover the object's shape, but by doing this we will rapidly increase the number of collisions to check. To avoid this problem, we can maintain the initial rectangle that contain all the lesser rectangles that gives precision.

Now, we continue to check the collision with bigger rectangles, and only when a collision is found, we check the lesser rectangles. If none of those return a collision detection, then we discard the situation as a collision.

Creating areas

The class Area will have the bigger rectangle as the area size, and the smaller rectangles in a table:

Area = {}
Area.__index = Area

function Area:new(size)
	local A = {}
	setmetatable(A, Area)
	
	-- copy the rectangle
	A.size = Rectangle:new(Vector:new(0, 0), Vector:new(size.x, size.y))
	A.hitbox = {}
	
	return A
end

-- add a rectangle to the area, inserting it in hitbox
function Area:newRectangularArea(c, v)
	local rectangle = Rectangle:new(c, v)
	table.insert(self.hitbox, rectangle)
end

The rectangles in hitbox table not just have a size in reference to their center, but also his center have reference to the Area center. This might look complex (and it is), but there is example below in this page that will better show this.

Collision of area with area

To detect a collision between areas we must first check if the bigger rectangle (size) have collision, if not, them none of the hit boxes would have collision, if size detect a collision, then we must check collision of all hit boxes.

The more hit boxes the objects have, more precise will be the detection, but more calculations will be required.

function Area:detectCollision(orientationA, posA, b, orientationB, posB)
	-- self = area A
	-- b = area B
	-- orientation = if it is inverted

	-- copy return a rectangle copy with the center in posA and orientationA
	-- the center reference will be the origin
	local sizeA = self.size:copy(orientationA, posA)
	local sizeB = b.size:copy(orientationB, posB)
	local intersection = false
	
	if sizeA:intersection(sizeB) then
		local i = 1
		while not intersection and i <= #self.hitbox do
			local rectangleA = self.hitbox[i]:copy(orientationA, posA)
			
			local j = 1
			while not intersection and j <= #b.hitbox do
				local rectangleB = b.hitbox[j]:copy(orientationB, posB)
				
				intersection = rectangleA:intersection(rectangleB)
				j = j + 1
			end
			i = i + 1
		end
	end
	
	return intersection
end

Here is an example checking collision between 2 objects, which results false (note that if it was just the bigger rectangles, it would be a collision):

Fail to load image :(

local posA = Vector:new(3, 3)
local posB = Vector:new(7, 5)
local orientation = Vector:new(0, 1)

-- create the area
local areaA = Area:new(Vector:new(3, 3))
local areaB = Area:new(Vector:new(2, 2))

-- create the smaller rectangles for areaA
areaA:newRectangularArea(
	Vector:new(0, 0),
	Vector:new(3, 1))

areaA:newRectangularArea(
	Vector:new(0, 0),
	Vector:new(1, 3))

-- create the smaller rectangles for areaB
areaB:newRectangularArea(
	Vector:new(-1, 0),
	Vector:new(1, 1))

areaB:newRectangularArea(
	Vector:new(1, 0),
	Vector:new(1, 2))

local collision = areaA:detectCollision(orientation, posA, areaB, orientation, posB)
print(collision) -- false

Welcome

First things first

Programming in Lua

Analytical Geometry: Movement

Analytical Geometry: Collision

Applying Analytical Geometry

Clone this wiki locally