/now /links /thoughts

a simple collision resolution algorithm for 2D action games

28 Mar 2024

I recently implemented a simple 2D AABB collision resolution algorithm that works fairly robustly. It still has a few failure cases, but none that have been relevant in the types of games I write (top-down games with a grid map and simple platformers).

(Try out the demo below! WASD moves actors, left click adds new tiles, right click adds new actors)

Demo of the collision algorithm
  • Left click: add static collider
  • Right click: add dynamic collider
  • WASD: move dynamic colliders

Constraints/limitations of this implementation:

  • AABB only. Only axis aligned rectangles are supported.
  • Dynamic object against immovable static objects only. No dynamic/dynamic interactions – if you need that, use box2D.
    • For action games you don’t generally want to open the can of worms that is dynamic/dynamic collision resolution. Look up how hard it is to implement a simulation that handles stacked boxes properly if you don’t believe me :P
  • Discrete resolution. Fast objects can tunnel and generally be problematic.

But these things work:

  • Collide and slideeeeeeee
  • Floating point coordinates 1
  • Fixed sized tiles or arbitrarily sized static AABB colliders (with limits, see below)
  • Wall/floor sliding without getting caught or hitching on colliders that are placed next to each other on a grid
  • Correct collision resolution with or without gravity (no need for hacks like handling Y first then X)
  • Very simple implementation

Here’s the algorithm pseudocode:

loop N physics substeps:
  I = find all rectangular intersections of colliders that overlap between the map and the actor_aabb
  R = search I for the rectangle with the largest area
  # move along the smallest axis to resolve the intersection
  if abs(R.width) < abs(R.height):
    actor_aabb.x += R.width
    actor_aabb.y += R.height

And here’s the Python implementation I used this in my recent jam submission:

def resolve_map_collision(map_aabbs, actor_aabb) -> Optional[vec2]:
    """Fix overlap with map tiles. Returns new position for actor_aabb."""
    # internal copy of actor_aabb that will be mutated
    aabb = copy_rect(actor_aabb)
    if map_aabbs:
        for i in range(2):  # run multiple iters to handle corners/passages
            most_overlap = max(
                (get_signed_collision_rec(r, aabb) for r in map_aabbs),
                key=lambda x: abs(x.width * x.height),
            if abs(most_overlap.width) < abs(most_overlap.height):
                aabb.x += most_overlap.width
                aabb.y += most_overlap.height

    new_pos = vec2(aabb.x, aabb.y)
    old_pos = vec2(actor_aabb.x, actor_aabb.y)
    return new_pos if new_pos != old_pos else None

(There’s also a JavaScript port that runs the demos on this page – just view the source if you want it :))

The key is to pick the collider with the largest overlap before fixing the collision using the axis of smallest intersection. If you iterate over the colliders in an arbitrary order, you end up getting stuck on the edges of certain colliders rather than smoothly sliding over them.

oscillation issues

If you play around with the demo, you might notice some glitchy behavior when Snap to grid is disabled. Moving an actor into a passage that’s just slightly too small will cause jitter.

Oscillation setup diagram
How an oscillation is triggered

It’s easy to get in this state. When a fast-moving actor careens into an opening that isn’t wide enough for it to fit through, the algorithm considers resolving on the vertical axis (black arrow in the example picture) or horizontal (gray arrow).

Since the horizontal axis is shorter, it fixes the collision with the box on the left, only to push it into the box on the right, and so on, resulting in infinite oscillation.

Example of oscillation issue

I think the fix is to undo the last velocity move if it results in a position where no adjustments resolve all contacts. Or you could try using the alternate axis to fix up the position if it doesn’t result in a collision. In my experiments this did work, but also introduced some weird popping when going over small bumps which isn’t desirable. I might expand the algorithm a bit more if I find something that works better.

Another way to avoid the problem is to simply use a fixed size grid. Or with arbitrarily sized AABBs, require maps to be authored with openings that are larger than the actors. This is what I’ve done in my games and I think it’s a reasonable constraint. I’ll solve this properly if I have to, but I’d like to tackle a collide-and-slide implementation for 3D action games next time I take a crack at writing physics code. That’s a problem I haven’t found a solid implementation for yet.

  1. A lot of amateur game development advice online seems to treat floating points as the boogie man, but I haven’t hit physics issues that were to blame because of the float representation.

    I know it’s possible to see quantization issues in large game worlds and roundoff error can compound over time resulting in inaccurate simulation. But too often I see someone complain about jittery movement or phasing and then immediately jump to the conclusion: “ooh it’s floating point bugs”, without any evidence. Even though floats are a bit weird, they’re still deterministic and understandable.