We just saw how to model the movement of the worker using graphs — can we use the same idea to model the movement of crates as well? In theory, we could define a graph of game states in which the neighbors of each node are those states that can be reached either by moving the worker or
by pushing a crate. Given this graph, we could then solve a level by searching for a path from the level’s initial state to the nearest game state in which every crate is located on a goal.
As appealing as this solution may appear, it has a serious problem: For all non-trivial Sokoban levels, the resulting graph is so large that we quickly run out of memory when we attempt to traverse it using breadth-first search. In the case of Level 1, for instance, the
optimal solution requires 230 steps. Before breadth-first search reaches any node that is 230 steps away from the start, however, it has to visit every game state that is reachable in 229 steps or less, of which there are millions. And since breadth-first search guarantees that every node is
visited exactly once, all those states must be kept in memory until a solution has been found. If we want to model this puzzle as a graph traversal problem, we therefore have to find a way to reduce the size of the graph significantly.
The first important insight is that the worker always alternates between two actions: moving to the next crate and then pushing it one step in the direction of movement. Moving toward a certain crate is easy: we already saw how to do this using the move graph in the previous
section. We can therefore disregard all steps in which the worker doesn’t push a crate and remove the associated nodes and edges from the graph. We call the resulting graph the push graph: every node in this graph represents one configuration of crates, and every edge indicates one way to push a reachable crate to a neighboring square. We can solve a level by searching for a path through
the push graph that leads from the starting state to a state in which all crates are on a goal.
Figure 8.5 shows a small Sokoban level and its direct neighbors in the push graph. In the starting state \(S\), there are six ways to push the level’s two crates: The left crate can be pushed up or down, and
the right crate can be pushed in all four directions. The node therefore has six neighbors in the push graph. Notice that when following an edge in the push graph, the worker “jumps” to its new position, which is always the original position of the crate that was pushed.
Figure 8.5 Illustration of the push graph. The game state shown in the center has six neighbors, one for each possible way of moving one of the two crates. Only the movement of crates is modeled explicitly. The graph continues in all
directions: Each of the six outer nodes has additional neighbors.
In contrast to the move graph, most edges of the push graph are directed since pushing a crate is usually not a reversible operation. In Fig. 8.5, the only edge that goes in
both directions is the one to the node labeled E. This node is reached by pushing the left crate down, and after pushing the crate back up we return to the starting configuration. In contrast, there are no edges from A or B back to the central node. Even though the right crate
can be moved back to its original position, the worker ends up in a different location than in state S.
Listing 8.9 defines the push graph as a Graph with nodes of type GameState. Since the graph is typically enormous in size, we leave the nodes() method unimplemented. The implementation of neighbors() computes the list of game states that can be reached by pushing a single crate. We first iterate over all
reachable positions in the level by creating an instance of MoveGraph and traversing it using visitNodes(). For every reachable position we then call tryPush() to check whether there is a movable crate in one of the adjacent squares; if there is, we add the resulting GameState to the list of neighbors.
Listing 8.9ch8 / PushGraph
// A graph of game states that are one push apart.
public class PushGraph implements Graph<GameState> {
private final Level level;
public PushGraph(Level level) {this.level = level;}
// Computes game states reachable by pushing a single crate.
public List<GameState> neighbors(GameState state) {
var neighbors = new ArrayList<GameState>();
var moveGraph = new MoveGraph(level, state.crates());
moveGraph.visitNodes(state.workerPos(), index -> {
for (var dir : Board.ALL_DIRECTIONS) {
int crateIndex = level.moveIndex(index, dir);
var newState = state.tryPush(level, crateIndex, dir);
if (newState != null)
neighbors.add(newState);
}
});
return neighbors;
}
}
One notable detail is that the list of game states returned by this implementation of neighbors() is sorted by the distance of the crate being pushed from the worker’s position in state.
This is because Graph.visitNodes() is a variation of breadth-first search and therefore visits the nodes of the move graph in the order
of increasing distance from state.workerPos(). We will discuss in Exercise 8.6 how this ordering affects which path through the push graph is discovered first.
The purpose of the tryPush() method used in the implementation of neighbors() is to
push a crate in the specified direction and return a new GameState if successful (Listing 8.10). Moving a crate is only possible if there actually is a crate at position cratePos and
if the square next to the crate isn’t blocked by a wall or another crate. If this is the case, we compute a new set of crate positions newCrates by replacing the old crate with the new one. If there is no movable crate nearby, tryPush() returns null.
Listing 8.10ch8 / GameState
// Push the specified crate, return new game state if successful.
public GameState tryPush(Level level, int cratePos,
Board.Direction direction) {
var newCrate = level.moveIndex(cratePos, direction);
if (newCrate == -1) // outside of level?
return null;
if (crates.contains(cratePos) && !blocked(level, newCrate)) {
var newCrates = new BitSet(crates);
newCrates.remove(cratePos);
newCrates.add(newCrate);
// Create game state with worker at 'cratePos'.
var newState = new GameState(cratePos, newCrates);
if (!newState.hasDeadlockAt(level, newCrate))
return newState;
}
return null;
}
public boolean blocked(Level level, int pos) {
return crates.contains(pos) || level.walls().contains(pos);
}
As a simple but important optimization, tryPush() rejects moves that cause a deadlock, an unsolvable game state in which one or more crates are stuck and can no longer be moved to any of the goals. The simplest kind of deadlock occurs when a crate is pushed into a corner, in other words, if the crate completes a \(2\times 2\) block of walls or other
crates. The implementation of causesDeadlock() in Listing 8.11 tests whether a game state has such a \(2\times 2\) block in the
neighborhood of crateIndex. If crateIndex is a goal square, the method immediately returns false because deadlocks are only problematic for crates that still need to be moved. Otherwise, it checks whether crateIndex is the lower-right, lower-left,
upper-right, or lower-right corner of a \(2\times 2\) block of walls or other crates. The two nested for loops iterate over these four directions, with the loop variables xOff and yOff forming the offset pairs \((-1, -1)\), \((-1, 1)\), \((1, -1)\), and \((1, 1)\). Each of these
offsets is then used to test whether the three squares next to crateIndex in a certain direction are all blocked.
Listing 8.11ch8 / GameState
// Check if the crate at 'crateIndex' is part of a 2x2 deadlock.
private boolean hasDeadlockAt(Level level, int crateIndex) {
if (level.goals().contains(crateIndex))
return false;
int x = level.getX(crateIndex);
int y = level.getY(crateIndex);
for (int yOff = -1; yOff <= 1; yOff += 2) {
for (int xOff = -1; xOff <= 1; xOff += 2) {
if (blocked(level, level.index(x + xOff, y))
&& blocked(level, level.index(x, y + yOff))
&& blocked(level, level.index(x + xOff, y + yOff)))
return true;
}
}
return false;
}
This simple deadlock test is surprisingly effective: When solving Level 1, it reduces the size of the push graph and the number of nodes that must visited by a factor of almost 6, from 23 755 405 to 4 095 995! Even though there
are more complex deadlock patterns, using more sophisticated deadlock tests quickly hits a point of diminishing returns: Since the test must be performed for every game state that is examined, an accurate but time-consuming test can be slower overall than a cheap test that misses a few deadlocks.