Pathfinding-Algorithmus-Visualizer

Die Formel f(n)=g(n)+h(n) lässt A* Knoten bevorzugen, die bisher günstig sind und dem Ziel noch nahe erscheinen. Solange h die verbleibenden Kosten nie überschätzt, behält A* seine Garantie auf den kürzesten Pfad; eine stärkere zulässige Heuristik h durchsucht weniger unnötige Zellen. Wechsle das Algorithmus-Dropdown, um zu sehen, was passiert, wenn man die Heuristik weglässt (Dijkstra), die bisherigen Kosten weglässt (Greedy) oder ganz auf Bewertung verzichtet (BFS).

Alle vier Algorithmen laufen in genau derselben Schleife: Sie holen die vielversprechendste Zelle aus einer Warteliste (die bernsteinfarbene Front), markieren sie als besucht (indigo) und fügen deren freie Nachbarn wieder zur Liste hinzu. Der einzige Unterschied ist, wie sie entscheiden, welche Zelle am vielversprechendsten aussieht. Fazit: Die Zahl der expandierten Knoten ist der eigentliche Maßstab — weniger indigo Zellen bedeuten, dass der Algorithmus dasselbe Ziel mit weniger vergeudeter Arbeit erreicht hat.

Aktiviere 'Diagonale erlauben' zusammen mit der Manhattan-Heuristik, und A* kann klammheimlich einen Pfad liefern, der nicht der kürzeste ist. Ein Diagonalschritt kostet hier nur √2 ≈ 1.41, doch die Manhattan-Distanz berechnet ihn als 2 — die Heuristik überschätzt also, wird unzulässig, und die Optimalitätsgarantie ist dahin. Wechsle zu Euklidisch, das die Luftlinie nie überschätzt, und der kürzeste Pfad kehrt zurück.