Presented at the 2019 GDC AI Summit.
To compute paths for virtual characters we often transform a continuous environment into a simplified grid or a navigation mesh. However, pathfinding algorithms developed for grids and meshes usually return only approximate shortest paths, with unnecessary detours and additional turns being common side-effects. In this session, the speaker will discuss a range of "any-angle" techniques that can help you overcome such difficulties. The presentation will also describe Anya and Polyanya, two new algorithms which not only guarantee to compute actual shortest paths but which can also run 10-100+ times faster than traditional grid-based A* search.
Daniel's website:
harabor.net/daniel
For reference implementations of Anya and Polyanya please visit:
bitbucket.org/dharabor/pathfi...
References:
String Pulling:
Pinter, M., 2001. Toward more realistic pathfinding. Game Developer Magazine, 8(4).
(Link: web.archive.org/web/2013060614...)
Theta*:
Nash, A., Daniel, K., Koenig, S. and Felner, A., 2007, July. Theta^*: Any-angle path planning on grids. In AAAI (Vol. 7, pp. 1177-1183).
(PDF: idm-lab.org/bib/abstracts/pape...)
SUB-TL:
Uras, T. and Koenig, S., 2015, April. Speeding-up any-angle path-planning on grids. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 25, pp. 234-238).
(PDF: ojs.aaai.org/index.php/ICAPS/...)
Anya:
Harabor, D.D., Grastien, A., Öz, D. and Aksakalli, V., 2016. Optimal any-angle pathfinding in practice. Journal of Artificial Intelligence Research, 56, pp.89-118.
(PDF: www.jair.org/index.php/jair/a...)
Polyanya:
Cui, M., Harabor, D.D., Grastien, A. and Data61, C., 2017, August. Compromise-free Pathfinding on a Navigation Mesh. In IJCAI (pp. 496-502).
(PDF: www.ijcai.org/Proceedings/201...)
27 июл 2024
