Shortest Path Problem
(Kürzeste-Wege-Problem)

Wie findet ein Navigationssystem den kürzesten Weg vom Start zum Ziel? Wie orientieren sich Bot-Gegner im Ego-Shooter? Diesen Problemstellungen geht diese Artikelserie über Shortest-Path-Algorithmen (und allgemeiner: Pathfinding-Algorithmen) nach.

Dieser erste Artikel behandelt folgende Themen:

• Was ist der Unterschied zwischen "Shortest Path" und "Pathfinding"?
• Welche Shortest-Path-Algorithmen gibt es?
• Beispiel: Wie findet man den kürzesten Weg zwischen zwei Punkten in einem Labyrinth?

Die Quellcodes zum Artikel findest du in meinem GitHub-Repository.

Shortest Path oder Pathfinding?

Ein Shortest-Path-Algorithmus löst das Problem der Suche nach dem kürzesten Weg zwischen zwei Punkten in einem Graph (z. B. auf einer Straßenkarte). Der Begriff "kurz" meint damit nicht unbedingt die physische Distanz. Es kann sich dabei beispielsweise auch um Zeit (Autobahnen werden bevorzugt) oder Kosten (Maut-Straßen werden gemieden) oder eine Kombination aus mehreren Faktoren handeln.

Graphen können sehr komplex sein und Millionen von Knoten und Kanten enthalten (beispielsweise in einer Videospiel-Welt, in der sich hunderte oder tausende Charaktere frei bewegen können), so dass die Suche nach dem optimalen Weg sehr aufwändig wäre.

Für bestimmte Anwendungsgebiete genügt es einen einigermaßen kurzen (oder sogar irgendeinen) Weg zu finden. Hier spricht man dann allgemein von Pathfinding.

Shortest-Path-Algorithmen

Die bekanntesten Shortest-Path-Algorithmen sind:

• der Dijkstra-Algorithmus
• der A*-Algorithmus (ausgesprochen "A Stern" oder englisch "A Star")
• der Bellman-Ford-Algorithmus
• der Floyd-Warshall-Algorithmus

Auf zweidimensionalen, in Kacheln unterteilte Karten, wie sie in frühen Computerspielen üblich waren, kann auch eine Form der Breitensuche – bekannt als Lee-Algorithmus – durchgeführt werden.

Eine optimierte Variante davon erläutere ich im verbleibenden Teil dieses Artikels an einem Beispiel mit Animationen und Java-Quellcode.

Labyrinth-Algorithmus: Wie findet man den kürzesten Weg in einem Labyrinth?

Mein persönliches Lieblingsbeispiel für die Lösung des Shortest-Path-Problems ist das Spiel "FatCat" auf dem HP-85, einem Computer aus den 1980er Jahren, mit dem ich als Kind bei meinem Onkel experimentieren durfte.

Aufgabe war es (wie bei Pac-Man) eine Maus alle Käsestücke in einem Labyrinth fressen zu lassen, ohne selbst von der Katze gefressen zu werden. Das Schwierige dabei war (abgesehen von der Steuerung mit nur zwei Tasten zum Drehen der Maus nach links und rechts), dass die Katze (im Gegensatz zu den Geistern bei Pac-Man) immer auf dem kürzesten Weg zur Maus lief.

Lediglich durch ein Mauseloch, dass den linken und rechten Rand verband, konnte man der Katze ausweichen. Darüber hinaus konnte man die Maus einmal pro Leben an eine andere Stelle beamen – was insbesondere in Sackgassen hilfreich war:

Ich hatte mich damals (ich war etwa zehn) schon für Programmierung interessiert und wollte das Spiel auf meinem C64 nachprogrammieren. Die Anzeige der Labyrinthe und die Steuerung der Maus hatte ich schnell implementiert. Doch die Berechnung des kürzesten Weges zwischen Katze und Maus bereitete mir monatelang Kopfzerbrechen.

Letztlich löste ich es – wie ich Jahre später in meinem Informatikstudium herausfinden sollte – mit einer Variante des Lee-Algorithmus. Ohne Kenntnis dieses Algorithmus hatte ich eine optimierte Variante davon entwickelt, die ich im Folgenden Schritt für Schritt vorstelle.

Optimierter Lee-Algorithmus

