I recently read Frozen Fractal’s blog post on discrete 2D grid physics, and it piqued my interest. My current project operates under a similar (but simplified) set of rules, so I thought it would be fun to try to solve this problem in case I want to have more complicated interactions in the future. I was surprised at how elegant the solution actually turned out to be!
I’m not going to go over all the rules again as you can read them here, but to quickly recap the points relevant to this algorithm:
- Blocks are moved by forces
- Forces can add up from multiple blocks pushing in the same direction
- Similarly, forces in opposite directions can cancel each other out
- Forces transfer from block to block recursively
For this example, we’re going to be solving the arrangement below:
The arrows depict the direction a block is pushing on. In this example, all blocks push with a force of 1, though the algorithm works with any initial force.
Blocks with no arrows are exerting no force. Intuitively, we can immediately tell what should happen:
A, B, and D don’t move anywhere, as A and D have canceled out their movement, and C moves left with a force of -1. Solving this problem with an algorithm however has proved deceptively difficult. Below is my own attempt to create a generic solution applicable to all situations.
Discover what objects can possibly exert force in a direction by recursively colliding objects in their direction of motion, starting from all blocks that have an initial force. The purpose of this is to construct a tree of potential force transfers, not an actual force diagram. When searching, don’t include any object more than once to avoid creating loops in the tree.
The actual method of this search doesn’t matter too much, as long as it correctly maps out the force relationships between all objects. I’m being purposefully verbose in this article for the sake of clarity, but you could optimize this function quite a bit. I haven’t thought to much about implementation but I’m fairly certain that you can do most of step two during step one.
This boils down the blocks on the grid into a simple tree of relationships, something much easier to operate on.
Nice and clean!
Notice how for the connections between A and B, and B and D, arrows flow both directions, but for B and C, the arrow only goes from B to C and not the other way around. This is because C, which is exerting a force of -1, has no way to transfer force to B. B has a way to transfer force to C however, through D.
For any node, solve its potential forces by tracing all incoming forces.
The first step is to show all the known forces acting on the system from the outset. A block that exerts force can be said to have a force being placed on it by “somewhere” (as opposed to a force being placed on it by another block). You can depict this by adding a few extra virtual “links” to the graph:
Next, we need to pick a node to solve. It doesn’t really matter where we start, so I’ll start with D. In order to solve D, D needs to know all of the forces that act on D. It has a known force of -1 acting on it, but it has an unknown force acting on it from B. D asks B what force B is enacting on it.
B doesn’t know either, as it has its own unsolved forces, D→B and A→B. There is no C→B, as C cannot exert force on B.
Important!! Since D is the one asking, B ignores the link D→B in its calculations. This is true for any step in this algorithm. All calculations are done from the perspective of the node that’s asking for them, and the node’s own forces are not considered in those calculations. This leaves B with only one valid link, so it asks A what force is being transferred across the A→B link.
A has one known force (+1→A), and one unknown force (B→A). We’re ignoring B as it’s the one asking however, and this leaves A with a known force of +1. A can pass this information back to B, and establish the A→B link as having a force of +1. Looking at the paths we’ve traced so far, the graph looks like this:
Since we’re still ignoring D, that question mark becomes easy to solve. The only force on B is the known force of +1 from A, so we can solve the B→D link as well. D has successfully resolved all of its incoming forces, and can be totally solved by adding them all up: +1 from B→D and-1 from the universe = 0 total force. D won’t move anywhere.
Again, we can pick any new node to solve. Node A is solved exactly the same way as D was. A asks B what the force of the B→A link is. B doesn’t include the A→B link in its search and is therefore left with D→B, which is unknown. B asks D what the value of D→B is. Ignoring the B→D link, D is left with the known force of -1→D, and can set D→B to -1. This is important to note, as the solved value of 0 for D doesn’t affect the forces it passes on for queries.
B can then solve the B→A link with a -1, leaving A with a +1 from +1→A and a -1 from B→A. These cancel out to 0. A’s going nowhere fast.
With A solved, all of the incoming forces affecting B have been solved as well, and we can simply plug in the sum!
Last we can take care of C. C has one known force -1→C, and one unknown force, B→C. C asks B to solve the B→C link. This is easy, as B already has known values for all incoming forces. The +1 from A→B and the -1 from D→B cancel out to 0, meaning that the B→C link has a force of 0.
Now that all forces are known for C, we can total them up and set C’s force. 0 (B→C) + -1 (-1→C) = -1. C will be able move to the left.
If we overlay these numbers on our original animation, we can see that it matches up to the expected motion!
Here’s another couple of examples to show how the tree looks in different scenarios:
This same technique obviously works in both axis. The next step would be how to use these forces to resolve the final motions, but that’s outside the scope of this article. Walls/objects with mass can also be integrated into this model relatively easily.
Update 27.5.2017: Well, I thought it would be relatively easy. The rabbit hole of this problem keeps getting deeper, but I’m only getting more and more invested in completely solving it. I’ll be making a follow-up post sometime soon™.
TL;DR: Any given arrow has a force that is equal to the sum of all the forces of the arrows behind it. An object’s final motion vector is the sum of all the arrows flowing into it.
Hope this helps!