TY - CHAP
T1 - Improving the Cache-Efficiency of Shortest Path Search
AU - Edelkamp, Stefan
PY - 2017/9/19
Y1 - 2017/9/19
N2 - Flood-filling algorithms as used for coloring images and shadow casting show that improved locality greatly increases the cache performance and, in turn, reduces the running time of an algorithm. In this paper we look at Dijkstra’s method to compute the shortest paths for example to generate pattern databases. As cache-improving contributions, we propose edge-cost factorization and flood-filling the memory layout of the graph. We conduct experiments in commercial game maps and compare the new priority queues with advanced heap implementations as well as and with alternative bucket implementations.
AB - Flood-filling algorithms as used for coloring images and shadow casting show that improved locality greatly increases the cache performance and, in turn, reduces the running time of an algorithm. In this paper we look at Dijkstra’s method to compute the shortest paths for example to generate pattern databases. As cache-improving contributions, we propose edge-cost factorization and flood-filling the memory layout of the graph. We conduct experiments in commercial game maps and compare the new priority queues with advanced heap implementations as well as and with alternative bucket implementations.
UR - http://www.scopus.com/inward/record.url?scp=85030837682&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-67190-1_8
DO - 10.1007/978-3-319-67190-1_8
M3 - Other chapter contribution
AN - SCOPUS:85030837682
SN - 9783319671895
VL - 10505 LNAI
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 99
EP - 113
BT - KI 2017: Advances in Artificial Intelligence - 40th Annual German Conference on AI, Proceedings
PB - Springer Verlag
T2 - 40th Annual German Conference on Artificial Intelligence, KI 2017
Y2 - 25 September 2017 through 29 September 2017
ER -