The A*star path planning algorithm is a popular and efficient graph traversal and search algorithm that was developed in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael of the Stanford Research Institute. I have always been fascinated by the efficiency and complexity of search algorithms and this interest led me to try and implement the algorithm myself in an interesting and visual way.
Rule of exspansion - Expand node with lowest f value, aka node that is close to the straightest diagonal path from the start node to end node put simply
Hueristic used is Manhanntan Distance
To do this I used, the py-game python module for the visualization aspect.
The use of methods in Data Structures & Algorithms and Priority Queues were crucial in the implementation of the actual A* algorithm.
-
Python 3.6 and up
-
Py-game library (latest version)
-
Math library
-
Priority Queue library
-
After running the program;
-
Select the starting node from which the A* algorithm should begin the search.
-
Select a goal/end node at which the A* algorithm will attempt to reach.
-
Select barrier nodes that will represent obstacles that the algorithm must traverse to reach the goal node. (These will appear black in colour)
-
Hit the space bar and enjoy the visualization of the searching process.