Ein Labyrinthlöser in Java

1. Einleitung

In diesem Artikel werden mögliche Möglichkeiten zum Navigieren in einem Labyrinth mithilfe von Java untersucht.

Betrachten Sie das Labyrinth als Schwarzweißbild, wobei schwarze Pixel Wände und weiße Pixel einen Pfad darstellen. Zwei weiße Pixel sind etwas Besonderes, eines ist der Eingang zum Labyrinth und eines der Ausgang.

Angesichts eines solchen Labyrinths wollen wir einen Weg vom Eingang zum Ausgang finden.

2. Modellierung des Labyrinths

Wir betrachten das Labyrinth als ein 2D-Integer-Array. Die Bedeutung der numerischen Werte im Array entspricht der folgenden Konvention:

  • 0 -> Straße
  • 1 -> Wand
  • 2 -> Labyrintheintrag
  • 3 -> Labyrinthausgang
  • 4 -> Zellenteil des Pfades vom Eingang zum Ausgang

Wir werden das Labyrinth als Grafik modellieren . Ein- und Ausgang sind die beiden Spezialknoten, zwischen denen der Pfad zu bestimmen ist.

Ein typischer Graph hat zwei Eigenschaften, Knoten und Kanten. Eine Kante bestimmt die Konnektivität des Diagramms und verbindet einen Knoten mit einem anderen.

Daher nehmen wir vier implizite Kanten von jedem Knoten an, die den angegebenen Knoten mit seinem linken, rechten, oberen und unteren Knoten verbinden.

Definieren wir die Methodensignatur:

public List solve(Maze maze) { }

Die Eingabe für die Methode ist ein Labyrinth, das das 2D-Array mit der oben definierten Namenskonvention enthält.

Die Antwort der Methode ist eine Liste von Knoten, die einen Pfad vom Eingangsknoten zum Ausgangsknoten bildet.

3. Rekursiver Backtracker (DFS)

3.1. Algorithmus

Ein ziemlich offensichtlicher Ansatz besteht darin, alle möglichen Pfade zu erkunden, die letztendlich einen Pfad finden, wenn er existiert. Ein solcher Ansatz wird jedoch eine exponentielle Komplexität aufweisen und sich nicht gut skalieren lassen.

Es ist jedoch möglich, die oben erwähnte Brute-Force-Lösung anzupassen, indem besuchte Knoten zurückverfolgt und markiert werden, um in angemessener Zeit einen Pfad zu erhalten. Dieser Algorithmus wird auch als Tiefensuche bezeichnet.

Dieser Algorithmus kann wie folgt beschrieben werden:

  1. Wenn wir uns an der Wand oder an einem bereits besuchten Knoten befinden, wird ein Fehler zurückgegeben
  2. Andernfalls, wenn wir der Exit-Knoten sind, geben Sie Erfolg zurück
  3. Fügen Sie andernfalls den Knoten in die Pfadliste ein und fahren Sie rekursiv in alle vier Richtungen. Wenn ein Fehler zurückgegeben wird, entfernen Sie den Knoten aus dem Pfad und geben Sie einen Fehler zurück. Die Pfadliste enthält einen eindeutigen Pfad, wenn der Exit gefunden wird

Wenden wir diesen Algorithmus auf das in Abbildung 1 (a) gezeigte Labyrinth an, wobei S der Startpunkt und E der Ausgang ist.

Für jeden Knoten durchlaufen wir jede Richtung in der Reihenfolge: rechts, unten, links, oben.

In 1 (b) erkunden wir einen Pfad und treffen die Wand. Dann ziehen wir uns zurück, bis ein Knoten gefunden wird, der keine Wandnachbarn hat, und erkunden einen anderen Pfad, wie in 1 (c) gezeigt.

Wir stoßen erneut gegen die Wand und wiederholen den Vorgang, um endlich den Ausgang zu finden, wie in 1 (d) gezeigt:

3.2. Implementierung

Sehen wir uns nun die Java-Implementierung an:

Zuerst müssen wir die vier Richtungen definieren. Wir können dies in Koordinaten definieren. Wenn diese Koordinaten zu einer bestimmten Koordinate hinzugefügt werden, wird eine der benachbarten Koordinaten zurückgegeben:

private static int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 

Wir brauchen auch eine Dienstprogrammmethode, die zwei Koordinaten hinzufügt:

private Coordinate getNextCoordinate( int row, int col, int i, int j) { return new Coordinate(row + i, col + j); }

Wir können jetzt die Methode Signatur lösen definieren. Die Logik hier ist einfach : Wenn es einen Pfad vom Eingang zum Ausgang gibt, geben Sie den Pfad zurück, andernfalls geben Sie eine leere Liste zurück:

