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.
See also
References
- "Akritean distance". October 18, 2016.