Discrete physics on a 2D grid: back to basics

Fri, 7 Jul 2017 by Thomas ten Cate · Comments
 Game Development, Programming, Algorithms

Last week, I talked about a fairly sophisticated attempt at solving my 2D discrete physics problem, which ultimately turned out to have unfixable flaws. But I need this problem solved for my game, so I decided to relax my requirements for the time being.

This is just to get something up and running, so I can continue working on the rest of the game. I’ll probably revisit this later and come up with a better solution. I did some experiments in Infinifactory and found that that game does solve it properly, so it’s possible even in 3D!

Attempt 4: Back to basics

The change in requirements I made is this: forces don’t have to add up or cancel out. This was a nice-to-have from the beginning, because I wasn’t certain it would be needed for gameplay. If it turns out to be important, I can always revisit later.

This makes the original algorithm from Attempt 1 viable again: applying each force in turn, but keeping track of which objects have moved to avoid moving them more than once in the same time step. So we do get this unexpected result:

But if we do this naively, the red object will still be the first to move in the next time step:

So to make it more fair, I changed the order in which forces are being applied. Instead of visiting the objects in some fixed order, this code visits force directions in a fixed order. And it alternates that order every time step:

def force_directions(now):
  if now % 2 == 0:
    return [up, down, left, right]
  else:
    return [right, left, down, up]

def time_step(now):
  for force_direction in force_directions(now):
    for force in forces:
      if force.direction == force_direction:
        if can_move(force.object, force):
          move(force.object, force)

So if the red object pushes the orange in a particular time step, the orange one will take precedence over the red one in the next, and push it back to where it came from:

This results in the two blocks pushing each other back and forth. It’s not a great outcome, but it’s acceptable for now. As said, I’ll probably improve this later. And of course I’ll document the solution in a future post!