The goal of this project is to clearly demonstrate the functionality of the most renowned artificial intelligence algorithms for finding the shortest path between 2 or more points. The use case involves a vehicle navigating to one or more points in space, avoiding obstacles such as walls and trying not to waste too much time at traffic lights. The reference model is an undirected and weighted graph. The implemented algorithms consist of 5 variants, covering a range of types including heuristic, exact, informed, uninformed, and greedy algorithms.
- Breadth First Search
- Depth First Search
- Uniform Cost Search
- A star Search
- Greedy Best First Search
This tool was also used to explain search algorithm concepts to younger computer science students (the visualization is done with the PyGame library).
The main focus of the peroject is to visualize the algotihms working, trying to be as clear as possible. The possibility to move the starting and ending points, as well as the obstacles, after the search ended is useful to see the different reasoning done by different algoritmhs.
There is also the possibility to automatically generate a random maze and to find the best path in that specific situation.
I decided to implement a min heap for the priority queue from scratch so that the project would be completely customizable for my needs, specifically to visualize the algorithms in the best possible way.
Here you can see an example on how to use this tool