Benchmarks for Grid-Based Pathfinding

摘要

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.