Pathfinding bugs

[adituv]

I am now pretty sure the heuristic used for the A* algorithm here is inadmissible as it overestimates in some cases, such as a diagonal move.

For example, moving from (1,1) to (2,2), the heuristic returns 2, while the actual cost is either 1 or sqrt(2) depending on how you want to value it, if we do allow diagonal movement (as I assume we do).

Instead we could use something like this:

h :: Position -> Position -> Int
h ( x1, y1 ) ( x2, y2 ) =
  let
    dx = abs (x1 - x2)
    dy = abs (y1 - y2)
  in
    -- Travel diagonally most of the way, then the rest along an axis
    (min dx dy) - abs (dx - dy)

What do you think? Am I misremembering the A* heuristic's requirements?

[krisajenkins]

Ah, you're right. That's my memory at fault - I thought it was inadmissible if it underestimated. Wikipedia says points to you. I should have checked originally. :-}

Ha, now I check it looks like I got the docstring right but the code wrong. Oh dear...

But...shouldn't the in clause there just be max dx dy?

If dx=3 and dy=10 and diagonal is 1 step, then the correct answer is 10, but that in clause would give -4, no?

[adituv]

Yes you're absolutely right. I was rushing while dinner was nearly ready and got distracted.

There's still something weird with the max solution though as walking Down-Right chooses a down-right alternating path, while Up-Left moves diagonally as expected

[adituv]

Found it - you're missing the case ( x + 1, y + 1 ) in movesFrom.

[krisajenkins]

Okay, that's live. :-)