Hit Detection for Spheres and Platforms

There are tons of tutorials out in the wild that explain how to create a basic platformer game. Most of them will at some point add in a basic ‘ground’ by restricting the y coordinate of your character to ensure it doesn’t fall below zero. Using a little bit of math we can extend this basic idea to preform much more general hit detection.

Platforms as Vectors and the Trapezium Approximation

Suppose our player is represented by a ball of radius \(r\) at position \(p = (x_p,y_p)\). We want the player not to fall below the ‘ground’, which is at height \(0\). This primitive hit detection is super easy to test, \[ y_p \leq 0 + r. \]

We can rephrase this in terms of a vertical normal vector, \[ p \cdot (0,1) \leq 0 + r. \]

Writing the ‘obvious’ floor test in this way, we can extend it to a floor at any height and angle. Any line in 2d space can be represented by a unit normal vector \(n\) and an offset \(a\), where the line will be the set of points \((x,y)\) satisfying \[ (x,y) \cdot n = a. \]

Our player will have touched this floor whenever we have \[ p \cdot n \leq a + r. \] At this point it is important that \(n\) is a unit normal vector so that we can easily add the radius of the ball.

This is all good and well for infinite lines, but generally in a game the platforms would be short segments. Something like this,

Using one off the points on the line, we can rewrite the offset \(a\). \[ n \cdot p \leq n \cdot p_0 + r. \] However this doesn’t help us with the bounds of the platform.

The diagram below shows the hit detection area. The ball and the platform will collide whenever the center of the ball (\(p\)) is inside the red area.

This red hit area is relatively simple, and it’s not hard to calculate exactly when the player is in this area. However, it does require quite a few calculations. There is a nifty approximation we can use that’s considerably quicker. It does require pre-computing some more normal vectors, but then the actual hit calculations are very simple.

By straightening the round corners we lose a tiny bit of accuracy, but in compensation can calculate the hit detection with just a few dot products.

\[ n \cdot p_0 \leq n \cdot p \leq n \cdot p_0 + r \\ n_0 \cdot p \leq n_0 \cdot p_0 + \frac{r}{\sqrt{2}} \\ n_1 \cdot p \leq n_1 \cdot p_1 + \frac{r}{\sqrt{2}} \]

Maths over and done with, let’s implement this as a little toy example.

Toy Implementation

We can implement this hit detection technique quite simply using the Haskell library Gloss. Gloss provides (limited) 2D graphics and a built in implementation for simple games. This whole page is written in literate Haskell so you should be able to copy and paste it directly into a new project.

module Main where

import Graphics.Gloss
import Graphics.Gloss.Interface.Pure.Game

Gloss comes with a built in datatype Point which is just syntactic sugar for (Float,Float). For simplicity’s sake, we’ll run with Gloss’ point type and implement our own primitive linear algebra functions. This is good enough here, but in general you should use a real linear algebra library like linear. (And I really shouldn’t hardcode in rotation matrices!)

(.*) :: Float -> Point -> Point
(.*) a (x,y) = (a*x,a*y)

dot :: Point -> Point -> Float
dot (x1,y1) (x2,y2) = x1 * x2 + y1 * y2

normalise :: Point -> Point
normalise p@(x,y) = (1/sqrt(x^2 + y^2)) .* p

rotate90 (x,y) = (-y,x)
rotate45 (x,y) = (1/sqrt 2) .* (x-y,x+y)
rotate315 (x,y) = (1/sqrt 2) .* (x+y,y-x)

Lets first make a datatype to describe our surfaces. Our level will be a collection of surfaces.

data Surface = Surface
                { normal :: Point
                , offset :: Float
                , lowerBoundNormal :: Point
                , lowerBoundOffset :: Float
                , upperBoundNormal :: Point
                , upperBoundOffset :: Float
                }

type Surfaces = [ Surface ]

In our surface data type the three normals correspond to the normals we use for the detection. We will assume that they are all unit vectors. The offsets are the constants used to define the three hyperplanes.

With this Surface datatype we can implement the hit detection.

detect :: Point -> Surface -> Bool
detect p s =  p `dot` (lowerBoundNormal s) <= lowerBoundOffset s
           && p `dot` (upperBoundNormal s) <= upperBoundOffset s
           && offset s <= p `dot` (normal s)
           && p `dot` (normal s) <= offset s + playerRadius

The detect function will tell us if the player and a surface collide. We then need to work out how to update the world to deal with the collision. Before this, lets describe the player.

playerRadius = 10

data Player = Player
    { pos :: Point
    , vel :: Point
    , acc :: Point }

gravity = -300

initialPlayer = Player { pos = (400,300) , vel = (0,0) , acc = (0,gravity) }

