Pathfinding-test Repository

Welcome to the Pathfinding-test repository, which includes the code for mine and Demian Skoglövs bachelor thesis titled "Opportunities for improvement in Dijkstra's pathfinding algorithm." This study, written in Swedish, compares the efficiency of various graph search algorithms in a two-dimensional grid-based environment. Below, you'll find a brief summary of the thesis, along with visualizations and descriptions of the pathfinding algorithms explored.

Thesis Summary

This study compares the efficiency of the following graph search algorithms:

• Dijkstra
• Bidirectional Dijkstra
• A*
• Bidirectional A*
• Jump Point Search (JPS)

By analyzing their performance based on execution time and the number of expanded nodes, the study aims to identify the efficiency improvements these algorithms offer. The results show significant performance differences between the algorithms, with JPS being 7235% faster than Dijkstra on a 1000x1000 grid map. This highlights the relevance of these improvements in gaming, where milliseconds matter. The bidirectional versions of Dijkstra and A* are also more efficient than their unidirectional counterparts, improving execution time by approximately 50%, validating the value of these improvements. Future research may include exploring additional algorithms and improvements, as well as their application and testing in real-time scenarios to further validate and develop these results.

Visualizations

Below are visual representations of the five pathfinding algorithms used in the study. The first image shows all five algorithms at once in the order mentioned above, and the subsequent GIFs illustrate how each algorithm explores the area.

All Pathfinding Algorithms

Dijkstra's Algorithm‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎‎ ‎‎ ‎ ‎ Bidirectional Dijkstra's Algorithm

‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎

A* Algorithm‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎‎ ‎ ‎ ‎ ‎ ‎ ‎‎ ‎ ‎ Bidirectional A* Algorithm

‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎

‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎‎ ‎ ‎ ‎ Jump Point Search (JPS) Algorithm

‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎‎ ‎ ‎‎ ‎ ‎‎‎ ‎ ‎ ‎

Repository Contents

This repository contains the following:

• Source code for implementing and testing the pathfinding algorithms.
• Scripts for generating and comparing execution times and node expansions.
• Visualization tools for displaying the pathfinding process.

Getting Started

To get started with this repository, follow these steps:

1. Download Unity: Download Unity version 2021.3.4f1

2. Clone the repository:

   git clone https://github.com/kmaxii/Pathfinding-Tests.git

3. Run the project You can run the tests to compare the algorithms by clicking play in the Unity editor. The different pathfinding algorithms are put in scriptable object which can be activated or deactivated.

License

This project is licensed under the Apache-2.0 license License. See the LICENSE file for details.

Acknowledgements

This repository is part of my bachelor thesis at Högskolan i Skövde. Special thanks to our advisor, Andreas Jonasson, for their guidance and support.

For more details, you can read the full thesis here.

Thank you for visiting the Pathfinding-test repository!