Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

Algorithms for Solving the Quick Path Finding Problem on Geographic Maps

Published: 19.11.2013

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.