Interaktive Demo
Jump Point Search
Jump Point Search (JPS) von Daniel Harabor und Alban Grastien (2011) macht A* auf Gittern, in denen jeder Schritt gleich viel kostet, viel schneller. Die meisten Zellen eines offenen Gitters lassen sich überspringen, weil viele gleich lange Wege zu ihnen führen.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Die blassen Zellen wurden nur beim Springen betrachtet, nur die Sprungpunkte (helltürkis) kommen in die Open List. Vergleiche die erweiterten Zellen mit A*. Schlamm wird ignoriert, mit Schlamm ist der Weg daher nicht unbedingt der günstigste.
Ablauf
- Erweitert
- –
- Front (max.)
- –
- Wegkosten
- –
Drücke Abspielen oder Nächster Schritt, um die Suche zu starten.
Raster
Optionen
Jump Point Search bewegt sich immer auch diagonal.
Legende
- Start (ziehen zum Verschieben)
- Ziel (ziehen zum Verschieben)
- Wand
- Schlamm
- Front (Open List)
- Besucht (Closed List)
- Beim Springen betrachtet
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Mit Bedingung
Findet den kürzesten Weg auf Gittern, in denen jeder Schritt gleich viel kostet. Schlamm verletzt diese Annahme.
Gewichtete Zellen
Nein
Nimmt gleiche Kosten an, der Schlamm wird bei der Suche ignoriert.
Heuristik
Ja
Wie bei A*, standardmäßig mit der Oktil-Distanz.
Beliebiger Winkel
Nein
Gerade und diagonale Strecken zwischen den Sprungpunkten.
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 diese Seite | Ohne Schlamm | Nein | Ja | Nein |
| Theta* | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
1. Nachbarn aussortieren
Kommt man aus einer Richtung, lassen sich die meisten Nachbarn einer Zelle genauso günstig erreichen, ohne durch sie hindurchzugehen. JPS folgt nur den natürlichen Richtungen (geradeaus oder den Anteilen einer Diagonale) und erzwungenen Nachbarn, die eine Wand sonst unerreichbar machen würde.
2. Springen
Statt jede Zelle in die Open List aufzunehmen, läuft JPS in eine Richtung, bis es auf eine Wand, das Ziel oder eine Zelle mit erzwungenem Nachbarn trifft: einen Sprungpunkt. Diagonale Läufe prüfen bei jedem Schritt beide geraden Richtungen.
3. Ohne Ecken zu schneiden
In dieser Demo dürfen Wege nicht an der Ecke einer Wand vorbeischlüpfen. Das ändert, welche Nachbarn erzwungen sind: Nur gerade Läufe halten an eigenen Sprungpunkten, diagonale Läufe halten dort, wo ein gerader Lauf einen findet.
Quellen
- Daniel Harabors Artikel Jump Point Search über das Verfahren aus „Online Graph Pruning for Pathfinding on Grid Maps“ von Daniel Harabor und Alban Grastien (AAAI 2011).
- Die Sprungregeln für Wege, die keine Ecken schneiden, folgen PathFinding.js von Xueqiao Xu (MIT-Lizenz).