Hit Detection with Polyhedra

Everyone knows polygons. Two dimensional shapes, straight lines, corners, etc. Less well known are polyhedral representations of (convex) polygons. This is an alternative way to describe a polygon that uses lines instead of corners. Typically it’s used in discrete geometry for multi-dimensional polytopes. Restricting ourselves to just two dimensions we can use polyhedra to create a slick hit detection algorithm.

Let’s create a simple platformer with the level built from a list of convex polyhedra.

Polyhedra

I’m using the word ‘polyhedra’ instead of polygon deliberately. Usually you would describe a polygon by giving its corners. This is intuitive and easy. Below the triangle has three corners, if you know what the corners are then you’re set.

An alternative is to instead describe the convex polygon by its edges. Any line in two dimensions divides the plane up into two halves, if we choose one of these halves we have a half space. By intersecting several half spaces we can also obtain the same triangle.

A common theme in discrete geometry is that some problems are easier to solve with vertices, and some with half spaces. We’ll use the half space representation to do some efficient hit detection.

Before continuing, note that convexity is a big deal. An object is convex if the straight line connecting any two points in the object is also in the object. If the terrain featured some non-convex features, we would have to slice it up into convex components.

If you write a polygon as a list of half spaces, then there is no reason why the result would have to be bounded. For our purposes that’s actually a good thing. For example, you could write the ground as a single unbounded polyhedron represented by the half space \(y < 0\).

Implementation

We’ll write a no-fuss implementation in Haskell using the Gloss library. This whole document is literate haskell, so you should be able to just copy and compile.

module Main where

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

import Data.List (maximumBy)
import Data.Function (on)

The edges of our polygons will described with half spaces using the equation \(a\cdot x = b\).

data Halfspace = Halfspace { normal :: Point , offset :: Float }
type Polyhedron = [ Halfspace ]

We’ll just roll our own rudimentary functions for linear algebra. If you’re doing this for real, use a proper library for vector arithmetic.

(.*) :: 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)

Our polyhedra are defined by a list of inequalities. A point lies in a polyhedron if it satisfies all the inequalities. This is a rather nice condition because we can test the inequalities one by one and jump to the next polyhedron the moment a single test fails. In a worst case scenario we have to run one test for each side of the polygon, but often we will use many less. We can express this very cleanly using the all function.

Firstly our player is just an entity with position, velocity and acceleration.

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

Then the hit detection is performed by comparing this player’s position to all the half-space inequalities.

dummyTest :: Polyhedron -> Player -> Bool
dummyTest poly x = all (0 >=) offsetDistances
  where
    halfspaceCompare x h = dot (normal h) x - (offset h)
    offsetDistances = fmap (halfspaceCompare (pos x)) poly

Once we determine that the point is inside a polygon, we need to make the collision mean something. The option I’ve chosen here is to deflect the player in the direction of the nearest edge. Assuming that we’ve normalised all the facet normals, the nearest edge is easy to find. It is simply the edge corresponding to the maximum value (or rather minimum negative value) in offsetDistances above. We will remove any velocity from the player in the direction of this closest side. To save calculating the offsetDistances twice, we may as well roll the hit detection and deflection into one function.

deflect :: Polyhedron -> Player -> Player
deflect poly x =
    if (all (0 >=) offsetDifferences)
    then x { pos = pos x - fst principleNormal .* snd principleNormal
           , vel = vel'
           }
    else x
    where
        halfspaceCompare x h = dot (normal h) x - (offset h)
        offsetDifferences = fmap (halfspaceCompare (pos x)) poly
        normals = fmap normal poly
        principleNormal = maximumBy (compare `on` fst) (zip offsetDifferences normals)
        vel' = if (snd principleNormal `dot` vel x) <= 0
               then vel x - (snd principleNormal `dot` vel x) .* snd principleNormal
               else vel x

Applying this deflection to all the polyhedra in our world just involves a fold.