Der Lee-Algorithmus hat den Nachteil, dass man am Ende den gefundenen Weg zurückgehen muss ("Backtrace"), um herauszufinden, welche Richtung die Katze einschlagen muss.

Außerdem spezifiziert der Algorithmus nicht, wie man "Felder, deren Nachbar mit i markiert ist" findet. Es wäre unperformant in jedem Schritt das gesamte Labyrinth zu durchsuchen. An dieser Stelle verwende ich eine aus der Breitensuche bekannte Queue, um die jeweils im nächsten Schritt zu überprüfenden Felder zu speichern.

Die folgenden Grafiken und Animationen verwenden das oben gezeigte Labyrinth mit der Katze an Position (15,7) und der Maus an Position (11,5). Das Koordinatensystem startet an der linken oberen Ecke des Labyrinths mit (0,0).

Vorbereitung

Das Labyrinth wird in einem zweidimensionalen boolean-Array namens lab gespeichert. Wände werden durch den Wert true gekennzeichnet. Die äußere Wand mit in diesem Array abzuspeichern vereinfacht den Code, der so keine separaten Prüfungen auf das Erreichen des Randes benötigt.

Um bei der Suche nicht im Kreis zu laufen, wird ein weiteres zweidimensionales boolean-Array mit dem Namen discovered erstellt, in dem diejenigen Felder markiert werden, die bei der Suche bereits entdeckt wurden. Die aktuelle Position der Katze wird darin initial auf true gesetzt.

Die Wände des Labyrinths habe ich etwas dunkler gefärbt, die Position der Katze ist rot markiert, die der Maus gelb. Diese Informationen sind im discovered-Array nicht enthalten. Sie werden im Folgenden mit angezeigt, um das Verständnis zu erleichtern.

Weiterhin wird die Queue für die als nächstes zu besuchenden Felder angelegt. In diese wird die aktuelle Position der Katze (15,7) ohne Richtungsangabe (daher "null") eingefügt:

(Lerne alles über Queues im HappyCoders-Queue-Tutorial.)

Schritt 1

Das soeben in die Queue gelegte Element (also die Startposition der Katze) wird wieder entnommen:

Dann werden alle von der Katze in einem Schritt erreichbaren Felder in die Queue geschrieben – mit ihren X- und Y-Koordinaten sowie der jeweiligen Richtung relativ zum Startpunkt:

Diese Felder werden ebenfalls als "entdeckt" markiert:

Schritte 2 bis n

Solange die Queue nicht leer ist, wird nun jeweils ein Positions-Element entnommen und alle wiederum von dieser Position erreichbaren Felder in die Queue geschrieben – es sei denn sie sind bereits als "entdeckt" markiert.

Dabei wird nicht die in diesem Schritt gegangene Richtung gespeichert, sondern die Richtung des entnommenen Elements kopiert. Denn wir wollen ja wissen, welche Richtung die Katze von ihrer Ausgangsposition aus einschlagen muss.

Das erste Element in der Queue ist die Position (15,6) oberhalb der Katze:

Von dieser Position sind wiederum die Felder darüber (15,5) und darunter (15,7) erreichbar:

Das untere Feld (15,7) ist bereits als "entdeckt" markiert (von dort sind wir gekommen) und wird ignoriert. Das obere Feld (15,5) wird in die Queue geschrieben und ebenfalls als "entdeckt" markiert:

Dieser Prozess wird nun so lange wiederholt, bis die Position der Maus "entdeckt" wurde. Die folgende Animation zeigt, wie sich das discovered-Array dabei nach und nach füllt:

Abbruchbedingung

Sobald die Position der Maus erreicht wird, ist der Algorithmus beendet. Der zuletzt entnommene Queue-Eintrag zeigt die Richtung an, in die die Katze gehen muss. Im Beispiel ist das (11,4)/LEFT (das Feld über der Maus):

Der kürzeste Weg von der Katze zur Maus führt also nach links. In der folgenden Grafik habe ich den Weg gelb markiert:

Der Weg kann den Daten zu diesem Zeitpunkt nicht mehr entnommen werden. Er ist irrelevant, da die Katze nur einen einzigen Schritt machen muss, und danach der kürzeste Weg neu berechnet wird (denn die Maus bewegt sich ja auch, und der kürzeste Weg könnte im nächsten Schritt in eine andere Richtung führen).

