Labyrinthe lösen mit PHP

Tags:

Heute werde ich eine Art vorstellen, wie man (mit PHP) einfache 2D-Labyrinthe lösen kann. Dazu werden wir den Maze Routing Algorithmus von C. Y. Lee verwenden. Dieser Algorithmus ist relativ simpel, findet garantiert einen Weg (falls es einen gibt) - und erst noch den schnellsten. Negativ ist, dass der Algorithmus nicht besonders schnell ist und bei grossen Labyrinthen auch speicherintensiv werden kann.

Die Theorie

Aber schauen wir uns erst mal so ein Beispiellabyrinth an. Blau markiert den Start, das Ziel ist Gelb.

Beispiellabyrinth

Rastern

Der erste Schritt besteht darin, dass Labyrinth zu rastern. Das geht bei diesem 2D Labyrinth sehr einfach, da alle Felder (egal ob Wand oder Weg) gleich gross sind. Wir können also ein Koordinatensystem anwenden, wobei oben links x=0, y=0 und unten rechts x=33, y=24 entspricht.

Beispiellabyrinth gerastert

Bewerten

Als nächstes werden wir nun, vom Startpunkt ausgehend, alle möglichen Wege wellenförmig bewerten. Dem Startpunkt geben wir die Wertung 0. Allen Wegfeldern die an den Startpunkt anknüpfen erhalten die Wertung 1 (1. Welle). Alle Wegfelder die wiederum an diese Felder anknüpfen, erhalten die Wertung 2 (2. Welle). Das tun wir solange, bis wir das Ziel erreicht haben oder keine Felder zum Bewerten mehr übrig sind. Tritt Letzteres ein, können wir davon ausgehen, dass es keine Möglichkeit gibt das Labyrinth zu lösen.

Bewertung 0 Bewertung 1 Bewertung 2 Bewertung 3 Bewertung 4 Bewertung 5 Bewertung 6 Bewertung 7

Anzumerken gilt, dass ein bereits bewertetes Feld nicht neu bewertet werden darf. Sonst würden wir nämlich in eine Endlosschleife kommen, da benachbarte Felder sich stetig neubewerten würden.

Das fertig bewertete Labyrinth sieht dann so aus:

Beispiellabyrinth bewertet

Hier ist gut zu sehen, dass wir das Ziel erreichten, bevor alle Felder bewertet wurden. Da der Weg über noch nicht bewertete Felder langsamer wäre, können wir diese getrost ignorieren.

Rückwärtssuche

Um den schnellsten Pfad zu finden, gehen wir jetzt - vom Zielpunkt aus - rückwärts durch das Labyrinth. Wir schauen uns also die Nachbarn des Zielpunktes (= Wertung 52) an und suchen uns den Nachbarn raus, der die tiefste Wertung hat. Der Nachbar rechts hat keine Wertung, bleibt also nur der Nachbar unten (51). Für diesen durchforsten wir wiederum dessen Nachbarn und finden einen weiteren Nachbarn darunter (50). Weiter geht's mit dessen Nachbarn. Wir wählen den Nachbarn rechts davon (49). Dies tun wir solange, bis wir den Startpunkt (0) gefunden haben. Während unserer Rückwärtsreise merken wir uns natürlich genau, welche Wegpunkte wir passieren.

Beispiellabyrinth gelöst

Sind wir durch, müssen wir die Route nur noch umkehren (damit sie vorwärts geht) und schon haben wir unseren Lösungsweg.

Wie ihr vielleicht bemerkt hat, gibt es für dieses Labyrinth mehrere Lösungswege, die genau gleich lang sind. So könnten wir z.B. beim Feld mit der Wertung 28 nach oben, anstatt nach links ziehen. Für solche Fälle könnte man den Algorithmus erweitern und einbauen, dass möglichst gerade Strecken bevorzugt werden. Sollte nicht allzu schwierig sein! :)

Die Praxis

Es braucht eigentlich nur zwei Klassen: Point und Maze. Jeder Point hat eine X- und eine Y-Position, einen Typ (Startpunkt, Wegpunkt, Zielpunkt oder Wand) sowie eine Wertung (standardmässig null). Die Maze Klasse verwaltet ein Raster bestehend aus Point-Objekten und bietet Methoden zum Bewerten und zur Wegfindung.

Den kompletten Source Code für die nachfolgenden Auszüge hab ich auf GitHub gestellt. Greift zu!

Rastern

Die Maze-Klasse bietet eine Hilfsfunktion an, um aus einem .PNG (z.B. https://github.com/bigwhoop/Maze-Routing-Algorithm/raw/master/maze3.png) ein Labyrinth zu erstellen. Dabei wird jeder schwarze Pixel als Wand, jeder weisse Pixel als Weg, der blaue Pixel als Startpunkt und der gelbe Pixel als Zielpunk angesehen.

$maze = Maze::createFromImage(__DIR__ . '/maze3.png');

Ihr könnt euch also gerne in Paint kurz euer eigenes Labyrinth malen. :)

Aber los geht's. Betrachten wir zuerst die findConnectingPaths() Methode. Diese findet für jeden Punkt die benachbarten Punkte oben, links, rechts und unten, die keine Wand sind.

/**
 * @param Point $point
 * @return array
 */
