Benchmarks for Grid-Based Pathfinding
Nathan Sturtevant · IEEE Transactions on Computational Intelligence and AI in Games · 2012
The study of algorithms on grids has been widespread in a number of research areas. Grids are easy to implement and offer fast memory access. Because of their simplicity, they are used even in commercial video games. But, the evaluation of work on grids has been inconsistent between different papers. Many research papers use different problem sets, making it difficult to compare results between papers. Furthermore, the performance characteristics of each test set are not necessarily obvious. This has motivated the creation of a standard test set of maps and problems on the maps that are open for all researchers to use. In addition to creating these sets, we use a variety of metrics to analyze the properties of the test sets. The goal is that these test sets will be useful to many researchers, making experimental results more comparable across papers, and improving the quality of research on grid-based domains.
Cited by 549 works. doi:10.1109/tciaig.2012.2197681
Authors
References
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
- Near Optimal Hierarchical Path-Finding.
- Reach for A*: Efficient Point-to-Point Shortest Path Algorithms
- Partial pathfinding using map abstraction and refinement
- Highway dimension, shortest paths, and provably efficient algorithms
- Memory-Efficient Abstractions for Pathfinding
- Memory-based heuristics for explicit state spaces
- Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
- Ultrafast shortest-path queries via transit nodes
- Euclidean Heuristic Optimization