Algorithms for Solving the Quick Path Finding Problem on Geographic Maps
Authors: Basarab M.A., Domracheva A.B., Kuplyakov V.M.
Published in issue: #11(23)/2013
DOI: 10.18698/2308-6033-2013-11-1054
Category: Information technology
For a pre-processed landscape, algorithms of path finding between two points, taking into account terrain passability, are considered. This paper describes the methods that can be divided into the following classes: algorithms for finding the shortest path (Dijkstra et al.) and algorithms for finding a suboptimal path (A * and its modifications, in particular, Theta*); postprocessing algorithms routes (removal of points lying on a direct line - Line of Sight). Particular attention is paid to the heuristic algorithm which finds near-optimal and sufficiently realistic looking route. The landscape interpreting is given. Conclusions are drawn on the applicability of certain algorithms and their combinations. In this work, with the help of the special software, a comparative analysis of different methods of path finding is carried out, with respect to such parameters as path length, path complexity, number of turning points, total angle of deviation.