Details

A Demonstration of Parallel Path-Finding Algorithms on a Grid-Based Map Through an Interactive Application

Year: 2014

Term: Winter

Student Name: Mark Murillo

Supervisor: Frank Dehne

Abstract: Pathfinding, or finding the shortest path between two points, is a common problem in video game development in addition to others areas of computer science such as networking. As the video game industry advances, video game maps are becoming increasingly more complex and larger in scale. With the rise in multicore processors, it is only natural to make an attempt to parallelize pathfinding solutions and decrease runtimes. The goal of this project was to provide a visualization of the prominent pathfinding algorithm A* and the parallel variation Parallel Bidirectional Search (PBS). To do this, a program was created with several different features to help people better understand how these algorithms work. The implementation of PBS used in this project differed from previous implementations used in literature with regard to the handling of shared meta-data between processing cores. In the end, this variation proved detrimental to the algorithm’s performance and resulted in consistently higher runtimes for PBS in comparison to A*. It can thus be concluded that a greater emphasis on the handling of shared meta-data must be taken into account for people who look to implement PBS as well as parallel pathfinding algorithms in general.