Interaktive Demo
Theta*
Gitterwege sind zackig: Selbst der günstigste biegt nur in 45°-Schritten ab. Theta* von Alex Nash, Kenny Daniel, Sven Koenig und Ariel Felner (2007) prüft beim Suchen die Sichtlinie und findet Wege, die in jedem Winkel geradeaus verlaufen.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Die weißen Linien verbinden jede Zelle mit ihrem Vorgänger, oft weit entfernt. Theta* kürzt nur über freies Gelände ab, um und durch Schlamm geht es von Zelle zu Zelle.
Ablauf
- Erweitert
- –
- Front (max.)
- –
- Wegkosten
- –
Drücke Abspielen oder Nächster Schritt, um die Suche zu starten.
Raster
Optionen
Theta* schätzt immer mit der Luftlinie.
Legende
- Start (ziehen zum Verschieben)
- Ziel (ziehen zum Verschieben)
- Wand
- Schlamm
- Front (Open List)
- Besucht (Closed List)
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Nein
Meist kürzer als der beste Gitterweg, aber nicht garantiert der kürzeste Weg in beliebigem Winkel.
Gewichtete Zellen
Mit Bedingung
Abkürzungen führen nur über freies Gelände, durch Schlamm geht es von Zelle zu Zelle.
Heuristik
Ja
Die Luftlinie, die einzige sichere Schätzung für Wege in beliebigem Winkel.
Beliebiger Winkel
Ja
Der Weg kann in jedem Winkel abbiegen, wo die Sichtlinie frei ist.
Alle 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* diese Seite | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
1. Zwei Kandidaten
Erreicht A* einen Nachbarn von einer Zelle aus, wird diese Zelle sein Vorgänger. Theta* probiert auch den Vorgänger der Zelle: Ist die gerade Linie von dort zum Nachbarn frei, verbindet sich der Nachbar direkt mit ihm, und seine Kosten sind die Länge dieser Linie.
2. Sichtlinie
Die Linie wird Zelle für Zelle geprüft, als würde man sie aufs Gitter zeichnen. Jede berührte Zelle muss frei sein. Wo sie genau durch eine Ecke geht, müssen auch beide Zellen neben der Ecke frei sein, so schlüpft der Weg nie zwischen zwei Wänden hindurch.
3. Fast optimal
Theta*-Wege sind meist kürzer als jeder Gitterweg und sehen ohne nachträgliches Glätten natürlich aus. Garantiert die kürzesten Wege in beliebigem Winkel sind sie nicht, weil Abkürzungen nur zum Vorgänger des Vorgängers führen.
Quellen
- Alex Nash, Kenny Daniel, Sven Koenig und Ariel Felner: Theta*: Any-Angle Path Planning on Grids (AAAI 2007).
- Die Sichtlinie läuft wie die Supercover-Linien in Line drawing on a grid von Amit Patel (Red Blob Games) über das Gitter.