Ich denke, dein Pfad ist nicht optimal. Vom Start aus müsste dieser zweimal diagonal nach rechts unten verlaufen, hier scheint dir ein Fehler bei der Parent-Zuweisung passiert zu sein
Gut aufgepasst, dies ist allerdings vollkommen beabsichtigt. Da ich den Algorithmus vorwiegend für die Spieleentwicklung verwende, habe ich auch hier eingebaut, dass man sich nicht über Diagonalen, die direkt neben unbegehbaren Feldern liegen bewegen darf. Dies würde nämlich dazu führen, dass sich die Figur beim traversieren der Diagonale leicht durch die Wand bewegt, was natürlich unerwünscht ist. Diese Extra-Regel, dass Diagonalen nicht begehbar sein sollen, wenn diese durch eine Wand blockiert werden würden, ist in meinem Code hier implementiert: github.com/ArztSamuel/A-Star-Pathfinding/blob/master/C-Sharp%20Demo/A-Star%20Demo/AStar.cs#L204 Dementsprechend kannst du diese Kondition auch ganz einfach wieder entfernen, solltest du diese Regel nicht benötigen.
Danke für das Video. Jedoch verstehe ich nicht, warum man eine unterschätzende Heuristik Funkion für den Algorithmus braucht, damit er korrekt arbeitet.
Danke für den netten Kommentar! Das ist tatsächlich eine sehr gute Frage. Die Webseite, die ich in der Videobeschreibung verlinkt habe, erklärt kurz die Unterschiede zwischen unterschätzenden, überschätzenden und richtigen Heuristiken, aber ich glaube sie geht auch nicht genauer auf die Details ein... (theory.stanford.edu/~amitp/GameProgramming/Heuristics.html)
Auch wenn die Frage schon 4 Monate alt ist, versuch ich diese Trotzdem zu beantworten. Der Algorithmus würde auch gänzlich ohne diese Heuristik funktionieren, allerdings wäre die durchschnittliche dauer diesen Weg zu finden länger, da die Felder willkürlich untersucht werden. Der Wert der unterschätzenden Heuristik gibt dem Algorithmus quasi einen Vorschlag welche der zu untersuchenden Felder er sich primär anschauen soll. Kann man sich wie ein Kompass vorstellen, der auf das Zielzeigt.
Ich glaube, dein Pfad bei Min. 10. ist falsch?! Weil im ersten Schritt würde man in das Feld rechts gehen, weil dieses ja nur 40 "kostet" und nicht nach rechts unten, da hier die "Kosten" 54 betragen...oder nicht?
Gut aufgepasst! Die F-Kosten des rechten Feldes sind tatsächlich kleiner als die des Feldes darunter und es wird auch als erstes zur geschlossenen Liste hinzugefügt (blau markiert). Wichtig ist jedoch: wenn man Felder "untersucht" und zur geschlossenen Liste hinzufügt, beschreitet man diese nicht sofort. Es werden zuerst so viele Felder wie notwendig untersucht (also zur offenen/geschlossenen Liste hinzugefügt), bis eine der Abbruchbedingungen erfüllt ist und erst dann kann man den gefunden Weg beschreiten. In diesem Fall würden sich durch das Untersuchen der Nachbarn des rechten Feldes keine neuen günstigeren Felder ergeben und es wird direkt das Feld rechts unter dem Startfeld (jetzt das günstigste in der offenen Liste (grün markiert)) zur geschlossenen Liste hinzugefügt. Durch das Rückverfolgen der Parents der Felder ergibt sich dann am Ende der gezeigte Pfad. Am besten verständlich wird das ganze, meiner Meinung nach, durch eine interaktive Visualisierung. Auf meiner Github-Seite kannst du dir zum Beispiel das Java-Programm downloaden, dass ich auch in diesem Video verwendet habe und den Algorithmus Schritt für Schritt durchspielen: github.com/ArztSamuel/A-Star-Pathfinding Danke für dein Interesse, ich hoffe ich konnte dir weiterhelfen.
