Pada artikel ini saya akan memberi tahu Anda cara menulis implementasi Anda sendiri dari mainan Sokoban yang terkenal, serta algoritma untuk menyelesaikannya dari awal. Pada saat yang sama, saya akan mempraktikkan beberapa pola desain dan prinsip SOLID.
Latar Belakang
Saya menggunakan telepon tombol. Dari hiburan di dalamnya hanya radio dan satu-satunya permainan sokoban dari 15 level. Dari jumlah tersebut, saya hanya menyelesaikan 10 dan terjebak di kesebelas. Suatu kali saya naik kereta sepanjang hari dan menyelesaikan level 11 yang naas ini, tetapi tidak berhasil. Kemudian saya memutuskan untuk menggunakan komputer, karena saya memiliki pengalaman pemrograman yang cukup untuk tugas ini. Saya menetapkan tujuan: secara mandiri menulis implementasi dengan solusi untuk mainan ini. Akibatnya, artikel ini muncul.
Level 11 yang sama (solusi di akhir artikel):
Mainan itu sendiri adalah bidang 2D persegi panjang tempat kotak, dinding, dan tanda berserakan. Kotak bisa didorong, tapi tidak ditarik, inilah keseluruhan kesulitannya. Tujuan Anda: untuk memindahkan semua kotak ke sel dengan tanda. Contoh permainan:
Kami menulis implementasinya
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 . , .
Untuk memulai algoritma AI baru, saya menulis pengontrol baru AIControlleryang tidak membaca perintah dari konsol, tetapi menyelesaikan level dengan algoritma yang ditentukan dan kehilangan solusi pada pengatur waktu. Anda hanya perlu mengubah satu baris main. Investasi kami dalam arsitektur telah membuahkan hasil:
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();
}
}kesimpulan
Kami telah membuat implementasi kami sendiri dari mainan Sokoban, menerapkan pola desain Pabrik Abstrak, Metode Pabrik, dan Strategi dalam praktik, memeriksa prinsip S, O dan D dari SOLID dan mengimplementasikan algoritma BFS dan A *.
Saya akan dengan senang hati memberikan komentar baik tentang kode maupun artikel itu sendiri. Sampai jumpa!
Saya di telegram: @outofbound