• Create Account

### #Actualjefferytitan

Posted 17 September 2012 - 07:39 PM

I'd suggest simple Euclidean distance. Think about how the cost estimate works. You take the distance traveled so far plus the heuristic of the rest of the distance. If you use Manhattan distance and a cost of 14 for diagonal, this is how it pans out:
• Travelling 1 unit horizontally towards the target costs 10 and gets you 10 closer.
• Travelling 1 unit vertically towards the target costs 10 and gets you 10 closer.
• Travelling 1 unit diagonally towards the target costs 14 and gets you 20 closer.
So of course it would pick diagonal paths first.

Edit: Also I believe that using the Manhattan distance if a unit can travel diagonally actually makes it an inadmissible heuristic. The heuristic should never overestimate the remaining cost. Not that I'm morally against inadmissible heuristics - they can cut down the search space nicely. But they aren't good if you're doing them by accident.

### #1jefferytitan

Posted 17 September 2012 - 06:13 PM

I'd suggest simple Euclidean distance. Think about how the cost estimate works. You take the distance traveled so far plus the heuristic of the rest of the distance. If you use Manhattan distance and a cost of 14 for diagonal, this is how it pans out:
• Travelling 1 unit horizontally towards the target costs 10 and gets you 10 closer.
• Travelling 1 unit vertically towards the target costs 10 and gets you 10 closer.
• Travelling 1 unit diagonally towards the target costs 14 and gets you 20 closer.
So of course it would pick diagonal paths first.

PARTNERS