Tutorial 31 - Codea Collision Detection

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:

1. Dynamic - these objects move under the influence of collisions, forces, joints and gravity (we will use this type for our asteroids);
2. Static - these objects are not supposed to move and are unaffected by collisions and forces (e.g. the ground or walls); and 
3. 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.

function setup()

    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

Next up we need functions to create our asteroids. We will use the same function (createRandPoly) to generate the debris field for when our ship collides with an asteroid and explodes.

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.

Interlude 4 - A Rounded Border Class (Updated 17/01/16)

Interlude 4.1 Yes it is a bit of a Hack...

For our splash screen Tutorial we wanted to include a nice rounded border. To that end the following extends the roundRect() function that we have used in previous tutorials (to create a button). There are much more elegant ways to achieve this (e.g. using a mesh) but this has the advantage of simplicity. Once we have covered meshes we will rewrite this class. Another alternative would be to extend the roundRect() function to include a variable which determines if the roundRect is filled or not.

Interlude 4.2 The Rounded Border Class

This class relies on the roundRect() function, so you must include that to use RoundBorder(). The concept is very simple. We just draw two rounded rectangles, one inside the other. The inner rectangle is smaller by a factor of borderWidth. The larger rectangle is drawn using the borderColour and the inner using the fillColour.

RoundBorder = class()

function RoundBorder:init(x, y, w, h, borderWidth, borderColour, fillColour)

    -- you can accept and set parameters here
    -- Set dimensions of the outer "border" round rectangle

    self.x = x
    self.y = y
    self.w = w
    self.h = h
    self.r = 30

    self.borderWidth = borderWidth
    self.borderColour = borderColour
    self.fillColour = fillColour
    
    -- Set dimensions of the inner "background" round rectangle

    inX = self.x + self.borderWidth
    inY = self.y + self.borderWidth
    inW = self.w - 2 * self.borderWidth
    inH = self.h - 2 * self.borderWidth
end

function RoundBorder:draw()
    -- Codea does not automatically call this method
    -- Do the right thing and save the graphic context
    
    pushStyle()
    
    -- Start by drawing the outer Rounded Rectangle, this will become the border.
    
    fill(self.borderColour)
    roundRect(self.x, self.y, self.w, self.h, self.r)
    
    -- Then draw the inner rectangle using the fill colour
    
    fill(self.fillColour)
    roundRect(inX, inY, inW, inH, self.r)
    
    -- Return the graphic context to the way it was when entering this function
    
    popStyle()
end

Tutorial 2 - Creating a Rounded Rectangle (Updated 2/9/15)

Webcomic Courtesy of Ethanol & Entropy

Version Information

This tutorial has been updated for Codea version 2.3.1(47). You can check your version of Codea by tapping on the Two Lives Left logo in the bottom middle of the Codea start screen (Tutorial 1, Figure 1).

2.0 Drawing a Rounded Rectangle

Ok so our aim in these tutorials is to create code and classes that can be reused. We are working up to a standard menu class which can be used in your programs. But we need to build some foundations first, and the good people at Two Lives Left have provided most of the sample code we need. Curious?

Now menus need buttons and buttons need a rounded rectangle, so let's start there. Open up the Codea example program called Sounds Plus (Figure 7 - you will need to scroll down a bit) by tapping on it. 

Figure 7. Tap on Sounds Plus Example

One of the tabs in this project is called RoundRect, which is exactly what we need. Tap on this tab. We want to copy this entire class and use it in our new Menu project. To do this, tap and hold on any of the text in this class to bring up the Selection pop up, then tap on Select All, and then Copy. Dismiss the keyboard and then tap the back button (<) in the top left corner.

Back at the Codea launch page, tap on Add New Project and call it Menu (or whatever else you want). You will have one class called Main which you would have seen in Tutorial 1. Tap on the + in the top right corner and then tap on Create New Class (Figure 8). 

Figure 8. Create a New Class.

Call the new class RoundRect and then tap done. This will generate three boiler plate functions (init, draw and touched) which we don't need. Tap and hold on any of the text in the class, Select All and tap the delete key on the keyboard. Tap and hold on the empty screen to bring up the Paste pop up and tap that. Make sure you don't tap Cut to remove the old text otherwise you will overwrite the code you copied and will paste back what you just tried to delete.

You should now have the RoundRect class (Figure 9) which you copied from the Sounds Plus example code. 

Figure 9. RoundRect Class

Let's have a bit of a look at the rounded rectangle class. I have inserted comments in green to help you understand what is happening.

The roundRect function has 5 variables. These are: roundRect(x, y, w, h, r)

x - the x co-ordinate of the lower left corner of the rounded rectangle
y - the y co-ordinate of the lower left corner of the rounded rectangle

w - width of the rounded rectangle
h - height of the rounded rectangle

r - radius of the corners

function roundRect(x,y,w,h,r)

-- [[ pushStyle() saves the current graphic styles like stroke, width, etc. You can then do your thing and call popStyle at the end to return to this state.]]

    pushStyle()

-- [[ insetPos and insetSize contain the co-ordinates for the internal "fill" rectangle. InsetPos.x = x, insetPos.y = y, insetSize.x = w and insetSize.y = h. In effect this creates a rectangle that is smaller than a factor of "r" within the rectangle co-ordinates specified in roundRect. ]]
    
    insetPos = vec2(x+r,y+r)
    insetSize = vec2(w-2*r,h-2*r)
    
-- Copy fill into stroke

-- [[ Since Codea 1.3 you can retrieve the style information from all style functions by calling them without arguments. This way you only have to set the fill style once as you would for the normal rectangle function. You can read all about how this rounded rectangle function evolved on the Codea Forums.]]

    local red,green,blue,a = fill()
    stroke(red,green,blue,a)
    