multideflect :: [ Polyhedron ] -> Player -> Player
multideflect polys x = foldr deflect x polys

That’s actually it for the hit detection / maths. The rest of the code is just implementing some silly physics. We just fill in the functions for Gloss’ game function.

Before going on it’s worth mentioning that nothing we’ve done here is specific to 2d, these same calculations could work to make a 3d engine. In a real game you would definitely want to chop you world up into regions and only calculation detection for objects which are ‘nearby’.

main = play window bgColor fps initialPlayer render inputUpdate simulationUpdate

Let’s start with some basic parameters.

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

Input handling on the arrow keys, left and right to move, up to jump.

speed = 200
jumpspeed = 300

inputUpdate :: Event -> Player -> Player
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

Rendering is pretty simple.

playerRadius = 10

playerRender :: Player -> Picture
playerRender player = color rose $ translate x y $ circleSolid playerRadius
  where (x,y) = pos player

render :: Player -> Picture
render player = translate (-480) (-270) $ pictures [ playerRender player , background ]

We’ll draw the background and create a list of polyhedra to collide with later. First, the physics is super nice.

gravity = -300
decell = (0.95,1)
simulationUpdate :: Float -> Player -> Player
simulationUpdate dt player = velocerate dt $ multideflect hitPolys $ accellerate dt player

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

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

Now we can generate an example world.

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

It’s much easier to write out the polygons from their vertices, so we need some functions to covert to the representation used for our hit detection.

lineToHalfspace :: Point -> Point -> Halfspace
lineToHalfspace p0 p1 = Halfspace n o
  where n = normalise $ rotate90 $ (p1-p0)
        o = dot n p0

vPolyToHPoly :: Path -> Polyhedron
vPolyToHPoly points = take l $ spaces $ cycle points
  where l = length points
        spaces (p0:p1:ps) = ( lineToHalfspace p0 p1 ) : spaces (p1:ps)
        spaces [] = []

The example data is used to generate both a background and a bunch of collision polygons.

egData :: [ [ Point ] ]
egData =
  [ [ (797.14286,366.42857) , (867.14286,366.42857) , (849.28572,350) , (817.85714,346.42857) ]
  , [ (857.85714,274.28571) , (897.14286,232.85714) , (918.57143,155.71429) , (901.42857,122.14286) , (845,115) , (803.57143,138.57143) , (795,175.71429) , (810,261.42857) ]
  , [ (727.81491,387.89858) , (703.57125,312.64221) , (665.18545,284.86302) , (613.1626,323.75389) , (600.03061,387.89858) ]
  , [ (196.97975,434.36559) , (325.7742,434.36559) , (289.91378,417.69808) , (240.92138,415.67777) , (211.62696,421.73869) ] 
  , [ (59.599,377.29198) , (109.09647,377.29198) , (91.418805,364.15999) ] 
  , [ (137.38075,320.72343) , (178.797,320.72343) , (157.5838,310.11683) ] 
  , [ (209.10158,241.42646) , (274.76149,241.42646) , (270.21581,206.07112) , (255.82113,180.31222) , (238.90107,174.75639) , (219.45564,209.35412) ] 
  , [ (68.185297,217.1828) , (155.05842,217.1828) , (131.82491,200.0102) , (88.388348,194.95944) ] 
  , [ (553.05851,-0.00003) , (368.20061,-0.00003) , (368.20061,72.73106) , (410.12193,202.03056) , (514.16765,248.49758) , (535.38084,208.59656) , (553.05851,114.14726) ] 
  , [ (520,114.14726) , (731.35044,105.56094) , (960,51.51777) , (960,-0.00003) , (520,-0.00003) ] 
  , [ (380,-0.00003) , (0,-0.00003) , (0,126.26915) , (149.50258,131.82499) , (295.9747,114.14732) , (380,72.73106) ] 
  ]       

background = color azure $ pictures $ map polygon egData
hitPolys = fmap vPolyToHPoly egData