Search code examples
algorithmpath-findinga-star

Does Manhattan path finding supports diagonal movement?


Can someone explain whether diagonal movement is supported in Manhattan Distance Metric?


Solution

  • An admissible heuristic must never overestimate the distance.

    Consider a start of 0,0 and a destination of 10,10.

    The Manhattan distance metric is 10+10=20, which is an overestimate of the true distance if diagonal moves are allowed.

    Therefore the Manhattan distance is not an admissible heuristic for A* when diagonal movement is allowed.