Ja. Wenn du die Manhattan-Distanz oder die Max-Distanz verwendest, dann ist es egal ob du erst 5 Felder runter und dann 5 Felder nach rechts läufst, oder ob du 5 Mal abwechselnd ein Feld nach rechts und ein Feld nach unten gehst. Bei der euklidischen Distanz ist die zweite Lösung besser.
Du änderst zwar nur den approx_value (das heißt für die exakte Lösung ist es weiterhin egal), aber das sorgt ja dennoch dafür, dass das abwechselnd nach rechts und nach unten laufen bevorzugt wird (weil diese Knoten einen niedrigeren approx_value haben und daher als erstes besucht werden).
Wichtig beim Ändern der approx_value Berechnung ist immer, dass du nie zu hoch schätzt. Man kann aber zeigen dass die euklidische Distanz nie höher als die Manhattan-Distanz oder die Max-Distanz sein kann (nennt sich Dreiecksungleichung). Darum ist das in diesem Fall erlaubt nur den approx_value anzupassen und die exakten Kosten weiterhin nach dem gewohnten Schema berechnen zu lassen.
Achja, wegen dem Berechnen der diagonalen Schritte: das ist das letzte worüber du dir Sorgen machen musst. Der Pathfinding-Algorithmus muss unter Umständen sehr sehr viele Knoten anschauen. Der Algorithmus, der aus diesen Knoten diagonale macht muss hingegen nur so viele Knoten anschauen, wie es Schritte auf dem Weg gibt. Das ist im Normalfall extrem wenig. Außerdem kannst du diese Umrechnung auch "lazy" machen. Also erst wenn das Event (oder für wen auch immer du den Pfad berechnest) sich wirklich bewegt, wird geguckt ob es die nächsten zwei orthogonalen Schritte durch einen diagonalen Schritt ersetzen kann.
Zitieren