public List solve(Maze maze) { List path = new ArrayList(); if ( explore( maze, maze.getEntry().getX(), maze.getEntry().getY(), path ) ) { return path; } return Collections.emptyList(); }

Definieren wir die oben genannte Erkundungsmethode . Wenn es einen Weg gibt dann true zurück, mit der Liste der Koordinaten in dem Argumente Pfad . Diese Methode hat drei Hauptblöcke.

Zuerst verwerfen wir ungültige Knoten, dh die Knoten, die sich außerhalb des Labyrinths befinden oder Teil der Wand sind. Danach markieren wir den aktuellen Knoten als besucht, damit wir nicht immer wieder denselben Knoten besuchen.

Schließlich bewegen wir uns rekursiv in alle Richtungen, wenn der Ausgang nicht gefunden wird:

private boolean explore( Maze maze, int row, int col, List path) { if ( !maze.isValidLocation(row, col) || maze.isWall(row, col) || maze.isExplored(row, col) ) { return false; } path.add(new Coordinate(row, col)); maze.setVisited(row, col, true); if (maze.isExit(row, col)) { return true; } for (int[] direction : DIRECTIONS) { Coordinate coordinate = getNextCoordinate( row, col, direction[0], direction[1]); if ( explore( maze, coordinate.getX(), coordinate.getY(), path ) ) { return true; } } path.remove(path.size() - 1); return false; }

Diese Lösung verwendet eine Stapelgröße bis zur Größe des Labyrinths.

4. Variante - kürzester Weg (BFS)

4.1. Algorithmus

Der oben beschriebene rekursive Algorithmus findet den Pfad, aber es ist nicht unbedingt der kürzeste Pfad. Um den kürzesten Weg zu finden, können wir einen anderen Graph-Traversal-Ansatz verwenden, der als Breitensuche bekannt ist.

In DFS, one child and all its grandchildren were explored first, before moving on to another child. Whereas in BFS, we'll explore all the immediate children before moving on to the grandchildren. This will ensure that all nodes at a particular distance from the parent node, are explored at the same time.

The algorithm can be outlined as follows:

  1. Add the starting node in queue
  2. While the queue is not empty, pop a node, do following:
    1. If we reach the wall or the node is already visited, skip to next iteration
    2. If exit node is reached, backtrack from current node till start node to find the shortest path
    3. Else, add all immediate neighbors in the four directions in queue

One important thing here is that the nodes must keep track of their parent, i.e. from where they were added to the queue. This is important to find the path once exit node is encountered.

Following animation shows all the steps when exploring a maze using this algorithm. We can observe that all the nodes at same distance are explored first before moving onto the next level:

4.2. Implementation

Lets now implement this algorithm in Java. We will reuse the DIRECTIONS variable defined in previous section.

Lets first define a utility method to backtrack from a given node to its root. This will be used to trace the path once exit is found:

private List backtrackPath( Coordinate cur) { List path = new ArrayList(); Coordinate iter = cur; while (iter != null) { path.add(iter); iter = iter.parent; } return path; }

Definieren wir nun die Kernmethode lösen. Wir werden die drei in der DFS-Implementierung verwendeten Blöcke wiederverwenden, dh Knoten validieren, besuchten Knoten markieren und benachbarte Knoten durchlaufen.

Wir werden nur eine kleine Änderung vornehmen. Anstelle einer rekursiven Durchquerung verwenden wir eine FIFO-Datenstruktur, um Nachbarn zu verfolgen und über sie zu iterieren:

public List solve(Maze maze) { LinkedList nextToVisit = new LinkedList(); Coordinate start = maze.getEntry(); nextToVisit.add(start); while (!nextToVisit.isEmpty()) { Coordinate cur = nextToVisit.remove(); if (!maze.isValidLocation(cur.getX(), cur.getY()) || maze.isExplored(cur.getX(), cur.getY()) ) { continue; } if (maze.isWall(cur.getX(), cur.getY())) { maze.setVisited(cur.getX(), cur.getY(), true); continue; } if (maze.isExit(cur.getX(), cur.getY())) { return backtrackPath(cur); } for (int[] direction : DIRECTIONS) { Coordinate coordinate = new Coordinate( cur.getX() + direction[0], cur.getY() + direction[1], cur ); nextToVisit.add(coordinate); maze.setVisited(cur.getX(), cur.getY(), true); } } return Collections.emptyList(); }

5. Schlussfolgerung

In diesem Tutorial haben wir zwei wichtige Graph-Algorithmen beschrieben: Tiefensuche und Breitensuche, um ein Labyrinth zu lösen. Wir haben auch angesprochen, wie BFS den kürzesten Weg vom Eingang zum Ausgang gibt.

Weitere Informationen zum Lösen eines Labyrinths finden Sie unter A * und Dijkstra.

Wie immer finden Sie den vollständigen Code auf GitHub.