Parallel Ripple Search

Project by Gavin Gray, Lorenzo Liso, Dario Mylonopoulos, Ishaan Shamanna and Lucas Weitzendorf for the course Design of Parallel and High-Performance Computing (263-2800-00L) HS 2021 at ETH Zurich.

Build

The project requires CMake version 3.16 (or newer). The repository and all the submodules can be cloned with the following command:

git clone --recursive <url>

Due to the long compilation time of oneTBB, it was not included as a build dependency. If a version of oneTBB is not already present on your system, it can be built and installed with the following commands (see here for the complete installation reference):

cd oneTBB
mkdir build && cd build
cmake ..
make
sudo make install

Parallel Ripple Search and the other binaries can then be built with the following commands from the root directory of the repository:

mkdir build && cd build
cmake ..
make

Run

The build process described above produces the following binaries in the build directory

./bench # Runs the benchmarks for each algorithm and outputs measurements into <algorithm>.lsb
./graph_view <file path> <source> <goal> # Runs the algorithms and displays results
./high  # Generates the high level graph and displays it on top of the original graph

Project Structure

The source code is structured as follows:

• src/benchmark: utilities for loading benchmark data
• src/bin: source code for the output binaries
• src/graph: graph and map data structures
• src/reference: source code of reference implementations of pathfinding algorithms
• src/ripple: Parallel Ripple Search implementation
• src/utility: utilities for data structures, parsing, and performance measurement

Dependencies

• oneTBB - concurrent queues
• LibSciBench - performance measurement
• GLM - math utils
• Raylib - UI and visualization

References

[1] Sandy Brand and Rafael Bidarra, “Parallel ripple search – scalable and efficient pathfinding for multi-core architectures”, in Proceedings of the 4th International Conference on Motion in Games, Berlin, Heidelberg, 2011,MIG’11, p. 290–303, Springer-Verlag.

[2] Nathan R. Sturtevant, “Benchmarks for grid-basedpathfinding”, IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 2, pp. 144–148,2012.

[3] Yngvi Bjornsson, Markus Enzenberger, Robert Holte and Jonathan Schaeffer, “Fringe search: Beating a* atpathfinding on game maps.”, 01 2005