Verwende mal eine euklidische Distanz:
Code: 
approx_distance = Math.hypot(node.x - to_tile_x, node.y - to_tile_y)
approx_value = exact_value + approx_distance * Node::MINIMAL_SPEED_FACTOR
Jetzt hat die Luftlinie einen kürzeren Lowerbound und wird daher bevorzugt.

(Math.hypot(a, b) ist Wurzel(a^2 + b^2))