The Sokoban solver we implemented in the previous section is able to find optimal solutions — optimal in the sense that they require the fewest pushes. Alternatively, the quality of a solution can also be measured by the total number of steps the worker has to take. In the following, we will refer to these
two criteria as “push-optimal” and “step-optimal.”
To appreciate the difference between these two measures, let’s compare the first steps of the push-optimal solution for Level 1 we constructed the previous section to the step-optimal solution:
.
u3l3uLUllDDuuruurDldldll3dr12R
(push-optimal)
u3l3uLUllD ll3dr12R
(step-optimal)
The first 12 steps are identical and are necessary to reach the upper room of Level 1, but once inside this room, the solutions diverge: In the step-optimal solution, the worker proceeds directly to the left room and starts to push the first crate to the goal area, but in the push-optimal solution,
the worker briefly stays inside the upper room and pushes two of the crates downwards. In principle, these two additional pushes are a good idea: Since the two crates have to be moved downward eventually, we might as well move them at the earliest opportunity. But if you also take the
worker’s total number of steps into account, moving the crates later — when the worker passes through the upper room a second and a third time — turns out to be more efficient.
How do we find a step-optimal solution? We already discarded the obvious idea — constructing a graph of all the worker’s possible moves — as impracticable when we discussed the push graph in the Section 8.3. It is therefore a better idea to start with the push graph and augment it with information about the cost of pushing a crate. One way to do this is to label every edge with a the number of steps required to reach the crate being pushed. A graph
in which edges are labeled with a numeric weight are called weighted graphs, so what we are looking for is the weighted push graph of a Sokoban level.
Figure 8.6 shows an extended version of the push graph from Fig. 8.5, in which each edge is now labeled with the number of
steps that are required to reach the target node. For example, the edge from S to F is labeled with 1 because the worker simply has to move one square up to push the crate; similarly, the label on the edge from S to A is \(4\) because the worker has to take a total of
four steps: one step down, two steps to the right, and one step up (drrU).
Figure 8.6 In the weighted push graph, the game state in the center is connected to six other states. The edges are labeled with the smallest number of steps the worker must take to reach and push the crate. Additional nodes of the graph are indicated by the
labels A1 to F5.
In a weighted graph, the weighted length of a path between two nodes is defined as the sum of all edge weights along the path. In Fig. 8.6, for example, the weighted length of the path
\(E\to {}S\to {}D\to {}D1\) is obtained by adding the weights of \(E\to {}S, S\to {}D\), and \(D\to {}D1\), which is \(5+4+3=12\). In this case, \(12\) steps are needed to obtain rearrange state E into state \(D1\). The shortest path between two nodes in a weighted graph is the path with the smallest possible weight. The problem of finding the step-optimal solution of a Sokoban level is therefore equivalent to finding the shortest path in the weighted push graph
that leads from the starting configuration to any configuration in which all crates are on a goal.
Before we consider the problem of finding shortest paths in a weighted graph, let’s first see how to represent and compute the weighted push graph itself. Similar to the way we handled regular graphs, we represent weighted graphs by an
interface called WeightedGraph that computes parts of the graph as needed (Listing 8.15). The main difference compared to the Graph
interface is that we have replaced the neighbors() method with an edges() method that
returns the collection of edges that originate at a given node. Each edge of a weighted graph is represented by the nested type Edge that stores an integer weight and the target node to which the edge leads.
Listing 8.15ch8 / WeightedGraph
// Basic interface for representing weighted graphs.
public interface WeightedGraph<N> {
record Edge<N>(N target, int weight) {
}
Iterable<Edge<N>> edges(N node);
default Iterable<N> nodes() {
throw new UnsupportedOperationException();
}
}
The weighted push graph can now be implemented as a WeightedGraph with nodes of type GameState (Listing 8.16). For a given node in the graph, edges() returns a list of Edges that point to game states that can be reached by
pushing a single crate. The weight of each edge is the number of steps that are required to reach that crate and push it to an adjacent square. In Listing 8.16, we first use scanLayers() to traverse the move graph of the current game state. Every layer we find corresponds to the set of positions that are at a certain distance from state.workerPos(). If, for any of these positions, there is a movable crate on an adjacent square, we create a new edge to the resulting game state. The weight of the edge is the distance of the current layer plus 1, since an additional step is necessary to push the crate.
Listing 8.16ch8 / WeightedPushGraph
public class WeightedPushGraph
implements WeightedGraph<GameState> {
final Level level;
public WeightedPushGraph(Level level) {
this.level = level;
}
public List<Edge<GameState>> edges(GameState state) {
var edges = new ArrayList<Edge<GameState>>();
var graph = new MoveGraph(level, state.crates());
graph.visitLayers(state.workerPos(), layer -> {
for (int pos : layer.nodes()) {
for (var dir : Board.ALL_DIRECTIONS) {
int crate = level.moveIndex(pos, dir);
var newState = state.tryPush(level, crate, dir);
if (newState != null) {
edges.add(new Edge<>(
newState, layer.distance() + 1));
}
}
}
});
return edges;
}
}