Discrete physics on a 2D grid: setting the stage
For a new game I’m working on, I need some 2D “physics” that work in discrete time and discrete space. In other words: every object consists of one or more blocks aligned to a square grid, and time advances in turn-based steps. If you’re thinking of Sokoban, you’ve got the idea:
Image by Carloseow at English Wikipedia, CC-BY 3.0
But unlike Sokoban, there can be multiple actors applying forces, and forces are transferred between objects too. It turns out that this is complicated!
Here is an example situation. The black arrow shows an external force being applied to the red box, which causes it to push all the other boxes along.
The rules
These are the rules I want the system to obey:
Rule 1: Objects move in response to forces
A force is described as just a direction, and is considered “infinitely strong” (but not so strong it can push objects into walls). This means that the mass of objects is irrelevant.
There is also an implicit “friction” that brings objects to rest at the end of the timestep. If we want them to keep moving, we have to keep applying a force to them.
The red box moves due to the force, but the orange box is being pushed into the wall and stays put:
Forces can cancel each other out:
And they can add up:
Rule 2: Forces are transferred from objects onto other objects
If object A pushes into B, B pushes into C, and C can move freely ahead, then all three will move. We’ve already seen an example of this at the start of this article.
Conversely, if anything is blocked, the entire chain of movement cannot happen:
Rule 3: During a time step, an object can move at most 1 axis-aligned square
Rotation does not exist in this world, even though this long object would happily rotate in real life:
Movement by more than one square is not possible, even if multiple forces act in the same direction:
Rule 4: Resolve ambiguities sensibly
There are many cases in which these rules do not give rise to a single, unique solution. In those cases, the system should do something sensible and deterministic.
For example, if both a horizontal and a vertical force are applied to an object, and both could result in movement, we have two possible outcomes, neither better than the other. (Remember, diagonal movement is forbidden.)
Either horizontal movement wins, and there is no way for the orange object to move forwards:
Or vertical movement wins, and the red object has no way to move:
A similar situation occurs when two objects want to move into the same space simultaneously — we arbitrarily gave precedence to the orange object in the example below:
Rule 5: No overlap during animation
This is not a valid solution:
Even though the “before” and “after” states are valid, and sensibly follow from the forces, the resulting animation shows the objects overlapping. Instead, the red object should wait for its turn, which might come in the next timestep:
Note that this rule makes the situation ambiguous, so it’s also fine if the red object gets to move first:
Also note that overlaps during animations are only an issue when the movement is orthogonal (left/right vs. up/down). If both objects move along the same line, we’re fine:
Implementation
This post laid out some of the basic rules I want my physics system to obey. In next week’s post, we’ll take a stab at writing an algorithm to implement these rules, and discover that it’s not as easy as it seems!