Pathfinding-Visualisierung
Sieh zu, wie klassische Graphsuchalgorithmen ihren Weg über ein Raster finden. Zieh Start und Ziel, male Wände und gewichtete Zellen, erzeuge ein Labyrinth und animiere dann A*, Dijkstra, gierige Bestensuche, BFS oder DFS – und vergleiche, wie viele Zellen jeder Algorithmus untersucht.
Zuletzt aktualisiert:
Vergleich auf diesem Feld
| Algorithmus | Besucht | Pfadlänge | Pfadkosten | Kürzester? |
|---|
Anleitung: Pathfinding-Visualisierung
- Wähle einen Algorithmus aus der Liste. Unter dem Raster erscheint eine kurze Erklärung, wie er funktioniert.
- Bearbeite das Feld: Wähle Wand, Gewicht oder Radieren und klicke oder ziehe auf dem Raster. Zieh den grünen Pfeil (Start) oder das rote Ziel, um sie zu verschieben.
- Erzeuge ein Labyrinth, wenn du eine fertige Herausforderung willst: Wähle einen Labyrinthtyp und klicke auf Labyrinth erzeugen.
- Klicke auf Suche starten, um zu animieren. Nutze den Geschwindigkeitsregler, Pause oder Schritt, um Zelle für Zelle vorzugehen.
- Klicke auf Alle Algorithmen vergleichen, um jeden Algorithmus auf demselben Feld auszuführen und besuchte Zellen, Pfadlänge, Kosten und ob jeder Pfad der kürzeste ist, zu sehen.
Pathfinding-Algorithmen im Vergleich
| Algorithmus | Datenstruktur | Nutzt Gewichte | Kürzester Pfad? | Laufzeit (Raster mit V Zellen) | Typisches Verhalten |
|---|---|---|---|---|---|
| A*-Suche | Prioritätswarteschlange nach f = g + h | Ja | Ja, mit zulässiger Heuristik | O(V log V) im schlechtesten Fall | Schmale, aufs Ziel gerichtete Suche |
| Dijkstra-Algorithmus | Prioritätswarteschlange nach g | Ja | Ja (nichtnegative Kosten) | O(V log V) | Gleichmäßige Wellen in alle Richtungen |
| Gierige Bestensuche | Prioritätswarteschlange nach h | Nein (ignoriert bisherige Kosten) | Nein | O(V log V) im schlechtesten Fall | Sehr schnell auf offenen Feldern, lässt sich von Wänden täuschen |
| Breitensuche | FIFO-Warteschlange | Nein | Nur wenigste Züge | O(V) | Schicht für Schicht vom Start aus |
| Tiefensuche | LIFO-Stapel | Nein | Nein | O(V) | Lange einzelne Zweige, viel Zurückgehen |
Auf einem Raster hat jede Zelle höchstens 4 Nachbarn (8 mit Diagonalen), daher wächst die Anzahl der Kanten linear mit der Anzahl der Zellen, und die Versionen mit Binärheap laufen in O(V log V).
Für A* und gierige Suche verwendete Heuristiken
- Manhattan-Distanz (Bewegungen in vier Richtungen): h = |ΔZeile| + |ΔSpalte|. Sie entspricht den exakten Kosten auf einem leeren Raster ohne Gewichte und überschätzt daher nie.
- Oktil-Distanz (Diagonalbewegungen an): h = (|ΔZeile| + |ΔSpalte|) + (√2 − 2) · min(|ΔZeile|, |ΔSpalte|). Sie nimmt an, dass du dich so viel wie möglich diagonal bewegst, wobei jeder Diagonalschritt √2 kostet.
- Diagonalschritte sind nur erlaubt, wenn beide angrenzenden geraden Zellen frei sind, sodass sich ein Pfad nie zwischen zwei Wänden hindurchzwängt, die sich an einer Ecke berühren.
- Bei Gleichstand entscheidet A* zugunsten der Zelle mit dem kleineren h, was die Suche fokussiert hält, wenn viele Zellen denselben f-Wert haben.
Lohnende Experimente
- Gewichte gegen BFS: Male ein Band aus Gewichten quer über die direkte Route. Dijkstra und A* gehen darum herum; BFS läuft geradewegs hindurch und meldet höhere Kosten.
- Falle für die gierige Suche: Zeichne eine U-förmige Wand, die vom Ziel weg geöffnet ist, mit dem Start darin. Die gierige Suche füllt die Mulde, bevor sie entkommt, während A* Entfernung und Kosten abwägt.
- Perfekte Labyrinthe: In einem Labyrinth mit rekursivem Backtracking findet jeder Algorithmus denselben eindeutigen Pfad; der Unterschied liegt nur darin, wie viele Zellen jeder vorher untersucht.
- Erhöhe die Gewichtskosten auf 20 und sieh zu, wie Dijkstra und A* längere Umwege nehmen, die trotzdem weniger kosten.
Tastatur: Fokussiere das Raster mit Tab, bewege die markierte Zelle mit den Pfeiltasten, drück die Leertaste, um mit dem gewählten Werkzeug zu zeichnen, S, um den Start zu setzen, und T, um das Ziel zu setzen.
Häufige Fragen
Welcher Pathfinding-Algorithmus ist der beste?
Für einen einzelnen Start und ein Ziel auf einem Raster ist A* mit einer zulässigen Heuristik meist die beste Wahl: Er findet wie Dijkstra immer den günstigsten Pfad, untersucht aber weniger Zellen, weil die Heuristik die Suche zum Ziel hinzieht. Dijkstra ist besser, wenn du Entfernungen zu vielen Zielen brauchst, und BFS ist am einfachsten, wenn jeder Zug gleich viel kostet.
Findet A* immer den kürzesten Pfad?
A* findet garantiert einen günstigsten Pfad, wenn seine Heuristik die tatsächlichen Restkosten nie überschätzt (zulässige Heuristik). Dieses Tool nutzt die Manhattan-Distanz für Bewegungen in vier Richtungen und die Oktil-Distanz für Diagonalbewegungen; beide sind zulässig, weil jeder Zug mindestens 1 kostet (bzw. √2 diagonal).
Warum findet BFS bei Gewichten einen längeren oder teureren Pfad?
Die Breitensuche zählt Züge, nicht Kosten. Sie findet die Route mit den wenigsten Schritten und läuft dabei bedenkenlos durch gewichtete Zellen. Dijkstra und A* addieren die Kosten jeder betretenen Zelle und machen deshalb Umwege um Gewichte, wenn das günstiger ist. Bei aktivierten Diagonalbewegungen behandelt BFS außerdem einen Diagonalschritt (Kosten √2) wie einen geraden Zug.
Warum ist der DFS-Pfad so lang und verschlungen?
Die Tiefensuche geht in die erste verfügbare Richtung, bis sie in einer Sackgasse landet, und kehrt dann zurück. Sie stoppt, sobald sie das Ziel erreicht, daher ist der gemeldete Pfad einfach der Zweig, auf dem sie sich gerade befand, keine optimierte Route. DFS findet garantiert einen Pfad, falls einer existiert, aber nie garantiert einen kurzen.
Was ist der Unterschied zwischen Dijkstra und gieriger Bestensuche?
Dijkstra ordnet Zellen nach den bereits vom Start aus gezahlten Kosten (g) und breitet sich daher gleichmäßig aus. Die gierige Bestensuche ordnet Zellen nur nach der geschätzten Entfernung zum Ziel (h) und stürmt daher direkt darauf zu. Gierige Suche ist oft viel schneller, kann aber einen deutlich längeren Pfad liefern, besonders um Wände und Gewichte herum. A* kombiniert beides: f = g + h.
Was bedeuten Gewichte in dieser Visualisierung?
Eine gewichtete Zelle ist passierbar, aber teurer zu betreten, wie Schlamm oder Verkehr. Das Betreten kostet die von dir gewählten Gewichtskosten (standardmäßig 5) statt 1. Wände können gar nicht betreten werden. Die Pfadkosten sind die Summe der Kosten aller nach dem Start betretenen Zellen.
Wie werden die Labyrinthe erzeugt?
Das rekursive Backtracking gräbt Gänge mit einer randomisierten Tiefensuche und erzeugt lange Korridore. Der randomisierte Prim-Algorithmus lässt das Labyrinth von einer zufälligen Grenze aus wachsen und erzeugt viele kurze Sackgassen. Die rekursive Teilung beginnt mit einem offenen Raum und teilt ihn wiederholt mit Wänden, die jeweils eine Lücke haben. Alle drei erzeugen perfekte Labyrinthe mit genau einem Weg zwischen zwei beliebigen offenen Zellen.
Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?
Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.