Discrete physics on a 2D grid: a dissatisfying solution

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

In last week’s post, I discussed my first two failed attempts at creating something like physics on a 2D grid. It gathered a good deal of attention on Reddit, with several replies from people claiming to have solved it, only to introduce new problems. As I already knew, this problem is surprisingly tricky!

However, the amazing /u/Madgvox (who has worked on something similar before) sunk their teeth into it, and came up with an approach that looks quite promising. It still needs work though, so I’ll save it for a future blog post.

The post you’re reading now was written before all that, and approaches the problem from a very different angle. Even though it didn’t work out, I still think it’s worth sharing.

Attempt 3: SAT

After thinking about this problem for a while, it dawned on me that I might be approaching it wrong. Instead of a physics problem, I should be thinking of it as a logic problem. After all, we have particular constraints that need to be satisfied, such as: if object A moves, then object B must move in the same direction; if a force acts on object A, and object A can move, then object A moves; and so on.

This reminded me of the Boolean satisfiability problem, which is: given a Boolean formula (i.e. one with a bunch of variables, combined using and, or and not operations), assign true and false to the variables such that the entire formula evaluates to true.

Unfortunately, the Boolean satisfiability problem (known as SAT for short, not to be confused with the Separating Axis Theorem used in physics engines) is NP-complete, which means that there is no known algorithm to solve it efficiently, and the running time quickly gets out of hand even for smallish problems like my game’s.

Fortunately, I kept reading Wikipedia, and discovered that there is a more restricted form, known as the 2-satisfiability problem (2-SAT), which does have an efficient solution.

A 2-satisfiability problem may be described using a Boolean expression with a special restricted form. It is a conjunction (a Boolean and operation) of clauses, where each clause is a disjunction (a Boolean or operation) of two variables or negated variables.

If that makes your head hurt, you’re forgiven, but it’s really quite simple. Here’s an example that shows the shape of such a formula:

(a || !b) && (!a || b) && (b || c) && (c || c)

Here, rather than using the logician’s notation of ∧ ∨ ¬, I use the programmer’s notation of && || ! respectively. Let’s try to find a solution. Each of the clauses must individually be true for the entire formula to be true, so.

• Because (c || c) must be true, c must be true.
• We now know that (b || c) is satisfied, so this doesn’t give us any information about b.
• From (a || !b) && (!a || b), we can infer that if a is true, then b must be true, and vice versa. But both can also be false. In other words, a == b.

As you can see, there are two possible solutions here:

            a     b     c
Solution 1: true  true  true
Solution 2: false false true

Rather than our manual inferences above, elegant algorithms exist to find a solution in linear time, which is as efficient as they get. I won’t explain the algorithms here, but the Wikipedia page has great explanations that you should read. It’s not at all rare for multiple solutions to exist, and as we’ll see, this will turn out to be important.

From physics to 2-SAT

Now back to our “physics” problem. How do we formulate this as a 2-SAT problem? Let’s start with our variables. We define aL, aR, aU and aD to mean “object a moves left, right, up, down” respectively. We have four such variables for each of our objects: bL, bR and so on.

The first rule, which is so obvious that I almost forgot it, is that an object can only move in one direction at a time:

(!aL || !aR) && (!aL || !aU) && (!aL || !aD) &&
(!aR || !aU) && (!aR || !aD) && (!aU || !aD)

For each pair of directions, this says that both cannot be true at the same time. This has five solutions: either all four directions are false, or exactly one of them is true.

Let’s add a rule to say that objects can push each other. Consider this situation, regardless of forces:

If a moves right, then b also has to move right. Conversely, if b moves left, a also has to move left. In the form of a formula:

(!aR || bR) && (!bL || aL)

Note that these are just implications in disguise, so a more readable form is (aR → bR) && (bL → aL).

Next up is the condition that objects cannot move through walls:

Of course what we want is simply !aR, but we need to pour it into the common form of a 2-SAT clause:

(!aR || !aR)

Finally, preventing overlaps of all sorts can be expressed elegantly as well:

Here, we just want to prevent a and b both moving into the square in the middle. So what we need is !(aR && bL), and by applying De Morgan’s rule we can put this into 2-SAT form:

(!aR || !bL)

