Maze Creator / Solver
A maze generator and solver written in Python, which uses a backtracker algorithm and Djikstra's algorithm.
It can be described with following steps
- Choose the initial cell, mark it as visited and push it to the stack
- While the stack is not empty
- Pop a cell from the stack and make it a current cell
- If the current cell has any neighbours which have not been visited
- Push the current cell to the stack
- Choose one of the unvisited neighbours
- Remove the wall between the current cell and the chosen cell
- Mark the chosen cell as visited and push it to the stack
Analysis of Algorithm
This algorithm has a time efficiency of O(n^2)
Maze Solver Algorithm
To solve the mazes, I used Dijkstra's shortest path algorithm, this algorithm utilises a priority queue data structure.
It can be described with the following steps
- Choose a start and end node, all nodes other than start node have a distance of infinity
- Consider each adjacent node to the current node, and update the distance of the node
- The new distance is the distance of the current node + distance from current node to new node
- If the new distance is smaller the node's distance already, don't update
- The priority queue shifts all the nodes into order based on their distance values
- Dequeue a node from the queue and start again from step 2
Here is a 500x500 maze generated (Image size is 1001x1001) using the maze generation algorithm as described further above. And it has been solved using the Dijkstra's algorithm implemented in this project.