### 31.1 Overview

Collision detection is a common requirement in game or simulator programming. It involves determining whether two or more objects have intersected. We will only be examining this problem in 2D (two dimensions) for this tutorial.

There are two main approaches to detecting collisions, discrete and continuous. In the discrete case, we advance the physical model by a small time step, and then check if any of our objects are intersecting, or are so close to each other that for all intents and purposes we consider them intersecting. For the continuous case, we write a collision detection algorithm which will be able to predict the trajectories of the physical bodies. The instants of collision are calculated, and the physical bodies never actually have to collide for us to detect the collision.

The continuous approach is more accurate but is also more difficult. So for this tutorial, we will develop a few different discrete detection algorithms. Discrete detection will get the job done in many situations and is well suited to the Codea draw loop architecture. As long as your time steps are small enough, there aren't too many objects and the objects are large enough, you shouldn't miss any collisions.

Note that collision detection can chew up a lot of CPU time. If n is the number of objects on the screen that we need to test, then the:

Number of collision detection tests = (n² - n) / 2

Thus the number of tests increases exponentially with the number of objects being modeled. Consequently, if you have more than a few objects, you will want to look at optimising your tests.

### 31.2 Bounding Box Detection

If we have two rectangular objects with origins at (x1, y1) and (x2, y2) and dimensions (i.e. width and heights) of (w1, h1) and (w2, h2), then we can use the following function to determine whether the two rectangles are overlapping at a particular point in time.

function CollisionDetected(x1, y1, w1, h1, x2, y2, w2, h2)

Collision = false

if (y2 >= y1 and y1 + h1 >= y2) or (y2 + h2 >= y1 and y1 + h1 >= y2 + h2)

or (y1 >= y2 and y2 + h2 >= y1)

or (y1 + h1 >= y2 and y2 + h2 >= y1 + h1) then

if x2 >= x1 and x1 + w1 >= x2 then -- corner 1

Collision = true

end

if x2 + w2 >= x1 and x1 + w1 >= x2 + w2 then -- corner 2

Collision = true

end

if x1 >= x2 and x2 + w2 >= x1 then -- corner 3

Collision = true

end

if x1 + w1 >= x2 and x2 + w2 >= x1 + w1 then -- corner 4

Collision = true

end

end

return Collision -- return whether or not a collision is detected

end

A faster version (about 10%) of the same function (albeit a bit more difficult to follow) is:

function CollisionDetected(x1, y1, w1, h1, x2, y2, w2, h2)

return not ((y1+h1 < y2) or (y1 > y2+h2) or (x1 > x2+w2) or (x1+w1 < x2))

end

And here is another version:

function CollisionDetected(x1, y1, w1, h1, x2, y2, w2, h2)

local ax2, bx2, ay2, by2 = x1 + w1, x2 + w2, y1 + h1, y2 + h2

return ax2 > x2 and bx2 > x1 and ay2 > y2 and by2 > y2

end

We will leave it as an exercise for the reader to demonstrate that these functions are all logically equivalent.

### 31.3 Bounding Circle Detection

The simplest method to detect circles colliding is to check whether the circles are overlapping. This can be done by calculating the distance between the centers of the two circles and seeing if it is less than or equal to the sum of the radii of the circles. If it is then a collision has occurred.

function CollisionDetected(x1, y1, r1, x2, y2, r2)

local dx = x2 - x1

local dy = y2 - y1

return math.sqrt(dx^2 + dy^2) <= r1 + r2

end

The square root in the distance formula is unnecessary because the inequality will still hold if we square both sides. Removing the square root will increase your collision detection speed, especially if you are checking for many collisions, because this is a relatively expensive calculation.

function CollisionDetected(x1, y1, r1, x2, y2, r2)

local dx = x2 - x1

local dy = y2 - y1

return (dx^2 + dy^2) <= (r1 + r2)^2

end

### 31.3 Box2D Collision Detection

If you don't want to roll your own collision detection, then you can utilise the built in collision detection functionality of Codea, which is provided courtesy of its Box2D implementation. To use this, the bodies which are colliding need to be created using the physics.body() function. The downside of using this approach is that physics bodies can only have the following shapes (the property is called shapeType):

