Comparing Pathfinding Algos

Inspiration

My inspiration for this project was based on my general interest in Artificial Intelligence which later branched out to things like reinforced learning. While going through this rabbit hole, I found many different games which were completed by programs that had learned things called "pathfinding" on their own. A specific example of this was the game snake which a snake was able to fill up a whole board using a strategy based on pathfinding. After this, I was inspired to learn a lot more about these techniques and I learned a lot about different examples of pathfinding and its uses while creating this project.

What it does

My program is split into 3 different files which each help the user visualize the differences and strategies that the different algorithms use to successfully achieve the quickest path between the starting and the ending node.

How we built it

I built this using python with an imported library called pygame which helped with the visualization aspect of this project. Inside each algorithm, there are several classes that are used for this project to break it up into smaller pieces (which is generally the goal of OOP)

Challenges we ran into

One major challenge that I ran into while programming this project was the calculation of the heuristic function/manhattan distance used in node weights for the A* program. While even now I'm not sure I factored in diagonal node weights, I think my final program runs smoothly. I also struggled a lot with a smooth user interface as I could never get my grid pattern to line up with the side of the widget window.

Accomplishments that we're proud of

A big accomplishment I am proud of is that I didn't think that I would be able to program three different pathfinding algorithms. While the Dijkstra algorithm program's weights aren't quite where I want them to be, it's better than my original plan where I was only going to present one pathfinding algorithm (DFS).

What we learned

Coming into this hackathon, I barely knew anything about pathfinding, however, through the last 24 hours, I basically built an entire project from scratch that I never would've known about a day prior. I also learned a lot about pygam and UI with python.

What's next for Comparing Pathfinding

In the future, I hope to turn this simple python project into a full-fledged app that is able to help the user visualize the differences between these algorithms in real-time. I also, in the future, would like to make my own version of google maps in order to give my program some real-world use. Finally, I would also like to add time complexity challenges for the algorithms.

(When running the program, the first click on a space is the starting node, the second click is the ending node, every other click are non-traversable walls, space bar is to run, and finally 'C' character to clear the board)

Thank you and enjoy!

Built With

• python