Akritean distance

In computer science, the Akritean distance or akrdis is a combination of the Euclidean and the Manhattan distance, designed for use in path finding algorithms as the heuristic distance function.

The idea is that Euclidean distance has better results in mostly empty areas and Manhattan in more filled areas, so a combination can be created based on the coverage of the area in each scenario.

Definition

The full extended definition:

akrdis(x1, y1, x2, y2, a) = sqrt(pow2(x2-x1) + pow2(y2-y1))*(1-a) + (abs(x2-x1) + abs(y2-y1))*a

The definition based on the Euclidean and the Manhattan distances:

akrdis(x1, y1, x2, y2, a) = euclidean(x1, y1, x2, y2)*(1-a) + manhattan(x1, y1, x2, y2)*a

The a parameter describes the ratio of the accessible area to the total area or simply the coverage of the area.

Properties

Dynamic

In scenarios with multiple calculations distance, the a parameter can be updated as new information about the coverage of the area are revealed or estimated.

Applications

Pathfinding

In pathfinding algorithms like A*, the Akritean distance can be used as the needed heuristic function in order to approximate distances. The Euclidean and the Manhattan distance are cheaper to calculate but the Akritean distance has a lower average error in the approximations. However with the a parameter near 0 or 1 the Akritean distance only adds cost.