Interaktive Demo
Wegfindungsalgorithmen
Wie kommt man von A nach B? Acht Suchalgorithmen finden Schritt für Schritt ihren Weg durch Wände und Schlamm. Jeder wägt anders ab zwischen Tempo, Qualität des Wegs und dem, was er wissen muss.
Uninformierte Suche
Breitensuche
Breitet sich in Ringen gleicher Schrittzahl vom Start aus. Findet den Weg mit den wenigsten Schritten, ignoriert aber, was ein Schritt kostet.
Optimal: Mit BedingungGewichtete Zellen: Nein
Tiefensuche
Folgt einer Richtung so weit wie möglich und kehrt erst in Sackgassen um. Findet einen Weg, aber selten einen kurzen.
Optimal: NeinGewichtete Zellen: Nein
Dijkstra-Algorithmus
Erweitert immer die günstigste bisher gefundene Zelle. Er breitet sich nach Kosten aus und findet den günstigsten Weg, um den Schlamm herum, wenn das günstiger ist.
Optimal: JaGewichtete Zellen: Ja
Bidirektionale Suche
Führt den Dijkstra-Algorithmus gleichzeitig vom Start und vom Ziel aus. Die beiden Suchen treffen sich in der Mitte und erkunden zusammen weniger.
Optimal: JaGewichtete Zellen: Ja
Informierte Suche
Gierige Bestensuche
Erweitert immer die Zelle, die dem Ziel am nächsten scheint. In freiem Gelände sehr schnell, lässt sich aber leicht in Sackgassen und Umwege locken.
Optimal: NeinGewichtete Zellen: Nein
A*-Suche
Addiert zu den bisherigen Kosten eine Schätzung der restlichen Entfernung. Mit einer guten Schätzung findet sie den günstigsten Weg und erkundet viel weniger als Dijkstra.
Optimal: Mit BedingungGewichtete Zellen: Ja
Gittertechniken
Jump Point Search
A* für gleichförmige Gitter, das entlang gerader Strecken springt und nur hält, wo der Weg abbiegen könnte. Viel weniger Zellen landen in der Open List.
Optimal: Mit BedingungGewichtete Zellen: Nein
Theta*
A*, das eine Zelle direkt mit dem Vorgänger ihres Vorgängers verbindet, wenn die Linie dazwischen frei ist. Wege verlaufen in jedem Winkel und schlagen Gitterwege.
Optimal: NeinGewichtete Zellen: Mit Bedingung
Wegfindungsalgorithmen im Vergleich
| Algorithmus | Optimal | Gewichtete Zellen | Heuristik | Beliebiger Winkel |
|---|---|---|---|---|
| Breitensuche | Ohne Schlamm und Diagonalen | Nein | Nein | Nein |
| Tiefensuche | Nein | Nein | Nein | Nein |
| Dijkstra-Algorithmus | Ja | Ja | Nein | Nein |
| Bidirektionale Suche | Ja | Ja | Nein | Nein |
| Gierige Bestensuche | Nein | Nein | Ja | Nein |
| A*-Suche | Mit Gewicht 1 und zulässiger Heuristik | Ja | Ja | Nein |
| Jump Point Search | Ohne Schlamm | Nein | Ja | Nein |
| Theta* | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
Die Vorschauen zeigen jeden Algorithmus auf derselben Karte mit diagonalen Schritten: Wände hellgrau, Schlamm braun.