- Circle;
- Polygon;
- Chain; or
- Edge (usually used for the ground or walls).

So for pixel perfect collisions you will need to use another approach if your sprites can't be outlined using one of the shapes above. In many cases however, you can approximate the sprite shape using these.

In addition to the shape type, we need to define the body type for our physics object. There are three options:

- Dynamic - these objects move under the influence of collisions, forces, joints and gravity (we will use this type for our asteroids);
- Static - these objects are not supposed to move and are unaffected by collisions and forces (e.g. the ground or walls); and
- Kinematic - these objects can move by setting their linear velocity but like static bodies are unaffected by collisions and forces (we will use this type for our ship, if the ship collides with an asteroid we want it to explode not bounce away).

To demonstrate how easy this is to implement we will create a simple Asteroids game with a ship in the center of the screen and randomly generated asteroids, which will destroy our ship if we detect a collision.

While Box2D will model the movement of our physics bodies for us, it is our responsibility to render (i.e. draw) representations of these bodies on the screen. To do this we will use a simplified version of the PhysicsDebugDraw class (called PhysicsDraw) which is included with the Physics Lab example. A copy of this simplified class is included at the end of the tutorial.

physics.gravity(0.0, 0.0)

physicsDraw = PhysicsDraw()

ship = createShip(WIDTH/2, HEIGHT/2)

physicsDraw:addBody(ship)

asteroidTimer = 0

end

The physics.gravity function allows us to set the gravity for our game for the x and y axis respectively. The units are pixels per second squared. We have set our program gravity to zero since we are in space. The createShip function will create a new physics body which we add to the table of bodies in PhysicsDraw. Every draw cycle, PhysicsDraw will render all the physics bodies at their current location.

function createShip(x, y, w, h)

-- (x, y) are the centre co-ordinates of the ship.

-- (w, h) define the width and height of the box containing the ship,

-- if not specified they are 50 and 35 respectively.

local width = w or 50

local height = h or 35

local shipBody = physics.body(POLYGON,

vec2(0, height), vec2(width, height/2),

vec2(0, 0), vec2(height/2, height/2),

vec2(0, height))

shipBody.x = x

shipBody.y = y

shipBody.type = KINEMATIC

shipBody.sleepingAllowed = false

shipBody.info = "ship"

shipBody.interpolate = true

return shipBody

end

function createRandPoly(x, y, s1, s2)

-- s1 and s2 define the range of length for the poly sides

-- count defines the number of sides of the poly

local minLength = s1 or 1

local maxLength = s2 or 5

local count = math.random(5,10)

local r = math.random(minLength, maxLength)

local a = 0

local d = 2 * math.pi / count

local points = {}

for i = 1,count do

local v = vec2(r,0):rotate(a)

+ vec2(math.random(-10,10), math.random(-10,10))

a = a + d

table.insert(points, v)

end

local poly = physics.body(POLYGON, unpack(points))

poly.x = x

poly.y = y

poly.type = DYNAMIC

poly.sleepingAllowed = false

poly.restitution = 0.5

poly.info = "poly"

physicsDraw:addBody(poly)

return poly

end

function createAsteroid(x, y)

return createRandPoly(x, y, 25, 65)

end

The asteroids are placed off the screen in random locations and accelerated towards the screen where eventually one of them will collide with our ship. Inside the draw() function we create a new asteroid every second.

function placeRandomAsteroid()

-- Generate (x, y) co-ordinates which are

-- initially off the screen.

local x = math.random(WIDTH)

if x < WIDTH/2 then

x = x - WIDTH

else

x = x + WIDTH

end

local y = math.random(HEIGHT)

if y < HEIGHT/2 then

y = y - HEIGHT

else

y = y + HEIGHT

end

-- Create an asteroid at the new co-ordinates

local asteroid = createAsteroid(x, y)

-- Give the asteroid a linear velocity

-- towards the screen (and our ship)

local dX, dY = math.random(50, 100), math.random(50, 100)

if x > WIDTH then

dX = -dX

