octile

Octile is a distance metric used in grid-based pathfinding where movement is allowed in eight directions: north, south, east, west and the four diagonals. In such grids, a straight (cardinal) move costs 1 and a diagonal move costs sqrt(2). The octile distance between two grid cells with coordinates (x1, y1) and (x2, y2) is computed from dx = |x1 - x2| and dy = |y1 - y2| as D = max(dx, dy) + (sqrt(2) - 1) * min(dx, dy). Equivalently, D = (max(dx, dy) - min(dx, dy)) + sqrt(2) * min(dx, dy). This formula captures the fact that you can take up to min(dx, dy) diagonal steps and then the remaining straight steps.

Properties and usage: Octile distance is a metric for eight-direction grids and serves as an admissible and consistent heuristic in A* search when diagonal costs are sqrt(2) and straight costs are 1. It provides a closer approximation to Euclidean distance than the Manhattan or Chebyshev metrics on such grids. If all eight moves had the same cost, the Chebyshev distance would apply; if only cardinal moves were allowed, Manhattan distance would apply. The octile metric thus sits between these two in terms of tightness as a heuristic for grid pathfinding.

Applications: It is widely used in game AI, robotics, and other domains that involve planning shortest paths on square grids with diagonal movement. Practical implementations often precompute or inline the formula for efficiency.

Example: From (0,0) to (3,4), dx=3, dy=4, so D = 4 + (sqrt(2)-1)*3 ≈ 5.24.