Discrete physics on a 2D grid: how hard can it be?

Wed, 21 Jun 2017 by Thomas ten Cate · Comments
 Game Development, Programming, Algorithms

In the last post, I described my requirements for a 2D discrete physics system I’m working on. Now that I’ve laid out what the system should do, let’s turn to the implementation.

Given a space with some walls, a set of objects, and some forces being applied to the objects, we want to develop an algorithm to figure out what happens during the upcoming timestep.

Attempt 1: Force by force

Let’s start with a quick and dirty algorithm to get a feel for how this would work. We treat each force separately, regardless of other forces, and apply it recursively:

def time_step():
  for force in forces:
    if can_move(force.object, force):
      move(force.object, force)

def can_move(object, force):
  # Walls can never be moved
  if object.is_wall:
    return False
  # Compute where the object would end up
  moved_object = object.moved_by(force)
  # For each pushed object, check whether it can move
  for pushed_object in objects_colliding_with(moved_object):
    if not can_move(pushed_object, force):  # recursive call
      return False
  return True

def move(force, object):
  object.move_by(force)
  for pushed_object in objects_colliding_with(object):
    move(force, pushed_object)  # recursive call

This gets the basic situation right: a single force being applied will result in a bunch of objects being pushed along. Where it breaks down is if there is more than one force:

Whoa, what happened there? First, the force on the red object was applied, and it pushed the orange object along. Then the force on the orange object was applied, and because it still has empty space ahead of it, it moves another square to the right.

Maybe we can fix this by keeping track of which objects have already moved during this time step, and forbid them from moving again? Nope:

Again the force on the red object was handled first, pushing the orange object away. But when we got round to the force on the orange object, it was not allowed to move again, so it lost its chance to push back against red.

Clearly, this approach is too simplistic. If we want forces to be able to add up and cancel out, we need to explicitly code that in.

Incidentally, there’s another problem with these recursive algorithms. In general, two blocks can have shapes such that they can push on each other:

This would lead to infinite recursion if we’re not careful. To break the cycle (and turn the force graph into a tree), we can keep track of which objects have already been dealt with, and bail out without entering the recursion as soon as we encounter one of these. I’ve left this code out for simplicity.

Attempt 2: Adding up forces

Let’s try an algorithm that performs two passes. In the first pass, it computes the net forces that act on each object, by adding up all the forces that act on them directly and indirectly. In the second pass, it moves all the objects according to the net forces acting upon them, until nothing can move anymore.

def time_step():
  # Reset net forces
  for object in objects:
    object.net_force = (0, 0)
  # Pass 1: Compute net forces recursively
  for force in forces:
    propagate_force(force.object, force)
  # Pass 2: Move objects according to their net forces
  change = True
  while change:
    change = False
    for object in objects:
      if try_move(object):
        object.net_force = (0, 0)
        change = True

def propagate_force(object, force):
  object.net_force += force
  moved_object = object.moved_by(force)
  for pushed_object in objects_colliding_with(moved_object):
    propagate_force(pushed_object, force)  # recursive call

def try_move(object):
  if object.is_wall:
    return False
  if object.net_force == (0, 0):
    return False

  # Restrict net forces to the four allowed directions
  force = object.net_force.clamp()

  # Only move the object if the space ahead is free
  moved_object = object.moved_by(force)
  if objects_colliding_with(moved_object) == []:
    object.move_by(force)

This gets the above situations right. In the first case, the net force on the red object is (1, 0), so it wants to move right. The net force on the orange object is (2, 0), but this gets clamped to (1, 0) and it also moves by just one square:

And the cancelling out works because the net force on both objects is zero:

But we now have a more subtle problem. Look at this:

What?! Yes, this is what the algorithm says. The force propagates from the red block to the blue and teal ones, so we get a net force of (1, 0) on all three blocks. After that, the teal block doesn’t care that the blue block can’t actually push it forwards, so it happily flies off on its own.

How do we fix this? Somehow we need to keep track of the reason why the blue block had to move in the first place, and only move it if that reason is still valid. But in general, there is no single reason: multiple forces might be acting on it from different directions.

All in all, I didn’t manage to find a satisfactory way to make this algorithm work. Better luck next week?