Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Modification of JPS+ Algorithm for Optimal Pathfinding on Uniform-Cost Grids. / Iakushkin, Oleg; Tazieva, Lilia; Eremin, Alexey S.; Balabanov, Mikhail.
Proceedings of the 3rd International Conference on Applications in Information Technology, ICAIT 2018. ed. / Klyuev Vitaly; Pyshkin Evgeny; Natalia Bogach. New York, NY, USA : Association for Computing Machinery, 2018. p. 131-134 (ACM International Conference Proceeding Series).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
}
TY - GEN
T1 - Modification of JPS+ Algorithm for Optimal Pathfinding on Uniform-Cost Grids
AU - Iakushkin, Oleg
AU - Tazieva, Lilia
AU - Eremin, Alexey S.
AU - Balabanov, Mikhail
N1 - Publisher Copyright: © 2018 Association for Computing Machinery.
PY - 2018/11/1
Y1 - 2018/11/1
N2 - Pathfinding is a widespread task in many domains, including computer games, robotics and road maps. This paper describes the work of JPS+ algorithm and puts forward its modifications allowing to reduce pathfinding time. We propose to use a visibility graph to modify the map pre-processing logic at the stage of Primary Jump Points calculation. The paper also puts forward modifications in the shortest path algorithm solved for two points: the logic of Target Jump Points work and Primary Jump Points filtering has been altered to deal with obstacles. We propose an open-source software solution that accommodates the modifications.
AB - Pathfinding is a widespread task in many domains, including computer games, robotics and road maps. This paper describes the work of JPS+ algorithm and puts forward its modifications allowing to reduce pathfinding time. We propose to use a visibility graph to modify the map pre-processing logic at the stage of Primary Jump Points calculation. The paper also puts forward modifications in the shortest path algorithm solved for two points: the logic of Target Jump Points work and Primary Jump Points filtering has been altered to deal with obstacles. We propose an open-source software solution that accommodates the modifications.
KW - A
KW - Grid
KW - JPS
KW - JPS+
KW - Pathfinding
UR - http://www.scopus.com/inward/record.url?scp=85058651886&partnerID=8YFLogxK
U2 - 10.1145/3274856.3274883
DO - 10.1145/3274856.3274883
M3 - Conference contribution
SN - 978-1-4503-6516-1
T3 - ACM International Conference Proceeding Series
SP - 131
EP - 134
BT - Proceedings of the 3rd International Conference on Applications in Information Technology, ICAIT 2018
A2 - Vitaly, Klyuev
A2 - Evgeny, Pyshkin
A2 - Bogach, Natalia
PB - Association for Computing Machinery
CY - New York, NY, USA
T2 - 3rd International Conference on Applications in Information Technology, ICAIT 2018
Y2 - 1 November 2018 through 3 November 2018
ER -
ID: 36504871