In this article, I will tell you how to write your own implementation of the famous Sokoban toy, as well as an algorithm for solving it from scratch. At the same time, I will put into practice some design patterns and SOLID principles.
Background
I use a push-button telephone. From entertainment on it only radio and the only game Sokoban of 15 levels. Of these, I only solved 10 and got stuck on the eleventh. Once I rode the train all day and solved this ill-fated 11th level, but did not succeed. Then I decided to use a computer, since I have enough programming experience for this task. I set a goal: to write an implementation with the solution of this toy myself. As a result, this article appeared.
The same 11 level (solution at the end of the article):
The toy itself is a rectangular 2D field on which boxes, walls and tags are scattered. The boxes can be pushed, but not pulled, this is the whole difficulty. Your goal: to move all boxes to cells with marks. Example game:
We write the implementation
GUI . - Rogue-like, . . :
- # , .
- O .
- X , .
- @ .
- . .
- G .
— . , . MVC — , , . , , . . . — - . , SOLID. , . — , — , — . , . . . :
- , , GUI . .
- .
— , :
public class ConsoleController implements Controller
{
private final Model model;
private final View view;
public ConsoleController(final Model model)
{
this.model = model;
this.view = new ConsoleView(model);
}
// methods
}model , , view . , ConsoleController View, ConsoleView, . ConsoleView ConsoleController, , :
public class ConsoleController implements Controller
{
private final Model model;
private final View view;
public ConsoleController(final Model model, final View view)
{
this.model = model;
this.view = view;
}
// methods
}ConsoleController . D SOLID , . . , — . , - Spring , . .
. , ?
-
(row, col),row,col, . — , . , , , . .
, . , , , . "" — , , . :
, , Model. Sokoban , . move() . Sokoban . getCrates() getMarks() . , : A* (A star algorithm).
run() " -> -> -> "
, :
###########
#.@..O..X.#
########### - . " ". : CharSokobanFactory , , , . , Sokoban , , :
public Sokoban(final Field field, final Set<Point> crates, final Set<Point> marks, final Point player)
{
this.field = field;
this.crates = crates;
this.marks = marks;
this.player = player;
} CharSokobanFactory. , . .
vi-like :
- j —
- k —
- h —
- l —
, :
class Sokoban {
// some stuff
public boolean solved()
{
return marks.equals(crates);
}
// other stuff
} if- , Direction, . Move, Direction move(direction) . Move.resolve, .
" ". : , 4 .
O SOLID, Open-Closed Principle: . , . , , . - , , .
:
:
class ConsoleController {
//
@Override
public void run()
{
view.say("Sokoban Starts");
char symbol = '0';
view.render();
final List<Move> history = new LinkedList<>();
while (symbol != 'q')
{
final Move move = Move.resolve(symbol);
if (move != null)
{
history.add(move);
move.perform(sokoban);
view.render();
if (sokoban.solved())
{
view.say("YOU WIN!");
break;
}
}
try
{
symbol = (char) System.in.read();
}
catch (IOException io)
{
view.say(" :");
throw new IllegalStateException(io);
}
}
view.say("Your moves: " + Move.compress(history));
}
//
}, , . , "" , , . .
:
class ConsoleView {
//
@Override
public void render()
{
clearConsole();
for (int i = 0; i < sokoban.numberOfFieldRows(); i++)
{
for (int j = 0; j < sokoban.numberOfFieldCols(); j++)
{
final Point at = new Point(i, j);
final Tile tileAt = sokoban.tile(at);
if (tileAt == null)
break;
final char symbolToPrint = tileAt == Tile.CRATE && sokoban.isMarkAt(at) ? Tile.CRATE_ON_MARK.symbol() : tileAt.symbol();
System.out.print(symbolToPrint);
}
System.out.println();
}
}
//
}15 . G (Good) , , . , .
. :
- , . , .
, "walkable" Tile:
public enum Tile {
WALL('#', false),
GRASS('.', true),
CRATE('O', false),
MARK('X', true),
CRATE_ON_MARK('G', false),
PLAYER('@', true);
private final char symbol;
private final boolean walkable;
Tile(final char symbol, final boolean walkable) {
this.symbol = symbol;
this.walkable = walkable;
}
public boolean isWalkable() {
return walkable;
}
}, :
public Sokoban {
// Sokoban
public Tile tile(final Point at) {
if (player.equals(at))
return Tile.PLAYER;
//
if (crates.contains(at))
return Tile.CRATE;
//
return field.tileAt(at);
}
public boolean isWalkableTileAt(final Point at) {
return tile(at).isWalkable();
}
// Sokoban
}, , , . :
public class Main {
public static void main(String[] args) {
final Sokoban sokoban = CharSokobanFactory.fromFile(args[0]).make();
final View view = new ConsoleView(sokoban);
final Controller game = new ConsoleController(sokoban, view);
//
game.run();
}
}:
############
#.XO.......#
#.XO......@#
#.XO.......#
############, :
, , , . . , — .
? . . , , :
, , . . , , , . . ,
, :
, . , (1:1), .
. — .
. . , . , , . , — Breadth-First Search (BFS).
BFS
"" — (Depth-First Search) — BFS , . , . BFS (FIFO), DFS (LIFO), . BFS:
BFS(G, s)
1. , :
* v.p = null //
* v.marked = false //
2. Q
3. Q.enqueue(s)
4. Q :
4.1 v = q.poll()
4.2 v.marked = true
4.3 v ,
4.4 v , child:
4.4.1 child.marked, :
4.4.1.2 child.p = v
4.4.1.3. q.enqueue(child) v.p v. v.marked , v . v "" v -> v.p -> v.p.p -> ... -> s -. .
. .
. , , . . , :
, :
public class BFSSolver {
//
protected List<Pair<Sokoban, List<Direction>>> deriveChildren(final Sokoban parent) {
final Map<Point, Point> walkablePoints = shortestPathsFromPlayer(parent);
final List<Pair<Sokoban, List<Direction>>> result = new LinkedList<>();
for (final Point crate : parent.getCrates()) {
final Point[][] pairs = new Point[][]{{crate.left(), crate.right()}, {crate.right(), crate.left()},
{crate.up(), crate.down()}, {crate.down(), crate.up()}};
for (Point[] pair : pairs) {
final Point playerWillStand = pair[0];
final Point crateWillGo = pair[1];
if (canMoveCrate(parent, playerWillStand, crateWillGo, walkablePoints) && !isDeadPosition(parent, crateWillGo)) {
final LinkedList<Direction> pathToChild = unwindWalk(walkablePoints, playerWillStand);
pathToChild.add(crate.derive(crateWillGo));
final Sokoban child = parent.derive(crate, crateWillGo);
result.add(Pair.pair(child, pathToChild));
}
}
}
return result;
}
//
} shortestPathsFromPlayer parent . walkablePoints v v.p. isDeadPosition . derive Sokoban "" :
public Sokoban derive(final Point crateToRemove, final Point crateToInsert)
{
final Set<Point> childConfiguration = new HashSet<>(crates);
childConfiguration.remove(crateToRemove);
childConfiguration.add(crateToInsert);
return new Sokoban(this.field, childConfiguration, Collections.unmodifiableSet(this.marks), crateToRemove);
} , "" . , Point (immutable). "", , BFS, . v.p v.marked .
:
public class BFSSolver {
//
public List<Move> solve(final Sokoban start) {
final Map<Sokoban, Pair<Sokoban, List<Direction>>> childToParentAndDirection = new HashMap<>();
final Set<Sokoban> visited = new HashSet<>();
final Queue<Sokoban> toVisit = new LinkedList<>();
toVisit.add(start);
boolean found = false;
Sokoban parent = null;
while (!toVisit.isEmpty()) {
parent = toVisit.remove();
if (parent.solved()) {
found = true;
break;
}
visited.add(parent);
for (final Pair<Sokoban, List<Direction>> pair : deriveChildren(parent)) {
final Sokoban child = pair.first;
final List<Direction> walkFromParentToChild = pair.second;
if (!visited.contains(child)) {
childToParentAndDirection.put(child, Pair.pair(parent, walkFromParentToChild));
toVisit.add(child);
}
}
}
return found? unwind(parent, childToParentAndDirection) : new LinkedList<>();
}
//
} , , BFS , . , , , . , , . ,
"" , . , . .
* (A star), . * .. h . h . — , h .
"" . . AStarSolver . , .
To start a new AI algorithm, I wrote a new controller AIControllerthat does not read commands from the console, but solves the level with the specified algorithm and loses the solution on a timer. you only need to change one line in main. Our investment in architecture has paid off:
public class Main {
public static void main(String[] args) {
final Sokoban sokoban = CharSokobanFactory.fromFile(args[0]).make();
final View view = new ConsoleView(sokoban);
final Solver solver = new AStarSolver();
final int sleepBetweenMovesMillis = 300;
final Controller game = new AIController(sokoban, view, sleepBetweenMovesMillis, solver);
//
game.run();
}
}conclusions
We created our own implementation of the Sokoban toy, applied the Abstract Factory, Factory Method, and Strategy design patterns in practice, considered the S, O and D principles from SOLID and implemented the BFS and A * algorithms.
I would be glad to have any comments both on the code and on the article itself. See you!
I'm in telegram: @outofbound