Python project that visualizes maze generation and multiple path-finding algorithms.
Main program exectution is found in Driver.py. Press any button to step through program execution. After the maze has been solved, use the exit button to exit the program.
MAZE_WIDTH and MAZE_HEIGHT are used to specify maze dimensions. Window size readjusts to fit any maze size. Mazes that are too big will go off-screen.
generate and solve refer to the generation and pathfinding algorithms, respectively. To change algorithms, substitute the extension for the names described below.
animateGeneration and animateSolution alter whether generation steps and pathfining steps will be shown. True -> show steps. False -> skip steps
Currently the only supported generation algorithm.
Generates a path until there are no ways to go, then backtracks until it can create a different path.
Mostly results in mazes with long, windy trails.
gray: maze walls. Cursor cannot go through them
white: maze halls. Cursor can move through them
red: points the maze's entrance and exit
As the name suggests, this algorithm works by prioritizing making right turns over anything else.
It will often give the impression of wandering aimlessly... and it's pretty much doing that. It does not know where the exit is found, so it will go around until it finds it.
Not super efficient and only works if all parts of the maze are connected by walls (no "islands").
orange: algorithm's current position
cyan: areas previously visited by the algorithm
blue: shortest path from the entrance to the exit
A* pathfinding algorithm.
This algorithm works by stepping through the maze and moving through the path with the least cost. The cost of a path is determined by how far away the path moves from the entrance, and how close to the exit the path gets.
orange: cells in line to be evaluated. The one with the lowest cost is picked to be evaluated next
cyan: nodes that have been evaluated
blue: shortest path from the entrance to the exit
To run the program, you need to have pygame installed on your computer.
To install, run python3 -m pip install -U pygame --user