As part of the Bachelor of Computer Science program at the Algorithms and AI Lab, this project focuses on the implementation and comparative analysis of pathfinding algorithms in a 2D grid map environment. The project involves creating Dijkstra's algorithm, the A* algorithm, and the Jump Point Search (JPS) algorithm using C#.
The core objective is to explore these algorithms' efficiency and performance characteristics in determining the shortest path on a grid-based map, which could be comparable to urban road networks. The application will require a defined starting and ending point on the grid to conduct pathfinding tasks. Through this implementation, the project aims to evaluate the speed and effectiveness of each algorithm, providing a comparative study of their results in practical scenarios.
Original study paper:
Online Graph Pruning for Pathfinding on Grid Maps by Daniel Harabor and Alban Grastien
Original JPS algorithm:
Original blog post series by Daniel Harabor:
Maps:
2D Pathfinding Benchmarks by Nathan Sturtevant's Moving AI Lab
Additional references:
Introduction to the A* Algorithm from Red Blob Games
A Visual Explanation of Jump Point Search by Nathan Witmer
Jump Search Algorithm in Python – A Helpful Guide with Video by Matija Horvat