Sollte der Fall eintreten, dass die Queue leer ist, ohne dass die Maus gefunden wurde, bedeutet dies, dass es keinen Weg zwischen Katze und Maus gibt. Dieser Fall kann im FatCat-Spiel nicht eintreten, sollte für andere Anwendungen allerdings behandelt werden.

Shortest Path Java Code

Quellcode von 1990

Den C64-Code habe ich leider nicht mehr. Ein paar Jahre später habe ich das Spiel auf einem 286er in Turbo Pascal neu implementiert, und diesen Code konnte ich tatsächlich wiederfinden. Du findest ihn – gekürzt auf die relevanten Teile – hier: KATZE.PAS

Der Pascal-Code ist etwas in die Jahre gekommen und für Ungeübte schwer zu lesen. Daher habe ich den Quellcode – ohne Änderung der Algorithmen und Datenstrukturen – in Java übersetzt. Die Java-Adaption findest du hier: CatAlgorithmFrom1990.java

Der folgende Code implementiert den Algorithmus mit modernen Sprachmitteln und Datenstrukturen wie dem ArrayDeque als Queue. Du findest ihn im GitHub-Repository in der Klasse CatAlgorithmFrom2020.

Den Code des Enums Direction findest du am Ende.

/**
 * Finds the shortest path from cat to mouse in the given labyrinth.
 *
 * @param lab the labyrinth's matrix with walls indicated by {@code true}
 * @param cx the cat's X coordinate
 * @param cy the cat's Y coordinate
 * @param mx the mouse's X coordinate
 * @param my the mouse's Y coordinate
 * @return the direction of the shortest path
 */
private Direction findShortestPathToMouse
    (boolean[][] lab, int cx, int cy, int mx, int my) {
  // Create a queue for all nodes we will process in breadth-first order.
  // Each node is a data structure containing the cat's position and the
  // initial direction it took to reach this point.
  Queue<Node> queue = new ArrayDeque<>();

  // Matrix for "discovered" fields
  // (I know we're wasting a few bytes here as the cat and mouse can never
  // reach the outer border, but it will make the code easier to read. Another
  // solution would be to not store the outer border at all - neither here nor
  // in the labyrinth. But then we'd need additional checks in the code
  // whether the outer border is reached.)
  boolean[][] discovered = new boolean[23][31];

  // "Discover" and enqueue the cat's start position
  discovered[cy][cx] = true;
  queue.add(new Node(cx, cy, null));

  while (!queue.isEmpty()) {
    Node node = queue.poll();

    // Go breath-first into each direction
    for (Direction dir : Direction.values()) {
      int newX = node.x + dir.getDx();
      int newY = node.y + dir.getDy();
      Direction newDir = node.initialDir == null ? dir : node.initialDir;

      // Mouse found?
      if (newX == mx && newY == my) {
        return newDir;
      }

      // Is there a path in the direction (= is it a free field in the labyrinth)?
      // And has that field not yet been discovered?
      if (!lab[newY][newX] && !discovered[newY][newX]) {
        // "Discover" and enqueue that field
        discovered[newY][newX] = true;
        queue.add(new Node(newX, newY, newDir));
      }
    }
  }

  throw new IllegalStateException("No path found");
}

private static class Node {
  final int x;
  final int y;
  final Direction initialDir;

  public Node(int x, int y, Direction initialDir) {
    this.x = x;
    this.y = y;
    this.initialDir = initialDir;
  }
}Code-Sprache: Java (java)

Und die Klasse Direction:

public enum Direction {
  UP(0, -1),
  RIGHT(1, 0),
  DOWN(0, 1),
  LEFT(-1, 0);

  private final int dx;
  private final int dy;

  Direction(int dx, int dy) {
    this.dx = dx;
    this.dy = dy;
  }

  public int getDx() {
    return dx;
  }

  public int getDy() {
    return dy;
  }
}Code-Sprache: Java (java)

Testen kannst du den Code mit der Klasse CatAlgorithmsTest. Diese erstellt ein Labyrinth, platziert Katze und Maus an zufälligen Positionen und lässt die Katze auf kürzestem Weg zur Maus laufen.