Our player is simply a point with velocity and acceleration. Later on we can add some physics. A nice way to deal with the collision is by modifying the velocity of the player. When the player hits the immovable surface, the component of the players velocity in that direction will be eliminated. (Note that we should only do this if the player is moving towards the surface.)

deflect :: Surface -> Player -> Player
deflect surface player = player { vel = vel' }
    where vel' = if deflectVelocity <= 0
                 then (vel player) - deflectVelocity .* (normal surface)
                 else vel player
          deflectVelocity = dot (vel player) (normal surface)

We now have a small decision to make. Our level comprises of a list of surfaces. When calculating we can either look for the first surface that intersects our player or look for all surfaces that intersect our player. It is more efficient to only grab one surface, and in most situations the player will only be colliding with a single surface. However, if our surfaces join, say to make a polygon, the hit detection around corners can be a little funky if we are not thorough. Let’s check them all, it’s easy to refactor later if we change our minds.

hitDetection :: Surfaces -> Player -> Player
hitDetection surfaces player = foldr deflect player $ filter (detect (pos player)) surfaces

That’s actually all the hit detection code. Everything else here will just be details of how we implement the rest of the game. One useful thing to write is a function to convert a line described by two endpoints to our surface datatype. We’ll use this to build an example level.

lineToSurface :: Point -> Point -> Surface
lineToSurface p0 p1 = Surface n o n0 o0 n1 o1
    where n = normalise $ rotate90 ( p1-p0 )
          o = dot n p1
          r45 = playerRadius * sqrt 2 / 2
          n0 = rotate45 n
          o0 = dot n0 p0 + r45
          n1 = rotate315 n
          o1 = dot n1 p1 + r45

Our example level is just a list of lines. We can easily convert that to a list of surfaces.

egLevel = [ ( (-400,0) , (-300,-200) )
          , ( (-300,-200) , (-200,-250) )
          , ( (-200,-250) , (0,-250) )
          , ( (0,-250) , (25,100) )
          , ( (25,100) , (50,-250) )
          , ( (50,-250) , (250,-250) )
          , ( (250,-250) , (400,-100) )
          ] ++
          [ ( (-280,220) , (-120,220) )
          , ( (-120,220) , (-200,200) )
          , ( (-200,200) , (-280,220) )
          ] ++
          [ ( (100,70) , (300,70) )
          , ( (300,70) , (300,50) )
          , ( (300,50) , (100,50) )
          , ( (100,50) , (100,70) )
          ]

egSurfaces = fmap lToS egLevel
  where lToS ( p0 , p1 ) = lineToSurface p0 p1

The gloss game implementation uses three simple functions for most of the legwork. We’ll implement these later as render, inputUpdate and simulationUpdate. The state of our world, or at least those parts of it which change, will be kept in a data type Player. The function render will take our player and use it to draw the game. With inputUpdate we can modify the game state whenever we receive and input action. Finally simulationUpdate will be fed an elapsed time interval and the current state with which to calculate the next step in the simulation of our world.

window = InWindow "Platformer" (200, 200) (10,10)
bgColor = black
fps = 60

main = play window bgColor fps initialPlayer render inputUpdate simulationUpdate

As mentioned, the world state is just our player datatype. Let’s implement some simple movement physics. The left and right keys will make our player accelerate in each direction and the up key will cause the player to jump.

speed = 200
jumpspeed = 300

inputUpdate event player
    -- Left Right Movement
    | EventKey (SpecialKey KeyLeft) Down _ _ <- event
      = player { acc = acc player + (-speed,0) }
    | EventKey (SpecialKey KeyLeft) Up _ _ <- event
      = player { acc = acc player - (-speed,0) }
    | EventKey (SpecialKey KeyRight) Down _ _ <- event
      = player { acc = acc player + (speed,0) }
    | EventKey (SpecialKey KeyRight) Up _ _ <- event
      = player { acc = acc player - (speed,0) }
    -- Jumping
    | EventKey (SpecialKey KeyUp) Down _ _ <- event
      = player { vel = vel player + (0,jumpspeed) }
    | otherwise = player

We will render the player as a red circle. This circle will be stacked on top of some lines drawn to depict the level.

drawPlayer player = color rose $ translate x y $ circleSolid playerRadius
    where x = fst $ pos player
          y = snd $ pos player

drawLevel = Pictures . fmap drawLine
  where drawLine ( p0 , p1 ) = color white $ line [ p0,p1 ]

render :: Player -> Picture
render player = pictures [ drawLevel egLevel , drawPlayer player ]

Finally we can use our collision detection function in the simulation.

velocerate dt player = player { pos = pos' }
    where pos' = pos player + dt .* vel player

resistance = (0.95,1)

accellerate dt player = player { vel = vel' }
    where vel' = resistance * vel player + dt .* acc player

simulationUpdate dt = velocerate dt . hitDetection egSurfaces . accellerate dt

That’s it. Now you can compile and play around with the simulation.