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.


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.



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.



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


This article is issued from Wikipedia - version of the 10/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.