-- [[noSmooth() will disable smooth (unaliased) line drawing. It is useful for drawing thin lines. This initial rectangle is used to fill in the centre of your rounded rectangle, it has the usual 90 degree corners. Four lines are then drawn around this to give the rounded corner look. You can see this yourself by commenting out the 4 lines drawn below. ]]

    noSmooth()
    rectMode(CORNER)
    rect(insetPos.x,insetPos.y,insetSize.x,insetSize.y)
    
    if r > 0 then

-- [[ You have to use smooth() if you want to use the ROUND option for lineCapMode. Four lines are now drawn around the filler rectangle. One on each edge. Because the lines have rounded ends when you overlap them it makes the corners look rounded, albeit a bit like a ball if you get the proportions wrong. Each of the lines are twice the width of the corner radius. ]]

        smooth()
        lineCapMode(ROUND)
        strokeWidth(r*2)

        line(insetPos.x, insetPos.y, 
             insetPos.x + insetSize.x, insetPos.y)
        line(insetPos.x, insetPos.y,
             insetPos.x, insetPos.y + insetSize.y)
        line(insetPos.x, insetPos.y + insetSize.y,
             insetPos.x + insetSize.x, insetPos.y + insetSize.y)
        line(insetPos.x + insetSize.x, insetPos.y,
             insetPos.x + insetSize.x, insetPos.y + insetSize.y)            
    end

    popStyle()

end

So let's take our copied class for a spin. On my iPad AIR, the dimensions of the drawing screen is:

Width - 749 pixels
Height - 768 pixels

Sidebar: You can find out your screen dimensions by adding the following two lines to the Hello World project that you created in Tutorial 1. Stick these in the setup() function (Figure 10).

Figure 10. Determine the WIDTH & HEIGHT of your screen.

print("Screen Width: "..WIDTH)

print("Screen Height: "..HEIGHT)

One of the fab things about Lua is its ability to simply concatenate a string and a number using .. as shown in the print statement above. There is no need to convert the number to a string, it happens automagically.

Sidebar Update: As Hillary mentions in the comment below the iPad 3 has the same screen dimensions in the STANDARD display mode as the iPad 1 and 2. I should have mentioned that Codea lets you set one of three display modes using the function displayMode() - obvious huh. The three display modes available are:

1. STANDARD;
2. FULLSCREEN; and
3. FULLSCREEN_NO_BUTTONS (which hides the back, pause and play buttons).

In FULLSCREEN landscape mode the iPad 1 & 2 has screen dimensions of:

Height: 768 pixels
Width: 1024 pixels

You can check this out yourself by sticking displayMode(FULLSCREEN) in the setup() function of the Hello World project that we did in Tutorial 1 and using text() in the draw() function to display the HEIGHT and WIDTH constants - note the output from print() is not visible in FULLSCREEN mode.

The iPad 3 has double the resolution of the earlier versions, i.e. in FULLSCREEN landscape mode -

Height: 1536 pixels
Width: 2048 pixels 

In Interlude 13 we will discuss this subject in a lot more depth, skip ahead and have a read if you are interested.

Tap on the Main tab in your Menu class and below the comment -- Do your drawing here add the following line of code. Note that the variables chosen aren't anything special, we are just trying to draw the rectangle near the centre of the screen. Try modifying the variables yourself to see the effect. See Figure 11.

roundRect(WIDTH/2 - 150, HEIGHT/2, 300, 20, 30)

Figure 11. Using the RoundRect Function.

Run the program and you should end up with a gray rounded rectangle on your drawing screen (Figure 12). In the next tutorial we will turn this rectangle into a button.

Figure 12. A Rectangle with rounded corners!

Happy Coding.

SURPRISE SPECIAL BONUS SECTION:

Well not really that special - I should have mentioned that Codea is designed for fast prototyping and comes with some groovy functions to assist with this, namely parameter.

parameter.number(name, min, max) will populate your run screen with a visual slider which adjusts the value of the global variable called name between the min and max values specified, starting at the initial value. The difference between parameter.number and parameter.integer is that parameter.number gives you a float variable while parameter.integer will give you an integer. You usually stick these in the setup() function of your Main class.

Figure 13. RoundRect with Parameters.

There are a couple of example projects provided with Codea which illustrate the use of parameters but let's give them a spin on our rounded rectangle class. Update the Main class in our menu project to look like the following (Figure 13).

function setup()

    print("Rounded Rectangle Fast Prototype")
    
    -- [[parameter.number provides a float parameter(name, min, max, initial, callback). Don't worry about callback at the moment, we will use this later to respond to changes in the parameter.]]

    parameter.number("x", 0, WIDTH, WIDTH/2 - 150)
    parameter.number("y", 0, HEIGHT,  HEIGHT/2) 
    parameter.number("w", 0, WIDTH, 300)
    parameter.number("h", 0, HEIGHT, 21)
    parameter.number("r", 0,  200,  30)

end

-- This function gets called once every frame

function draw()

    -- This sets a dark background color 
    background(40, 40, 50)

    -- Do your drawing here
    
    roundRect(x, y, w, h, r)
    
end

Now run the program and note how moving the sliders changes the variables which effect your rounded rectangle. You can see how easily you could play with this to get exactly the shape you were after. You could then note down the variables required to reproduce that shape in your code. You will need to scroll up the parameter list to see r (Figure 14).

Figure 14. RoundRect with Parameters.

2.1 An Alternative Approach

@Jordan has come up with an alternative approach to drawing rounded rectangles using an ellipse for the corners. His code is available over at the Codea Forums.