Posted on by

colldet-featA question that occasionally comes up in the forums is “how can I tell when object A touches object B?” In programming terms, this is known as a “collision”.

Corona SDK has a robust collision detection engine that can accomplish many things. It’s even event-driven, which means you can sense when collisions have began and ended. This system reports when the collision happens and which two objects are involved in the collision. The only “catch” is that it’s based on Corona’s physics engine. That means every moving object needs to be a physics-based object under the control of this physics engine. While the physics engine is a lean, mean, calculating machine, it’s still extra math and processing behind that scenes that you typically don’t need if you’re not using physics for other purposes — for example, if you simply want to know if object A is occupying the same screen space as object B.

Detection Methods

There are multiple ways to detect collisions without using physics. These methods are similar to those used by the physics engine, but you won’t deal with gravity, density, bounce, friction, etc. Some of these methods include:

  1. Point Inside a Rectangle
  2. Separating Axis Theorem
  3. Overlapping Circles
  4. Overlapping Rectangles

“Point Inside a Rectangle” can be complex if the rectangles have any rotation applied to them. Similarly, the “Separating Axis Theorem” is fairly math-intensive and won’t be covered in this tutorial. You can read about it here if you’re curious.

NOTE: Before considering non-physics collision detection, remember that if your objects are not basic rectangles or circles, the physics engine is likely the best choice to handle your collisions. Using it, you can define complex polygon-based shapes from multiple parts that represent the actual shape of your objects better than these methods will. Essentially, the non-physics methods in this tutorial follow the “close enough” methodology. If you need precise collisions, the physics engine is the logical choice.

Overlapping Circles

In an “Asteroids” type game, the ship — even though it might appear triangular — can be represented by a circle: either a circle that encloses the entire ship, or a circle that spans a slightly smaller area around the center of the ship. The asteroids flying around can also be roughly represented by circles. During fast gameplay, the player will not really notice exact shape-precise collision detection.

Some very simple calculations can tell you if any two circles of an arbitrary sizes are overlapping:

--circle-based collision detection
local function hasCollidedCircle( obj1, obj2 )
   if ( obj1 == nil ) then  --make sure the first object exists
      return false
   end
   if ( obj2 == nil ) then  --make sure the other object exists
      return false
   end

   local dx = obj1.x - obj2.x
   local dy = obj1.y - obj2.y

   local distance = math.sqrt( dx*dx + dy*dy )
   local objectSize = (obj2.contentWidth/2) + (obj1.contentWidth/2)

   if ( distance < objectSize ) then
      return true
   end
   return false
end

Here, you pass in two display objects. Since a circle is still a “rectangular image” from a display object standpoint, we’ll use the contentWidth to determine the size of the circles. If the two circles are closer than the distance of their centers, they are touching.

Overlapping Rectangles

This code was originally located in the the Corona Labs Code Share:

--rectangle-based collision detection
local function hasCollided( obj1, obj2 )
   if ( obj1 == nil ) then  --make sure the first object exists
      return false
   end
   if ( obj2 == nil ) then  --make sure the other object exists
      return false
   end

   local left = obj1.contentBounds.xMin <= obj2.contentBounds.xMin and obj1.contentBounds.xMax >= obj2.contentBounds.xMin
   local right = obj1.contentBounds.xMin >= obj2.contentBounds.xMin and obj1.contentBounds.xMin <= obj2.contentBounds.xMax
   local up = obj1.contentBounds.yMin <= obj2.contentBounds.yMin and obj1.contentBounds.yMax >= obj2.contentBounds.yMin
   local down = obj1.contentBounds.yMin >= obj2.contentBounds.yMin and obj1.contentBounds.yMin <= obj2.contentBounds.yMax

   return (left or right) and (up or down)
end

This function uses the built-in contentBounds of each rectangle to see if they have overlapped. This works great for tiles and cards since they are visually rectangular. It uses a set of if statement checks to see if any corner of one rectangle is inside the bounds of the other rectangle. For graphics that have some transparency around them, note that this will include the transparent areas. Both functions will return true if the objects/points are colliding with the other object.

Checking for Collisions

Now that you have a couple different ways to determine if two items have collided, how do you actually use them? Unlike physics-based collisions, these are not listener events where the system tells you exactly when they collide. Instead, you must check periodically in your own code. The two primary ways are:

  1. While touch-dragging an object around the screen.
  2. Checking each frame/cycle using an enterFrame Runtime listener (“game loop” method).

Touch and Drag

You’ve probably seen this touch-drag code before:

