Zitat Zitat von Cornix Beitrag anzeigen
Ich bin mir natürlich bewusst, dass der Algorithmus derzeit diagonale Bewegungen mit der gleichen Geschwindigkeit als horizontale Bewegungen ansieht was natürlich falsch ist da sie mathematisch gesehen das Quadratwurzel(2) fache mehr benötigen sollten.
Jein. Die Berechnung darfst du selbst festlegen. Der euklidische Abstand ist am realistischsten, aber du kannst auch einen Maximum-Abstand verwenden (das also der diagonale Schritt genauso lang ist wie ein orthogonaler).

Das Problem ist nur: Du musst den gewählten Abstand auch konsistent verwenden. Derzeit verwendest du zwei Abstände: Einen Manhattan-Abstand in deiner Schätzfunktion (der diagonale Schritt ist gleich lang wie zwei orthogonale) und einen Maximum-Abstand in deiner Kostenfunktion. Das heißt, die approx_values werden über einen anderen Abstand berechnet als die exact_cost. Unglücklicherweise ist der Manhattan-Abstand länger als der Max-Abstand. Das führt dazu, dass die approx_values zu hoch geschätzt werden. Wenn das passiert, funktioniert der Algorithmus nicht mehr. Wie zuvor schon mal gesagt: Du darfst den Lowerbound (also die approx_values) nur zu niedrig schätzen, nicht aber zu hoch.

Man kann es auch an einem Beispiel erklären. Du berechnest die distanz derzeit so: distanz = x-abstand + y-abstand. Das würde bedeuten, das bei einem diagonalen Feld die Distanz gleich 2 ist. Nun berechnest du also den Lowerbound mit 2 * Min-Wegkosten. Nun erlaubst du aber auch einen diagonalen Schritt mit Kosten 1 * Wegkosten. Das heißt es gibt exakte Kosten, die kürzer sind als die zuvor berechneten Minimalkosten.

Die Lösung wäre eine Anpassung deiner Schätzfunktion:
Code: 
distance_x = node.x - to_tile_x
distance_y = node.y - to_tile_y
approx_distance = [distance_x.abs + distance_y.abs].max
# oder effizienter
approx_distance = distance_x
approx_distance = distance_y if distance_y > distance_x