That should give you an idea of how this “physics” problem can be expressed as a “logic” problem instead.

Adding forces

If you’ve been paying attention, you might have noticed that the “forces” are never mentioned in the 2-SAT formulation at all! Why is that? The trouble is that a force might not always have an effect; not all forces are “satisfiable”. Imagine we simply said “if a force to the right acts upon a, add a clause (aR || aR) to the 2-SAT problem”. If we did that, and a was being pushed into a wall, there would be no valid solution: aR would have to be true and false at the same time.

You might think we can express forces in our SAT formula regardless. For instance, if a force to the right is acting on object a:

(aR || !a_can_move_right)

The problem with this is, that a_can_move_right is itself a complex construct, potentially depending on the motion of many other objects. It might be possible to express it in 2-SAT form, but I’m not sure. I think we’d need an additional four variables per object: acL, acR, acU, acD which describe whether the object can move in that direction. But how do we ensure that these variables are set to true unless they are forced to be false?

But there’s another problem: expressing the absence of forces. If a is sitting in the middle of a room, with no forces acting on it from anywhere, setting aR to true is still a perfectly valid solution to the problem as formulated so far. But that means the object would spontaneously move to the right! So for objects on which no external force is acting, we need clauses along the lines of:

(!aR || a_must_move_right)

Perhaps it could work, if we also add variables amL, amR, amU, amD to express whether an object must move in that direction in response to other objects’ motions. But again, how do we ensure that these are set to false unless forced to be true by another object’s motion? We’ve just recreated the same problem again.

And either way, the adding up and cancelling out of forces is nowhere to be seen in this formulation, and I don’t see how to incorporate it.

So my idea was: use the 2-SAT problem just to describe which solutions are valid (result in no overlaps), while the forces define which solution is the best. We can define “best” in many ways: the solution in which most forces are satisfied, or the solution in which most objects move.

This approach finally fell down because of two reasons.

Measuring quality

Firstly, it turns out to be really hard to define a good metric for how “good” a solution is. For example, if we go with “most forces satisfied”, then this will still happen:

This satisfies the force on the red object, so that’s 1 force satisfied, whereas if nothing moved, then 0 forces would be satisfied.

How about if we add a penalty of -1 if a force is extremely “dissatisfied”, i.e. an object moves backwards against its force? Then both solutions are equally good: 1 for moving forwards and -1 for moving backwards adds up to 0, but a solution where both stay put also has a score of 0. So which do we pick? Remember, we want to do something consistent and somewhat predictable, in order not to surprise the player.

If we make the penalty for being “dissatisfied” stronger than the score for being “satisfied”, say 2 instead of 1, we solve this ambiguity, but run into other issues:

Now this situation is ambiguous: if everything moves to the right, we have a score of 1 for the leftmost two blocks, and a penalty of -2 for the rightmost block, again ending up with a score of 0. No matter which value we pick for the penalty, you can always construct a situation in which it doesn’t quite work out.

Efficiency

The other issue that eventually killed this attempt is efficiency. I previously wrote that 2-SAT can efficiently be solved, in linear time. However, the SAT problem is officially formulated as “determining if there exists an assignment that satisfies a given Boolean formula”. It just tells you whether a solution exists, but doesn’t necessarily tell you what the solution is! Fortunately, 2-SAT can efficiently produce a solution as a side effect of its calculations. Unfortunately, that solution happens to be really stupid and not the one that I want, because it can make objects move even in the absence of any forces.

I thought about modifying the algorithm to give me a list of all possible solutions, so I could pick the best one (although, as we saw, “best” is hard to define). But then it dawned on me: even though 2-SAT runs in linear time, the number of solutions can be exponential! As a simple example, consider n blocks that are free to move anywhere. Each can make one of five choices: move in some direction, or stay put. So this situation has 5^n solutions, which quickly gets unwieldy even for moderate values of n; even for n = 10, there are already almost 10 million solutions, and this is definitely a situation I would expect to happen in the game in practice.

So, even though the SAT-based solution ultimately failed, it still proved to be very valuable for my thought process. I had learned that this problem is much harder than it seemed at first sight, and that the rules I had drafted (forces add up and cancel out) were perhaps not as well-defined as I would like.