private function findConnectingPaths(Point $point)
{
    $possiblePointTypes = array(
        Point::TYPE_START,
        Point::TYPE_PATH,
        Point::TYPE_FINISH
    );

    if (!in_array($point->getType(), $possiblePointTypes)) {
        return array();
    }

    $offsets = array(
        array('x' => -1, 'y' =>  0), // left of $point
        array('x' =>  0, 'y' => -1), // above $point
        array('x' =>  0, 'y' =>  1), // below $point
        array('x' =>  1, 'y' =>  0), // right of $point
    );

    $connectingPaths = array();

    foreach ($offsets as $offset) {
        // Build x/y of connecting point
        $x = $point->getX() + $offset['x'];
        $y = $point->getY() + $offset['y'];

        if (!isset($this->grid[$y])) {
            continue;
        }

        if (!isset($this->grid[$y][$x])) {
            continue;
        }

        $connectingPoint = $this->grid[$y][$x];

        if (in_array($connectingPoint->getType(), $possiblePointTypes)) {
            $connectingPaths[] = $connectingPoint;
        }
    }

    return $connectingPaths;
}

Wir erhalten also ein Array mit Point-Objekten zurück. Oder auch nur ein leeres Array, falls ein Punkt keine Nachbarn hat.

Bewerten

Die scoreGrid() Methode schnappt sich den Startpunkt, steckt ihn in eine "Welle" für die Wertung 0 und startet damit die Bewertungsroutine scorePathsRecursively(). Diese wiederum tut folgendes:

  1. Setzt für alle übergebenen Wegpunkte die aktuelle Wertung.
  2. Sucht anhand der übergebenen Wegpunkte die nächst möglichen, noch nicht bewerteten Punkte und steckt sie in eine neue "Welle" ($upcomingPaths).
  3. Ruft sich selbst mit der eigens zusammengebauten nächsten "Welle" und der nächsten Wertung auf.
  4. Bricht dann ab, wenn eine "Welle" keine Punkte hat oder der Zielpunkt gefunden und bewertet wurde.

Und hier der Code:

/**
 * @return Maze
 */
public function scoreGrid()
{
    if (!$this->isScored) {
        $this->scorePathsRecursively(array($this->startPoint), 0);
        $this->isScored = true;
    }

    return $this;
}


/**
 * @param array $paths
 * @param int $score
 */
private function scorePathsRecursively(array $paths, $score)
{
    if (empty($paths)) {
        return;
    }

    $upcomingPaths = array();

    foreach ($paths as $path) {
        $path->setScore($score);

        if ($path->getType() == Point::TYPE_FINISH) {
            return;
        }

        foreach ($this->findConnectingPaths($path) as $connectingPath) {
            if (!$connectingPath->isScored()) {
                $upcomingPaths[] = $connectingPath;
            }
        }
    }

    $this->scorePathsRecursively($upcomingPaths, $score + 1);
}

Rückwärtssuche

Nachdem wir alle nötigen Felder bewertet haben, können wir die Wertungen analysieren und die Route zusammensetzen. Dazu nutzen wir die Methode findRoute(). Die stellt erst mal sicher, dass das Labyrinth bewertet wurde und überprüft dann, ob der Zielpunkt eine Wertung hat. Hat der nämlich keine, bedeutet das, dass es keine Lösung geben kann. In diesem Fall können wir einfach abbrechen.

/**
 * @return array
 */
public function findRoute()
{
    if (!$this->isScored) {
        $this->scoreGrid();
    }

    // We didn't reach the finish point :/
    if (!$this->finishPoint->isScored()) {
        return array();
    }

    return $this->findRouteRecursively($this->finishPoint);
}

Danach wird vom Zielpunkt ausgehend findRouteRecursively() aufgerufen. Diese Methode tut folgendes:

  1. Untersucht alle Nachbarn des Punktes nach folgenden Kriterien:
    1. Ist er der Startpunkt, können wir abbrechen.
    2. Er muss eine Wertung haben.
    3. Er muss eine kleinere Wertung als der Suchpunkt haben.
    4. Falls nicht der erste untersuchte Kandidat, muss er eine kleinere Wertung als der aktuell beste Kandidat haben.
  2. Wurde ein Punkt gefunden, wird dieser der Route hinzugefügt.
  3. Danach gibt es einen rekursiven Aufruf von findRouteRecursively() mit dem gefundenen Punkt und der bisher zusammengesetzten Route.

Zu beachten gilt, dass die Route den Start- und Zielpunkt nicht beinhaltet. Dies könnte man natürlich ändern. Ist nur eine Definitionssache, was man als Route bezeichnet. :)

/**
 * @param Point $point
 * @param array $route
 * @return array
 */
private function findRouteRecursively(Point $point, array $route = array())
{
    $nextPoint = null;

    foreach ($this->findConnectingPaths($point) as $nextPointCandidate) {
        // If possbile next point is the start, we found what we're looking for
        if ($nextPointCandidate->getType() == Point::TYPE_START) {
            return array_reverse($route);
        }

        // Possible next point must be scored
        if (!$nextPointCandidate->isScored()) {
            continue;
        }

        // Possible next point's score must be below the current point's score
        if (!$nextPointCandidate->getScore() >= $point->getScore()) {
            continue;
        }

        // Possible next point's score must be below the current possible next point's score
        if (null === $nextPoint || $nextPointCandidate->getScore() < $nextPoint->getScore()) {
            $nextPoint = $nextPointCandidate;
        }
    }

    // Seems like we could not find the start. -> No route.
    if (!$nextPoint) {
        return array();
    }

    // Add next point to the route
    $route[] = $nextPoint;

    return $this->findRouteRecursively($nextPoint, $route);
}

So, wir haben nun ein Array mit allen Punkten für den kürzesten Weg zwischen Start- und Zielpunkt. Oder anders gesagt: Das Labyrinth ist gelöst! :)

Vielleicht kommt in Zukunft noch ein Update zu diesem Artikel, über einen anderen Algorithmus oder eine Verbesserung für diesen.

Ähnliche Artikel

Kommentare