A*-Labor

Auf einem festen 16 × 16-Raster sind horizontale und vertikale Schritte möglich. Jeder Schritt kostet eins; diagonale Schritte oder gewichtete Zellen gibt es nicht. Die Pfadkosten zählen Kanten. Liegen Start und Ziel zusammen, sind die Kosten null.

A* wählt eine offene Zelle mit dem kleinsten f = g + h. Dabei ist g die bisherige Strecke vom Start; h ist die Manhattan-Distanz, die euklidische Distanz oder null (Dijkstra). Bei Gleichstand entscheidet das kleinere h, dann die Einfügereihenfolge. Eine Verbesserung behält die ursprüngliche Reihenfolge der offenen Zelle bei. Alle drei Heuristiken sind auf diesem Raster konsistent; geschlossene Zellen müssen deshalb nicht erneut geöffnet werden. Die Suche endet, wenn das Ziel aus der offenen Menge entnommen wird. „Besucht“ zählt diese Entnahmen einschließlich des Ziels. Ein Einzelschritt entnimmt höchstens eine Zelle.

Der Vergleich verwendet dasselbe Raster und dieselbe Gleichstandsregel für alle drei Läufe. Das angezeigte Raster gehört zur gewählten Heuristik. Ist das Ziel erreichbar, liefern alle einen kürzesten Pfad. Die Besuchszahlen hängen vom Raster und der Gleichstandsregel ab. Diese kleine Lernimplementierung durchsucht die offene Menge und benötigt im ungünstigsten Fall O(V²) Zeit.

Bearbeitungsmodus wählen, dann klicken oder ziehen. Start und Ziel können nicht mit Wänden übermalt werden; das Setzen einer Markierung entfernt dort eine Wand. Im fokussierten Raster bewegen Pfeiltasten den umrandeten Cursor. Leertaste oder Enter bearbeitet die Zelle. Koordinaten reichen von 0 bis 15, mit (0, 0) oben links.

Starten setzt eine pausierte Suche fort und beginnt eine fertige Suche neu. Ein Schritt pausiert zuerst. „Suche zurücksetzen“ erhält das Raster; „Leer“ entfernt Wände und stellt die Markierungen zurück. Bearbeiten oder ein Heuristikwechsel verwirft Suche und Vergleich. Das Tempo ändert nur die Animation. Beim Verlassen des Tools oder Ausblenden der Seite stoppt sie. Raster, Heuristik, Tempo, Bearbeitungsmodus und Tastaturcursor bleiben lokal in diesem Browser erhalten, der Suchfortschritt nicht. Bei Fokusverlust oder ausgeblendeter Seite endet eine aktive Zeichengeste. Ältere gespeicherte Raster bleiben kompatibel.

Quellen: Hart, Nilsson und Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968), S. 101–102; Korrektur von 1972 zu Konsistenz und geschlossenen Knoten.