end

if y > HEIGHT then

dY = -dY

end

asteroid.linearVelocity = vec2(dX, dY)

end

function createExplosionAt(x, y)

-- Creates 6 small polygon moving out from (x, y)

-- to simulate our ship exploding.

--

-- the body.info field is set to debris so that we

-- can render it the same colour as our ship (i.e. to

-- distinguish them from the asteroid polygons.

randPoly1 = createRandPoly(x, y)

randPoly1:applyForce(vec2(50,50))

randPoly1.info = "debris"

randPoly2 = createRandPoly(x, y)

randPoly2:applyForce(vec2(50,50))

randPoly2.info = "debris"

randPoly3 = createRandPoly(x, y)

randPoly3:applyForce(vec2(50,50))

randPoly3.info = "debris"

randPoly4 = createRandPoly(x, y)

randPoly4:applyForce(vec2(-50,50))

randPoly4.info = "debris"

randPoly5 = createRandPoly(x, y)

randPoly5:applyForce(vec2(-50,50))

randPoly5.info = "debris"

randPoly6 = createRandPoly(x, y)

randPoly6:applyForce(vec2(-50,50))

randPoly6.info = "debris"

end

-- This function gets called once every frame

function draw()

-- This sets a dark background color

background(40, 40, 50)

-- Generate a random asteroid every second

asteroidTimer = asteroidTimer + DeltaTime

if asteroidTimer > 1.0 then

placeRandomAsteroid()

asteroidTimer = 0

end

-- Do your drawing here

physicsDraw:draw()

end

-- Collision Detection

--

-- This is simply a matter of checking whether one of the two

-- colliding bodies are our ship.

function collide(contact)

if contact.bodyA == ship or contact.bodyB == ship then

createExplosionAt(ship.x, ship.y)

ship.info = "destroyed"

ship = nil

end

end

Collision detection is then just a matter of calling the built in collide() function and checking whether one of the two colliding bodies is our ship. Included below is the simplified PhysicsDebugDraw class which is responsible for rendering our physics bodies each frame.

--# PhysicsDraw

PhysicsDraw = class()

-- Simplified Physics Debug Draw class from the Physics Lab

-- example in Codea.

function PhysicsDraw:init()

self.bodies = {}

self.contacts = {}

end

function PhysicsDraw:addBody(body)

table.insert(self.bodies,body)

end

function PhysicsDraw:draw()

pushStyle()

smooth()

noFill()

for i,body in ipairs(self.bodies) do

pushMatrix()

translate(body.x, body.y)

rotate(body.angle)

if body.type == STATIC then

stroke(255,255,255,255)

elseif body.type == DYNAMIC and body.info ~= "debris" then

stroke(150,255,150,255)

else

stroke(150,150,255,255)

end

if body.shapeType == POLYGON and body.info ~= "destroyed" then

strokeWidth(3.0)

local points = body.points

for j = 1,#points do

a = points[j]

b = points[(j % #points)+1]

line(a.x, a.y, b.x, b.y)

end

elseif body.shapeType == CHAIN or body.shapeType == EDGE then

strokeWidth(3.0)

local points = body.points

for j = 1,#points-1 do

a = points[j]

b = points[j+1]

line(a.x, a.y, b.x, b.y)

end

elseif body.shapeType == CIRCLE then

strokeWidth(3.0)

line(0,0,body.radius-3,0)

ellipse(0,0,body.radius*2)

end

popMatrix()

end

stroke(255, 0, 0, 255)

fill(255, 0, 0, 255)

for k,v in pairs(self.contacts) do

for m,n in ipairs(v.points) do

ellipse(n.x, n.y, 10, 10)

end

end

popStyle()

end

function PhysicsDraw:collide(contact)

if contact.state == BEGAN then

self.contacts[contact.id] = contact

sound(SOUND_HIT, 2643)

elseif contact.state == MOVING then

self.contacts[contact.id] = contact

elseif contact.state == ENDED then

self.contacts[contact.id] = nil

end

end

A complete download of the code presented in this tutorial is available from our Gist repository.

## No comments:

## Post a Comment