local function dragCard( event )
   local target = event.target 
   local phase = event.phase

   if ( event.phase == "began" ) then
      local parent = target.parent
      display.getCurrentStage():setFocus( target ) 
      target.isFocus = true
      target.x0 = event.x - target.x
      target.y0 = event.y - target.y
      target.xStart = target.x
      target.yStart = target.y
      target:toFront()
   elseif ( target.isFocus ) then
      if ( phase == "moved" ) then
         target.x = event.x - target.x0
         target.y = event.y - target.y0
      elseif ( phase == "ended" or phase == "cancelled" ) then
         display.getCurrentStage():setFocus( nil )
         target.isFocus = false
      end
   end
   return true
end

Now, for collision detection, you’ll add a check inside the phase moved or ended/cancelled conditional blocks, depending on when you need to check for the collision.

For simplicity, let’s use an example of dragging a card to a “drop zone,” potentially represented in your user interface by some outline graphic.

--forward declarations
local hotSpot
local card

local function dragCard( event )
   --insert code above here
   return true
end

local bg = display.newRect( 0, 0, display.contentWidth, display.contentHeight )

hotSpot = display.newRect( 0, 0, 50, 75 )
hotSpot.alpha = 0.25  --let's show it just a little
hotSpot.x = 200
hotSpot.y = 100
hotSpot:setFillColor( 255,0,0 )
card = display.newRect( 0, 0, 50, 75 )
card.x = 100
card.y = 100
card.xOrig = 100  --remember the initial location
card.yOrig = 100
card:setFillColor(0,0,255)

card:addEventListener( "touch", dragCard )

Now, you can request collision detection inside the standard drag handler. In this case, since you only care if the object is “dropped” in the right place, use the ended/cancelled phase:

elseif ( phase == "ended" or phase == "cancelled" ) then
   display.getCurrentStage():setFocus( nil )
   target.isFocus = false

   if ( hasCollided( event.target, hotSpot ) ) then
      --snap in place
      transition.to( event.target, {time=250, x=hotSpot.x, y=hotSpot.y} )
   else
      --move back
      transition.to( event.target, {time=500, x=event.target.xOrig, y=event.target.yOrig} )
   end
end

With this code, if you drag the card and drop it outside the drop zone, it will transition back to its original location. If the card touches the hot spot, then it will snap the target into place!

Let’s look at another example. This time you will spawn a bunch of coins and then touch-drag myPlayer to pick them up. Instead of doing the collision check in the ended/cancelled phase, you’ll check in the moved phase so that the collision report will occur immediately when myPlayer crosses over a coin:

local myPlayer = display.newCircle( 0, 0, 25 )
myPlayer:setFillColor( 0, 128, 0 )
myPlayer.x = display.contentCenterX
myPlayer.y = display.contentCenterY

local coins = {}
for i = 1,20 do
   coins[i] = display.newCircle( 0, 0, 15 )
   coins[i]:setFillColor( 255, 128, 0 )
   coins[i].x = math.random( 15, display.contentWidth - 15 )
   coins[i].y = math.random( 15, display.contentHeight - 15 )
end

local function movePlayer( event )
   local target = event.target 
   local phase = event.phase
   if ( phase == "began" ) then
      local parent = target.parent
      display.getCurrentStage():setFocus( target ) 
      target.isFocus = true
      target.x0 = event.x - target.x
      target.y0 = event.y - target.y
      target.xStart = target.x
      target.yStart = target.y
      target:toFront()
   elseif ( target.isFocus ) then
      if ( phase == "moved" ) then
         target.x = event.x - target.x0
         target.y = event.y - target.y0
         for i = 1,table.maxn(coins) do
            if ( coins[i] and hasCollidedCircle( event.target, coins[i]) ) then
               --pick up coin!
               coins[i]:removeSelf()
               coins[i] = nil
            end
         end
      elseif ( phase == "ended" or phase == "cancelled" ) then
         display.getCurrentStage():setFocus( nil )
         target.isFocus = false
      end
   end
   return true
end

myPlayer:addEventListener( "touch", movePlayer )

Runtime Detection (Game Loop)

These collision techniques also work well in enterFrame listeners where you can check for things that are transitioning around that the user isn’t directly in control of.

For this to work, your objects need to be in an array to loop through. Using the same coins above, let’s apply some transitions to move them to the bottom of the screen and then remove those coins that hit our player. For additional effect, if the coin hits our player, we’ll turn it blue.

local myPlayer = display.newCircle( 0, 0, 25 )
myPlayer:setFillColor( 0, 128, 0 )
myPlayer.x = display.contentCenterX
myPlayer.y = display.contentCenterY

local coins = {}
for i = 1,20 do
   coins[i] = display.newCircle( 0, 0, 15 )
   coins[i]:setFillColor( 255, 128, 0 )
   coins[i].x = math.random( 15, display.contentWidth - 15 )
   coins[i].y = math.random( 15, display.contentHeight - 15 )
end

