The tile-based 2D platformer example I provided in Processing included a section on collision detection applicable to that tiled level structure. It included this diagram, showing 6 collision points in a hexagonal pattern, where red detects “left side”, green detects “from top”, blue detects “from right”, and yellow detects “from bottom”:
The large gap between the shoulder-height and thigh-height world detection on either side works fine for that case because square units in the grid-based world are taller than that gap:
In a game engine that has thinner pieces in the world, a character based on 6 points could easily pass through, or even become hooked on those thin pieces. Everyone’s Platformer, the engine I wrote to give away to HobbyGameDev readers (source code and all), includes just those sort of thin pieces:
Even though the editor for that game includes a grid snap mode, the pieces are in no way tiled, and by disabling the grid snap they can be placed with the same per-pixel fidelity as the mouse.
How is collision detection handled, in this case, to support world pieces of arbitrary size and placement?
Once again, as with the tile-based example, we’ll be relying on the age-old trick of waiting until after overlap occurs in logic, then correcting for the overlap before it has a chance to render incorrectly. That will be “collision”. (I.e. no predictive/extrapolation calculations!)
No matter how we place 6 points to define player collision against the world using the arrangement illustrated earlier, some thin piece could slip between them. We’ll use rectangles instead, to create solid collision regions within the player that don’t have gaps.
Mathematically and computationally, it’s simple to tell whether two rectangles are overlapping: two axis-aligned rectangles don’t overlap if and only if the left of either is right of the other’s right or the top of either is below of the other’s bottom.
Collision areas for player character in Everyone’s Platformer
Compare that to the illustration from earlier. Once again, overlap with red implies a collision from the left, prompting the character to reposition. Since it’s now a rectangle-to-rectangle collision we’re handling, that translates to putting the left edge of the red at the same coordinate as the right edge of whatever it collided with. Green checks for top collisions, blue for right collisions, and yellow for bottom collisions.
Since the side bumped is evident by which rectangle overlaps a rectangle in the level geometry, in addition to repositioning, we can use that information in the code to affect character movement or state. When the green box on top is bumped, we know the player is hitting their head, and can cancel out whatever upward thrust they had from a jump. If it’s the yellow box on bottom, we know the player is currently on the ground – meaning they landed, if they weren’t on the ground the frame before. When handling collision with enemies, we can use whether it’s the bottom collision box to determine whether the player “jumped” on them (which defeats any non-spiked enemy).
Note here that the left/right edge detection does not occur from head to foot. This allows stairs to be climbed. When the player moving horizontally overlaps that yellow lower section with a step less than waist-high, instead of being pushed back horizontally, the character is raised vertically.
Speaking of stairs: since this is not a tile based 2D platformer, we need a finer way to define the level geometry. In the Everyone’s Platformer engine we overlay axis-aligned rectangles (i.e. not rotated). As shown here, rectangles can be used in groups to simulate bumpy, uneven, and sloped terrain:
Collision areas for level pieces in Everyone’s Platformer
Hierarchy of Rectangles
Using 4 separate rectangles for the player character is a handy way to detect and respond to collisions from different sides, but it also means that we’re checking 4 times as many collisions as we need to. On any given frame, the player character is probably not touching more than a few things in the level (if any!) so before checking any of those 4 for collisions, we should first verify that there’s a collision with the greater rectangle that incudes all 4 of them:
Master bounding box for player character
Likewise, rather than check for collision against all 8 stairs on every set of steps, we can check first whether the player character’s master bounding box overlaps the master bounding box of those stairs. The dimensions of the level piece bitmaps – say, the image of the lumpy land platform – provide fine approximations for this purpose. (Were we to squeeze the bounding box any tighter, fitting strictly to collision rectangle boundaries, performance gains would be marginal at best, and we wouldn’t be able to use the same bounding box to detect whether a level piece is on-screen for rendering.)
A level with 16 sets of stairs would have checked the player against 128 rectangles (16×8) – but now can instead only check the player against 16 rectangles (1 per set), plus another 8 rectangle checks whenever the player is overlapping one of those 16. From 128 down to 16-24! Not a bad gain, and since the levels will have lots of enemies using collision detection comparable to the player’s, those gains will be multiplied manyfold.
Instanced Rectangles Hierarchies
Rather than have 8 rectangles in memory for every set of stairs, we can share the same 8 rectangles for every instance of stairs in the map. Once we determine that the player’s bounding box overlaps the bounding box for stairs, we translate the universal stairs rectangles according to the player’s position relative to the stairs that have an overlapped bounding box, then do a more detailed and exhaustive collision check.
In the Everyone’s Platformer source, LevChunkPrefab.as contains the list of collision rectangle coordinates that define a piece like stairs (the actual coordinates are defined in-editor, and saved/loaded to an external file), whereas LevChunk.as instances are for placement of individual copies of that prefab, plus a few other details: the instance’s location, and whether it’s mirrored.
To return to our earlier case of a level with 16 sets of stairs, even having optimized processing complexity by only checking player collision against individual steps (8 rectangles) when overlapping one of the 16 master bounding boxes for stair sets, with a lazy solution we might still have 128 rectangles in memory to describe those 16 sets, stamped into existence with each stair graphic added to the level. Instead, we accept a very modest additional bit of computation, that being a few additions and subtractions to translate coordinate spaces, in exchange for 1/16 the memory usage to describe all of those stairs.
(When used in 3D game engines, an approach very similar to this one is referred to as “static mesh” construction. It became the standard after Unreal Engine 2.0 used it in Unreal Tournament 2003 to complement traditional “brush work” – convex volume addition/subtraction – to define and decorate levels.)
Instanced Rectangle Hierarchy Quad Tree
A quad tree is a data structure that recursively subdivides space into quadrants, to reduce the number of comparisons required to identify which object(s) relate to a particular region of space. In first-person shooter engines, quad trees are still employed to optimize collision detection for large outdoor terrain; in the case of Everyone’s Platformer they’re used to greatly accelerate determining “which level pieces overlap [some bounding box]?”
Here’s a picture visualizing a quad tree data structure for points:
Practically speaking, it’s a way of organizing data so that we can do the following:
Is the physical location in question on the left or right half of the map, and is it on the top or bottom half of the map? The answer to that question (ex. “top-left”), answered by straightforward math comparisons, immediately excludes 3/4 of the space in the world, taking with it whatever collision pieces reside in those spaces. But it does even better than narrowing the search down by 75%, thanks to recursion. That is, the search algorithm then asks which corner within the current corner the target location resides in, ruling out 3/4 of the area that was remaining. It repeats that pruning until some minimum number of objects or a minimum dimension of space is being considered, at which point those can be iterated through for thorough collision comparison.
The Wikipedia article on quad trees provides a more mathematical explanation.
Details of how quad trees are specifically implemented for Everyone’s Platformer is out of the scope of this already lengthy entry, but the source is yours if you’re curious to take a look at it, tinker with it, etc.
To go one last time into the previous example of a level with 16 sets of stairs, each with 8 rectangles for steps, compared against a player character that has one master bounding box and 4 internal collision detection boxes, we no longer have to compare the player’s master bounding box to all 16 stair bounding boxes. The quad tree is generated immediately after the level is loaded into memory, allowing us to identify eligible stair set bounding boxes given the player’s bounding box by just a few quick comparisons to crawl the quad tree. In the ideal case of those 16 stair sets being evenly distributed in level space, the first quad tree comparison would narrow it down to 4 stair sets (“player is in the bottom-right, so we can ignore the stairs in the top-left, top-right, and bottom-left of the level”), and the second quad tree comparison would narrow it down to 1 (“player is in the top-right of the bottom-right… [ruling out the 3 other quadrants within this quadrant]”).
To review how the quad tree is used in this example:
- 2 steps are taken into the quad tree to determine which set of steps is near enough to consider collision (within the same quad tree division), performing each step as a rectangle intersection check.
- 1 check for rectangle intersection to determine whether the player’s bounding box overlaps the bounding box of the stair set in this box.
- If it does, 32 (4 player detectors * 8 step rectangles) potential rectangle intersections are checked, to see whether the player is bumping into the tall end of the steps, hitting the bottom of them from a jump under the stairs, or walking up them.
That means we can do now in roughly 35 rectangle comparisons what would have required 512 comparisons (16 * 8 * 4) to do by brute force. Per frame, per character (!).
There are a few ways that we could optimize this further were there any need to do so, but the gains are already considerable, and at this point the engine can handle a level with many collision groupings and collision detecting enemies without any performance issues.
Free Quad Tree Rendering Optimization
Bonus: in addition to optimizing object-to-level collision, quad trees can (and are) also used to determine which background and foreground detail art from the level overlaps the screen, and therefore needs to be drawn. Rather than crawling the quad tree to identify what intersects the player’s bounding box, we crawl the quad tree to identify what intersects a bounding box formed by the edges of the screen.
To clarify an earlier claim, “arbitrary size” is a bit of an exaggeration. A small object moving at a modestly high speed could pass right through a piece that’s too thin. That issue is known as “tunneling”. It’s a product of the trick we’re using of waiting until after overlap happens before correcting for it, then handling that overlap as the sign of collision.
Here is how a ball (red) moving vertically at a constant speed (green) is intended to collide with a stationary wall (blue):
The ball and wall are thin enough – or conversely the speed is fast enough – that if the ball (red) happens to be coming from a different origin, it can pass right through the wall (blue) in the vertical space it crosses between one logic frame to the next (green):
The exact same ball, wall, and speed are shown there as in the first case, but the ball passes clean through it in the second case, since the ball doesn’t overlap the wall on an exact multiple of its speed from its starting position.
There are mathematical ways to detect and properly handle tunneling. For example, since Ghosts in the Machine involves high speed objects being blocked by thin paddles, I used ray-casting each frame to determine the intersection between a ray (the ball’s next movement step, from its current position) and each polygon that it might run into (bricks/paddles), acting on whatever collision point was found closest to its current position that frame.
Screenshot from Ghosts in the Machine (inspired by Atari Warlords)
Fun fact: The official Warlords on Atari 2600 has tunneling glitches.
But the simplest way to avoid tunneling – and the method used by most 2D platformers, including Everyone’s Platformer – is to just enforce safe upper bounds on speed and design with safe lower bounds on sizes. None of the enemies are 5×5 pixels and moving at 30 pixels per frame, because odds are good that they would tunnel clean through an 8×64 or even 16×64 pole in the level. (Quick aside: ray-casting is the most common means of implementing bullets; to support bullet time slo-mo, Max Payne was among the first few games to simulate bullet collision physics rather than computing an instantaneous line.)
In the Player.as constructor from Everyone’s Platformer, these lines:
_collisionSideT.height = c.PLAYER_JUMP_FORCE+5;
_collisionSideB.height = c.MAX_FALL_SPEED+5;
Show setting the player’s top collision detection box to be larger than the force the player applies when jumping (i.e. the maximum vertical speed achieved), and the bottom section is defined to be larger than the constant used as the player’s maximum fall speed. These are rather over-engineered (safe) margins, but they show an example of avoiding the tunneling effect. Were the player able to fall too quickly into a surface with too thin of a bottom detection area on the player, such that the left or right detection area caught the ground after the player’s feet tunneled through it, in a disorienting glitch the player character would be instantly teleported (!) to the left or right edge of the colliding rectangle since it would react to what seems like a collision “from the side”.
Player Control Quirks
As one final note, the player has a timer that ticks down for 6 cycles after the character has left the ground without initiating a jump (ex. running off the edge of something, or bounding down stairs). Until that timer reaches zero, the player can still initiate a jump, and the player is pulled down with a little extra force. These two strange adaptations are implemented to allow the player to run smoothly downhill instead of hopping downhill, to hug the ground when moving over uneven surface, and to be able to successfully jump if briefly mid-air from slipping between contact with the ground while running down steps.
There are other solutions to this problem, varying by the data structure and forms used for level definition – but for a rectangle-based 2D Platformer engine like the one included here, it works well.
Audio tip: that 6-cycle timer is also used to determine whether the player has been off the ground long enough to warrant an impact sound when establishing fresh ground contact.
Download the Source! Compile It! Try It!
If you’re reading this without compiling the source, you’re missing out on the best part. The code can be used on Mac, PC, or Linux, and the compiler is free and quick to set up (no need to buy Flash to make Flash games!).
Learn and practice team game development with Gamkedo Club.
Membership worldwide. Professional support. Proven process.
Subscribe by e-mail to receive weekly updates with Gamkedo.Community interviews and YouTube training videos for game developers!