Das Demo-Programm visualisiert das Labyrinth mit ASCII-Blöcken, und die einzelnen Schritte werden der Einfachheit halber untereinander gedruckt (der Pathfinding-Algorithmus steht im Vordergrund, nicht die Darstellung). Die folgende Animation zeigt die ausgegebenen Schritte in zeitlicher Abfolge:

Performance des Algorithmus

Mit dem Tool CatAlgorithmsBenchmark lässt sich die Performance der alten und neuen Implementierung vergleichen. Folgende Tabelle zeigt den Median der Messwerte aus 20 Test-Iterationen mit jeweils 100.000 Berechnungen des kürzesten Pfades. Dem Test gingen 10 Warmup-Runden voraus.

Der Algorithmus, den ich als 15-jähriger geschrieben habe, ist auf den ersten Blick schneller als mein neuer Algorithmus. Wie kann das sein?

Optimierung für Katze-und-Maus-Labyrinthe

Ein erneuter Blick in den alten Code zeigt, dass während des Pathfindings nur jeder zweite Wegpunkt betrachtet wird. Dies macht insoweit Sinn, als dass durch den spezifischen Aufbau der Labyrinthe die Katze nur nach jedem zweiten Schritt ihre Richtung ändern kann:

Ich habe den Java-Code noch einmal dahingehend optimiert. Es ändert sich nur der Teil innerhalb der Schleife. Die Zwischenschritte der Katze dürfen dabei nicht komplett außer Acht gelassen werden – denn dort könnte ja die Maus sitzen.

Den optimierten Code findest du im folgenden Listing und in der Klasse CatAlgorithmFrom2020Opt im GitHub-Repository.

while (!queue.isEmpty()) {
  Node node = queue.poll();

  // Go *two* steps breath-first into each direction
  for (Direction dir : Direction.values()) {
    // First step
    int newX = node.x + dir.getDx();
    int newY = node.y + dir.getDy();
    Direction newDir = node.initialDir == null ? dir : node.initialDir;

    // Mouse found after first step?
    if (newX == mx && newY == my) {
      return newDir;
    }

    // Is there a path in the direction (= is it a free field in the labyrinth)?
    // No -> continue to next direction
    if (lab[newY][newX]) continue;

    // Second step
    newX += dir.getDx();
    newY += dir.getDy();

    // Mouse found after second step?
    if (newX == mx && newY == my) {
      return newDir;
    }

    // Target field has not yet been discovered?
    if (!discovered[newY][newX]) {
      // "Discover" and enqueue that field
      discovered[newY][newX] = true;
      queue.add(new Node(newX, newY, newDir));
    }
  }
}Code-Sprache: Java (java)

Und hier das Ergebnis eines erneuten Performance-Vergleichs:

Der neue Code ist nun etwa 25 % schneller als der von 1990.

Falls du in den Code von 1990 geschaut hast: Der Grund liegt darin, dass ich damals keine Queue verwendet habe, sondern zwei separate Datenstrukturen für die Ausgangs- und Endpunkte jedes Pathfinding-Schritts. Nach jedem Schritt wurden alle Endpunkte in die Datenstruktur der Ausgangspunkte kopiert.

Dass ich mit 15 nicht an die Verwendung einer Queue gedacht habe (die ich damals auch gar nicht einfach aus dem Werkzeugkoffer hätte ziehen können), möge man mir verzeihen ;-)

Zusammenfassung und Ausblick

Dieser Artikel hat das "Shortest-Path-Problem" beschrieben und am Beispiel des "FatCat"-Spiels (bei uns hieß das Spiel übrigens "Katze und Maus") gezeigt, wie man die Problemstellung mit einem Pathfinding-Algorithmus in Java lösen kann.

Der hier vorgestellte Algorithmus kann nur auf kachelbasierte Karten, bzw. auf Graphen, die kachelbasierte Karten repräsentieren, angewendet werden.

In den folgenden Teilen der Serie werde ich allgemeine Shortest-Path-Algorithmen wie den Dijkstra-Algorithmus und den A*-Algorithmus vorstellen.

Wenn dir der Artikel gefallen hat, trage dich gerne in den HappyCoders E-Mail-Verteiler ein (dann wirst du sofort informiert, wenn ich weitere Teile dieser Serie veröffentliche), und teile den Artikel auch gerne über einen der Share-Buttons am Ende.