DE 
English
Українська🎮 Game-NPC-Pfadfinder — A*-Suche live
Beobachte, wie der echte A*-Suchalgorithmus simulierte Spielkarten-Knoten live nach genuinen f=g+h-Kosten expandiert und nachweislich kürzeste NPC-Pfade um Hindernisse herum findet — schneller als reiner Dijkstra.
Über die Simulation „A*-Suche live"
Spiel-Engines stellen ständig dieselbe Frage: Was ist die kürzeste begehbare Route von einem NPC zu seinem Ziel über eine Karte voller Wände, Terrain und anderer Hindernisse? Die A*-Suche (Hart, Nilsson & Raphael, 1968) ist die Standardantwort — eine Best-First-Graphensuche, die eine echte Prioritätswarteschlange nach f(n) = g(n) + h(n) ordnet, wobei g(n) die tatsächlich angesammelten Kosten vom Start und h(n) eine zulässige heuristische Schätzung der verbleibenden Distanz ist. Diese Simulation führt den echten Algorithmus aus — echte offene Menge, echte geschlossene Menge, echte Elternzeiger — auf einer Raster-Spielkarte, die du bearbeiten kannst, und lässt gleichzeitig den reinen Dijkstra-Algorithmus (A* mit h(n) = 0) auf derselben Karte laufen, sodass du Knoten für Knoten genau siehst, wie viel Arbeit die Heuristik einspart.
🔬 Was gezeigt wird
Zwei nebeneinanderliegende Raster teilen sich eine Hinderniskarte: Das linke Raster führt echtes A* mit einer Oktile-Distanz-Heuristik aus, das rechte Raster führt Dijkstra mit auf null erzwungener Heuristik aus. Cyanfarbene Zellen sind in der offenen Menge (entdeckt, eingereiht, noch nicht expandiert), bernsteinfarbene Zellen sind in der geschlossenen Menge (expandiert, finalisiert), und der farblich hervorgehobene Pfad ist die kürzeste Route, rekonstruiert über Elternzeiger, sobald der Zielknoten entnommen wird. Live-Zähler summieren die tatsächliche Anzahl der Knoten, die jede Prioritätswarteschlange wirklich entnommen hat.
🎮 Bedienung
Wähle einen Modus — Wand, Start oder Ziel — und klicke dann auf eine beliebige Zelle in einem der Raster, um die gemeinsame Karte zu bearbeiten; beide Suchen laufen sofort neu. Nutze „Zufälliges Labyrinth", um ein neues Hindernislayout zu erzeugen, „Wände löschen", um mit offenem Feld zu beginnen, und den Expansionsgeschwindigkeits-Regler, um die Enthüllung zum Lehren zu verlangsamen oder zu beschleunigen, um den finalen Pfad sofort zu sehen. „Wiederholen" startet die Knoten-für-Knoten-Animation neu, ohne die Suche neu zu berechnen.
💡 Wusstest du schon?
Weil der Dijkstra-Algorithmus mathematisch identisch mit A* bei h(n)=0 ist, laufen beide Panels exakt denselben Code mit einer geänderten Zahl — deshalb ist dies ein fairer, direkter Vergleich und nicht zwei unabhängige Implementierungen. Auf offenen Karten expandiert A* oft weniger als die Hälfte der Knoten, die Dijkstra benötigt; auf Karten, auf denen eine Wand beide Algorithmen zu einem langen Umweg zwingt, schrumpft die Lücke, weil keiner die Geometrie abkürzen kann, die die Heuristik nicht sehen kann.
Häufig gestellte Fragen
Was ist die A*-Suche und wie unterscheidet sie sich vom Dijkstra-Algorithmus?
Beide sind Best-First-Graphensuchen, die bei jedem Schritt den Knoten mit den geringsten Kosten aus einer Prioritätswarteschlange (der offenen Menge) entnehmen. Der Dijkstra-Algorithmus ordnet diese Warteschlange rein nach g(n), den tatsächlich angesammelten Kosten vom Startknoten, sodass er sich in alle Richtungen gleichmäßig ausbreitet, wie Wellen auf einem Teich. A* ordnet dieselbe Warteschlange nach f(n) = g(n) + h(n) und fügt eine zulässige heuristische Schätzung h(n) der verbleibenden Distanz zum Ziel hinzu. Dieser zusätzliche Term lenkt die Expansion in Richtung Ziel, sodass A* typischerweise weit weniger Knoten schließt als Dijkstra, dabei aber garantiert denselben kürzesten Pfad liefert — denn ein Dijkstra-Lauf ist mathematisch identisch mit einem A*-Lauf mit h(n) = 0 für jeden Knoten, genau so implementiert diese Simulation den Vergleich auf einer gemeinsamen Karte.
Was macht eine Heuristik zulässig, und warum garantiert das, dass A* den kürzesten Pfad findet?
Eine Heuristik h(n) ist zulässig, wenn sie die tatsächlichen verbleibenden Kosten von Knoten n zum Ziel niemals überschätzt — sie darf unterschätzen oder exakt richtig liegen, aber nie zu optimistisch in die falsche Richtung. Auf einem Raster, in dem diagonale Schritte √2 und orthogonale Schritte 1 kosten, ist die geradlinige (oktile) Distanz zum Ziel stets kleiner oder gleich den tatsächlichen verbleibenden Pfadkosten um Hindernisse herum, weshalb sie zulässig ist. Mit einer zulässigen Heuristik ist garantiert, dass A* niemals einen Knoten mit einem suboptimalen g-Wert finalisiert: Jeder als kürzest gemeldete Pfad ist wirklich der kürzeste — deshalb kann die Simulation behaupten, dass A* und Dijkstra stets bei denselben Pfadkosten landen, nicht nur bei ähnlichen.
Was ist die oktile Distanz, und warum wird sie auf Rasterkarten mit diagonaler Bewegung verwendet?
Die oktile Distanz ist die Heuristik für 8-Richtungs-Raster: Bei |dx| und |dy| Zellen horizontaler und vertikaler Trennung bewegt sich der kürzestmögliche Pfad (ohne Hindernisse) min(|dx|,|dy|) mal diagonal zu Kosten von je √2 und deckt dann die verbleibenden |dx|−|dy| Zellen orthogonal zu je 1 Kosten ab. Die Formel (|dx|+|dy|) + (√2−2)·min(|dx|,|dy|) berechnet genau das. Reine euklidische oder Manhattan-Distanz würde entweder überschätzen (und damit die Zulässigkeit auf einem Raster mit diagonaler Bewegung brechen) oder zu grob unterschätzen, weshalb die oktile Distanz die enge, zulässige Wahl ist, die diese Simulation für h(n) von A* verwendet.
Warum expandiert A* meist weniger Knoten als Dijkstra?
Dijkstra hat keine Vorstellung davon, wo das Ziel liegt, sodass sich seine Expansionsfront als annähernd kreisförmige Wellenfront um den Start ausbreitet und jeden Knoten innerhalb eines gegebenen Kostenradius berührt, bevor er das Ziel erreicht. A*s Ordnung nach f = g + h hält Knoten, die auf das Ziel zeigen, weit vorn in der Prioritätswarteschlange, sodass sich seine Front zu einer länglichen, zielgerichteten Form streckt und große Bereiche auf der anderen Seite der Karte überspringt, die Dijkstra noch besuchen müsste. Die Live-Zähler in dieser Simulation summieren die tatsächliche Anzahl der Knoten, die jeder Algorithmus wirklich aus seiner eigenen Prioritätswarteschlange entnommen und geschlossen hat, auf derselben Hinderniskarte — der sichtbare Unterschied ist also echt und gemessen, nicht angenommen. Auf Karten, auf denen die gerade Linie zum Ziel durch ein großes Hindernis blockiert ist, kann sich die Lücke verkleinern oder sogar verschwinden, was die Simulation ehrlich zeigt.
Was ist der Unterschied zwischen der offenen und der geschlossenen Menge?
Die offene Menge ist die Front: Knoten, die entdeckt (von einem Nachbarn aus erreicht) und in die Prioritätswarteschlange eingereiht, aber noch nicht expandiert wurden. Die geschlossene Menge sind Knoten, die bereits aus der Warteschlange entnommen wurden und deren Nachbarn vollständig untersucht sind — ihre kürzesten g-Kosten vom Start sind finalisiert und ändern sich nicht mehr. In der Visualisierung befinden sich cyanfarbene Zellen in der offenen Menge (noch betrachtete Kandidaten) und bernsteinfarbene Zellen in der geschlossenen Menge (vollständig verarbeitet); sobald das Ziel aus der geschlossenen Menge entnommen wird, stoppt der Algorithmus und rekonstruiert den Pfad, indem er Elternzeiger rückwärts vom Ziel zum Start durchläuft.
Kann A* jemals den kürzesten Pfad verfehlen oder überhaupt keinen Pfad finden?
A* findet garantiert den kürzesten Pfad, wann immer einer existiert und die Heuristik zulässig ist — die oktile-Distanz-Heuristik dieser Simulation erfüllt diese Bedingung auf jeder Karte, die du baust. Was A* nicht kann, ist einen Pfad zu finden, der nicht existiert: Wenn du das Ziel vollständig ummauerst, werden sowohl A* als auch Dijkstra ihre offenen Mengen erschöpfen und melden, dass kein Pfad gefunden wurde — was das Statistikfeld ausdrücklich anzeigt, anstatt stillschweigend eine veraltete Route zu zeigen.
Eine binäre-Heap-Prioritätswarteschlange expandiert Knoten in echter Best-First-Reihenfolge nach f(n)=g(n)+h(n) im linken Raster und f(n)=g(n) im rechten; beide rekonstruieren den kürzesten Pfad über echte Elternzeiger, sobald das Ziel aus der geschlossenen Menge entnommen wird.
3D · Three.js / WebGL-Renderer · 60 FPS Ziel · läuft vollständig clientseitig, keine Installation