Clever Geek Handbook

KI bei MindestgehÀltern: Wir schreiben unseren eigenen Sokoban und bringen dem Computer bei, ihn zu lösen

Computer spielt Sokoban



In diesem Artikel werde ich Ihnen erklĂ€ren, wie Sie Ihre eigene Implementierung des berĂŒhmten Sokoban-Spielzeugs sowie einen Algorithmus zum Lösen von Grund auf neu schreiben. Gleichzeitig werde ich einige Entwurfsmuster und SOLID-Prinzipien in die Praxis umsetzen.



Der gesamte Code befindet sich unter



Hintergrund



Ich benutze ein Drucktastentelefon. Von der Unterhaltung darauf nur Radio und das einzige Spiel Sokoban von 15 Levels. Von diesen habe ich nur 10 gelöst und bin am elften hĂ€ngen geblieben. Einmal bin ich den ganzen Tag mit dem Zug gefahren und habe dieses unglĂŒckliche 11-Level gelöst, aber es ist mir nicht gelungen. Dann habe ich mich fĂŒr einen Computer entschieden, da ich genug Programmiererfahrung fĂŒr diese Aufgabe habe. Ich habe mir ein Ziel gesetzt: selbstĂ€ndig eine Implementierung mit einer Lösung fĂŒr dieses Spielzeug zu schreiben. Infolgedessen erschien dieser Artikel.



Dieselbe 11-Ebene (Lösung am Ende des Artikels):



elf



Das Spielzeug selbst ist ein rechteckiges 2D-Feld, auf dem Kisten, WÀnde und Markierungen verstreut sind. Die Boxen können geschoben, aber nicht gezogen werden, das ist die ganze Schwierigkeit. Ihr Ziel: Alle Felder in Zellen mit Markierungen verschieben. Beispielspiel:



Level Beispiel



Wir schreiben die Implementierung



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 , . — , . , , , . .


, . , , , . "" — , , . :



Anwendungsarchitektur



, , 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. , . .



Abstrakte Fabrik



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: . , . , , . - , , .



:



Richtung



:



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.......#
############


, :



Entscheidung



, , , . . , — .





? . . , , :



Konfigurationsdiagramm



, , . . , , , . . ,

, :



Ereignisdiagramm



, . , (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 -. .



. .

. , , . . , :



Sackgasse



, :



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 . , .



Um einen neuen KI-Algorithmus zu starten, habe ich einen neuen Controller geschrieben AIController, der keine Befehle von der Konsole liest, sondern die Ebene mit dem angegebenen Algorithmus löst und die Lösung auf einem Timer verliert. Sie mĂŒssen nur eine Zeile Ă€ndern main. Unsere Investition in Architektur hat sich gelohnt:



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();
    }
}


Schlussfolgerungen



Wir haben unsere eigene Implementierung des Sokoban-Spielzeugs erstellt, die Entwurfsmuster Abstract Factory, Factory Method und Strategy in der Praxis angewendet, die S-, O- und D-Prinzipien von SOLID untersucht und die BFS- und A * -Algorithmen implementiert.



Ich wĂŒrde mich ĂŒber Kommentare sowohl zum Code als auch zum Artikel selbst freuen. Wir sehen uns!



Ich bin im Telegramm: @outofbound



More articles:


All Articles