In addition to the Level class, which represents a level in its original state, we also need a data type GameState that stores the state of the level as the game progresses. Only two things can change: the worker’s current
position, which we store as a single integer, and the positions of all crates, which we store as a bit set (Listing 8.7).
Listing 8.7ch8 / GameState
public record GameState(int workerPos, BitSet crates) {
// Initialize using starting configuration of 'level'.
public GameState(Level level) {
this(level.workerStart(), level.crates());
}
// Does this state solve the level?
public boolean allCratesOnGoals(Level level) {
return level.goals().containsAll(crates);
}
// ...
}
The allCratesOnGoals() method in Listing 8.7 determines whether a particular game state is a valid solution. This is the case if every
crate is on a goal square, in other words, if the bit setlevel.goals() contains every element of the bit set crates.
You may have noticed that GameState doesn’t store a reference to the Level it belongs to; instead, we have to explicitly pass this level to methods such as allCratesOnGoals(). This seems to go against the usual convention in object-oriented programming of designing classes to be self-contained. The main
reason against making GameState self-contained is memory consumption: Solving a Sokoban level involves creating millions or tens of millions of different GameState
objects that all belong to the same Level. When dealing with a large number of objects, minimizing the amount of duplicate information can save a significant amount of memory. In object-oriented design, this technique is often referred to as the Flyweight pattern, one of the original “design patterns” discussed in Gamma et al. [38].
For the moment, let’s assume that the crates are in fixed positions and start with the simpler problem of moving the worker alone. We can model this problem by defining a special graph in which nodes and edges represent locations and the possible moves between them. In our case, each location is a
square in the level that doesn’t contain a wall or a crate, and it is possible to move between two locations if they are horizontally or vertically adjacent. Figure 8.4 shows the resulting graph, which we will call the move graph, for the initial state of Level 1.
Figure 8.4 The move graph models how the worker can move in a Sokoban level.
Implementing the move graph is straightforward. Every position in the level, and therefore every node in the move graph, can be represented by its index, so we can define a class MoveGraph that implements the Graph interface and has nodes of type Integer (Listing 8.8). The arguments of the constructor MoveGraph() are the level and the positions of all crates. Since crates are considered immovable, we don’t need to distinguish between walls and crates and simply combine them into a single set of obstacles.
Listing 8.8ch8 / MoveGraph
public class MoveGraph implements Graph<Integer> {
private final Level level;
private final BitSet obstacles;
public MoveGraph(Level level, BitSet crates) {
this.level = level;
obstacles = new BitSet(level.walls());
obstacles.addAll(crates);
}
// Return the empty positions adjacent to 'index'.
@Override
public BitSet neighbors(Integer index) {
var result = new BitSet();
for (var direction : Board.ALL_DIRECTIONS) {
result.add(level.moveIndex(index, direction));
}
result.removeAll(obstacles);
return result;
}
}
The neighbors() method computes the list of nodes that can be reached from a given position, namely the adjacent positions that are not blocked by an obstacle. To compute the neighbors, we first
add all adjacent positions to a bit setresult and then remove the blocked squares in obstacles.
This implementation of neighbors() conforms to the Graph interface even though the return type BitSet differs from the Iterable type specified by the interface. The reason is that Java allows overloading methods to replace the return type with a more specific type. In
this case, BitSet is more specific because it implements the Iterable interface.
In technical terms, return types in Java are said to be covariant. What this means is that when you override a method defined in a base class or an interface, you can replace the return type with any subtype of it. The notion of covariance (and its
opposite contravariance) is also relevant when defining generic methods and classes; see also https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science).
As a simple application of the move graph, let’s use it to find the worker’s shortest path between two positions in a level. For example, if level is an instance of Level that represents
Level 1, we can use breadth-first search to find the path from the worker’s starting position \((11,8)\) to the right of the first box at \((8,4)\):
The return value is the shortest path between the two positions as a list of integers. One way to print this path in human-readable form is to take pairs of adjacent positions and translate them into a string of move commands:
if (path != null) {
for (int i = 0; i < path.size() - 1; i++) {
Board.Direction dir = level.getDirection(
path.get(i), path.get(i + 1));
System.out.print(dir.charCode());
}
System.out.println();
} else {
System.out.println("No solution");
}
For the path constructed above, this outputs “ullluuu”.
Exercises
Exercise 8.2. Implement a method for GameState that prints the current state using the text-based format described in Fig. 8.3.
Exercise 8.3.A Sokoban level is closed if there are no gaps in the walls through which the worker could escape. (Crates are ignored in this case.) Suggest an algorithm that determines whether a level
is closed.
Exercise 8.4.The move graph shown in Fig. 8.4 consists of four disjoint groups of nodes that are all
connected to each other, which are are also known as the components of the graph. Explain how to compute the components of a given instance of MoveGraph.