Maze Runner

The Project

This site employs the usage of the A* search algorithm for efficient path-finding encompassing a heuristic distance (both Manhattan and Euclidian available and a path cost) as per the start cell, goal cell, and obstructions. The grid of cells exhibits the color-changing behaviour via JavaScript, and Jinja and Flask with AJAX are used to dynamically render content onto the webpage. The search algorithm is implemented in a separate Python script. An A* algorithm is an extremely efficient, path-finding algorithm determined to find the shortest path between two points (if implemented correctly) by constantly expanding on the ideal next node, which is determined to be close to the starting point and (approximately) closer to the goal than other available options among all explored options. The project was inspired as a deep dive into path-finding algorithms such as this and others like DFS, BFS, or greedy. Initially, it was done with the help of matplotlib, but it eventually turned into a webpage hosted on the internet. A major difficulty was understanding how to practically apply the concept of expanding on the ideal node at each step from the explored nodes in the algorithm. Initially, I used the heap library in Python. However, I later with more knowledge of classes and object-oriented programming was able to make a PriorityQueue class of the same function. Another difficulty was the implementation of the backtracing after reaching the goal but after learning about object attributes and tracking parent nodes, it became a breeze. Furthermore, a major difficulty was enabling the behaviour of swapping the goal and start cell on the webpage while the user draws up the maze, but it was eventually overcome. This project is published on the internet with the help of PythonAnywhere and can be viewed at: https://aayan0207.pythonanywhere.com/maze_runner

View this project on YouTube