在本文中，我将告诉您如何编写自己的著名Sokoban玩具的实现，以及从头开始解决它的算法。同时，我将实践一些设计模式和SOLID原理。
背景
我使用按键电话。从娱乐上来看，只有电台和唯一的15级推箱子游戏。其中，我只解决了10个问题，并排在第11位。我整天骑着火车解决了这个不幸的11级问题，但没有成功。然后，我决定使用计算机，因为我有足够的编程经验来完成此任务。我设定了一个目标：独立编写带有此玩具解决方案的实现。结果，这篇文章出现了。
相同的11级（本文结尾处的解决方案）：
玩具本身是一个矩形的2D场，上面散布着盒子，墙壁和标记。盒子可以被推动，但不能被拉，这就是整个困难。您的目标：将所有盒子移到带有标记的单元格中。示例游戏：
我们写实现
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 . , .
为了启动新的AI算法，我编写了一个新的控制器AIController，该控制器不从控制台读取命令，而是使用指定的算法解决关卡，并在计时器上丢失解决方案。您只需要在中更改一行即可main。我们在建筑方面的投资已获得回报：
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();
}
}结论
我们创建了自己的推箱子玩具实现，在实践中应用了抽象工厂，工厂方法和策略设计模式，考虑了SOLID的S，O和D原理，并实现了BFS和A *算法。
我很高兴收到有关代码和文章本身的任何评论。再见！
我在电报中：@outofbound