# A maze generator and solver written in Python

## 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

### Visualised

### 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

### Example

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.