Performance Issues And Gains Of Caching The Pathfinding Data

Ivan Porkolab, Goran Djambic, Danijel Kucak

Abstract


Using non-cached methods for finding the shortest path between nodes is the most common case when using pathfinding systems. That approach generates a couple of issues. Foremost, it has a significant impact on processing resources as calculations must be done over again for each iteration, even for the repeating events. That’s not a big concern if pathfinding is invoked a reasonable number of times or the nodes involved are always different, but if pathfinding occurs many times on the same nodes, then the caching of once calculated path becomes an acceptable course of action. This paper has explored one of such caching algorithms, FAST-N algorithm and compared it with standard non-cached pathfinding. Doing so, it outlined margins of justifiable use of such systems.
On a small number of pathfinding requests or simple node structure, because of increase in memory usage and rather hefty initial calculation processing requirements, it has been concluded that non-cached system makes more sense than cached one. On the other hand, when confronted with a large number of pathfinding requests and more complex node structure, caching can generate significant benefits concerning processing power and speed.


Keywords


Pathfinding, Caching, FAST-N, C#

References


Gravot, F., Yokoyama, T. and Miyake Y. (2015). Precomputed Pathfinding for Large and Detailed Worlds on MMO Servers, Available from: https://pdfs.semanticscholar.org/aa57/155e58202a5d4b67d05d6bc96cd4b0dce9c7.pdf. Accessed: (2018-09-08).

Yukhimets, D., Zuev, A. and Gubankov, A. (2017). Method of Spatial Path Planning for Mobile Robot in Unknown Environment, Proceedings of the 28th DAAAM International Symposium, pp.0258-0267.

Li, X. H., Hong, S. H. and Fang, K. L. (2011). WSNHA-GAHR: A greedy and A* heuristic routing algorithm for wireless sensor networks in home automation, IET Communications, vol. 5, no. 13, pp. 1797–1805.

Demyen. D. and Buro M. (2006). Efficient Triangulation-Based Pathfinding. Available from: https://skatgame.net/mburo/ps/tra.pdf. Accessed: (2018-09-07).

Goldberg A.V. and Harrelson C. (2005). Computing the Shortest Path: A* Search Meets Graph Theory, Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA ’05), pp. 156-165.

Johnson D. and McGeoch L. (1997). The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization, pp. 215-310.

Talan K. and Bamnote G. R. (2015). Shortest Path Finding Using a Star Algorithm and Minimum weight Node First Principle, Available from: http://www.rroij.com/open-access/shortest-path-finding-using-a-star-algorithmand-minimum-weight-node-first-principle.php?aid=56299. Accessed: (2018-05-05).

Goldberg A.V., Kaplan H., Werneck R.F. (2006). Reach for A*: Efficient Point-to-Point Shortest Path Algorithms. Proc. SIAM Workshop Algorithms Eng. and Experimentation, pp. 129-143.

Dickheiser, M. (2003). “Inexpensive precomputed pathfinding using a navigation set hierarchy.” In AI Game Programming Wisdom 2, MA: Charles River Media, 2003, pp. 103–113.

[4] Björnsson, Y., Bulitko, V. and Sturtevant N. (2009). Time-Bounded A*. Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09). pp. 431-436.


Full Text: PDF

Refbacks

  • There are currently no refbacks.
x
Message