local function gameLoop( event )
   for i = 1,table.maxn( coins ) do
      if ( coins[i] and hasCollidedCircle( myPlayer, coins[i]) ) then
         coins[i]:setFillColor(0,0,255)
      end
   end
   return true
end

Runtime:addEventListener( "enterFrame", gameLoop )

This concludes the tutorial on non-physics collision detection. As you can see, this is a convenient method when you’re building an app where you require basic collision detection, but the physics engine — as powerful as it can be — is overkill for the required tasks.


Posted by . Thanks for reading...

8 Responses to “Tutorial: Non-Physics Collision Detection”

  1. Cleverson

    Great article!
    Any benchmark regarding using these “manual” techniques or leaving everything to the physics engine?

    Reply
  2. Rob Miracle

    I don’t know of any benchmarking, but physics has to have a list of object to iterate over to check for collisions, then they have to call functions to dispatch events that then have to call function handlers and a bunch of stuff going on in floating point number space.

    It can’t be faster than iterating over a list of objects, calling a function to do some integer math (for the rectangles) and limited floating point math for the circles (and there is a version that drops the square root’s out for even more performance). So it’s should be similar in performance if not a bit faster.

    Of course there are a few things you can do to speed up this even more, like in the coins example, doing:

    local coin = coins[i]

    and then doing all the test on coin (removes a couple of table lookups) (thanks Danny!).

    Reply
  3. finefin

    Here’s another one – Line intersection:

    ——————
    – Intersecting Lines –
    —————–
    – example: doLinesIntersect ( line1.pointA, line1.pointB, line2.pointA, line2.pointB )
    – points are tables containing x and y coordinates
    – returns: true, coordinate / false
    —————–
    doLinesIntersect = function ( a, b, c, d )
    local L1 = {X1=a.x,Y1=a.y,X2=b.x,Y2=b.y}
    local L2 = {X1=c.x,Y1=c.y,X2=d.x,Y2=d.y}
    local d = (L2.Y2 – L2.Y1) * (L1.X2 – L1.X1) – (L2.X2 – L2.X1) * (L1.Y2 – L1.Y1)
    if (d == 0) then
    return false
    end
    local n_a = (L2.X2 – L2.X1) * (L1.Y1 – L2.Y1) – (L2.Y2 – L2.Y1) * (L1.X1 – L2.X1)
    local n_b = (L1.X2 – L1.X1) * (L1.Y1 – L2.Y1) – (L1.Y2 – L1.Y1) * (L1.X1 – L2.X1)
    local ua = n_a / d
    local ub = n_b / d
    if (ua >= 0 and ua = 0 and ub <= 1) then
    local x = L1.X1 + (ua * (L1.X2 – L1.X1))
    local y = L1.Y1 + (ua * (L1.Y2 – L1.Y1))
    return true, {x=x, y=y}
    end
    return false
    end

    Reply
  4. Dpeif

    Great post, very informative and applicable to many projects. Thanks for posting, very well written too.

    Just as a general question, are there advantages to using these methods for UI functionality, i.e. the card drag-drop-snapback scenario, instead of using jQuery-UI’s .draggable() or .droppable() ?

    Reply
  5. Rob Miracle

    Well, given that Corona SDK Native apps are built in Lua and not Javascript, you can’t use jQuery and jQuery UI, so yea, there is a big advantage. Sure you can have native.newWebView’s which can run web pages using jQuery et. al. but if you’re going to use Corona SDK you’re not going to be interfacing with jQuery.

    Reply
  6. Ariel

    We have started using HardonCollider which is a very neat lua collision library implementing the GJK algorithm.
    I don’t have any performance number comparing to Box2D but for our 2D shooter it works much smoother.
    It is much lighter and provides only part of the collision functionality from Box2D as it doesn’t supply you with the collision point. It doesn’t even resolve the collision but it does provide you with a displacement vector with which you can resolve the collision and also compute the aproximate collision point.

    It also supports Points, Circles, Rectangles and any other convex or concave (which Box2D doesn’t support) polygons.
    You also have some cool API calls for hit testing for collisions within a region without having a real body colliding. This is useful for example when our character punchs and we want to see which enemies are in the punch area.

    It does require a little bit of code tweaking to get it going because it was designed to be used with the LOVE framework so you’ll need to modify two things:
    1. In the first line of the init.lua file you need to change it to:
    local _NAME, common_local = string.gsub( …, “.init”, “”), common
    And when you load the module you need to explicitly require the init.lua file and not like in the tutorial, that’s because package.path is configured differently in LOVE and it automatically searches for a init.lua file when you require a folder.

    2. If you want debug polygon shape printing you’ll need to replace the love.draw calls with Corona draw functions.

    Took us about an hour to hook it in our game and we are very happy with it.

    Reply

Leave a Reply

  • (Will Not Be Published)