Maze Generation and Solving in Python
After running the application a blank canvas will appear with a green and a red square at two opposing corners of the grid. The green cell will be the inital cell whilst the red cell will be the terminal cell. The user can move either cell by dragging and dropping:
Once we have chosen suitable start and end cells, click the Create to generate the maze. The application uses the Recursive Division algorithm.
In addition is it possible toggle wall cells with the mouse pointer:
Once the maze has been fully generated, click the DFS or BFS buttons to calculate a path between the initial and terminal cell. In all cases cells that have been visited will appear in yellow whilst the final path will appear in blue.
The DFS button will perform a depth first search between initial and terminal cells. Note that the algorithm will terminate as soon as a valid path is found, rather than strictly finding the optimum path. Finally, depth first searching is the least efficient method of solving this type of problem and requires a lot of stack-space.
The BFS button will perform a breadth first search between initial and terminal cells.
The program uses the following libraries:
pygame (Tested with v1.9.6)
numpy (Tested with v1.18.3)
Hopefully pip should do the trick...
pip install pygame
pip install numpy