Maze solver or pathfinding algorithm

This repository contains the implementation and visualization of the primitive pathfinding algorithm.

Problem

Given a space with passages and walls, an entry point and an exit point are also given, you must find a path from start to finish through free cells.

We can divide this task into 3 subtasks:

1. Generate given space (maze)
2. Implement a pathfinding algorithm
3. Create visualization of this algorithm

(1) Maze example

Description to image (1)

• ⬛ black — walls
• ⬜ white — passages
• 🟩 green — entry point (start)
• 🟪 magenta — exit point (finish)
• 🟥 red — iterations (steps)
• 🟦 cyan — path

Algorithms

1. Generate maze

Given the width and height of the maze we want to create.
So, to begin with, randomly generate an entry point (start) and an exit point (finish).
Then we create a matrix of ones (maze), in the further implementation we will denote 0 as a passage, and 1 as a wall. We set a labyrinth of some walls.

(2) Maze matrix initialization

Set the matrix element mazestart.x start.y = 0 and also denote by (current.x, current.y) the current position in the maze matrix.
Until we reach the finish (current.x, current.y) ≠ (finish.x, finish.y), then we take a random cell from the list of passed cells and a random direction of movement: up, down, left, right; we check whether we can go in this direction, if not, then we change the direction of movement until the desired direction is found, we move in the chosen direction.
Thus, at each iteration, we move in a random direction of a random cell until we find the finish. We destroy the walls.

2. Naive pathfinding algorithm

First, we create a zero matrix with the size: width × height
We put 1 at the starting point, in all positions around 1 we put 2 if there is no wall (we check this by our maze matrix), around 2 we put 3, also if there is no wall, and so on until we reach the finish point and that number, which will stand at the finish point is the minimum length of the path from start to finish.
Now it remains to find the path according to the matrix of steps that we received. To do this, you need to reach the finish point, let's say we reached in k steps, you need to find an adjacent cell with a value of k - 1, go there, decrease k by 1 and repeat this until we get to the starting point, namely 1.

Example

(3) Maze (10×10)

Maze matrix on the example of an image (3)

[
  [0, 0, 0, 0, 0,  0,  0,  0, 0, 0],
  [0, 0, 0, 0, 0, 10,  0,  0, 0, 0],
  [0, 0, 0, 0, 8,  9, 10,  0, 0, 0],
  [0, 0, 0, 0, 7,  0,  0,  0, 0, 0],
  [0, 0, 0, 7, 6,  0,  0,  0, 0, 0],
  [0, 0, 0, 6, 5,  4,  0,  0, 0, 0],
  [0, 0, 6, 5, 4,  3,  4,  0, 0, 0],
  [0, 6, 5, 0, 3,  2,  0,  0, 0, 0],
  [0, 5, 4, 3, 2,  1,  0,  0, 0, 0],
  [0, 0, 0, 0, 0,  0,  0,  0, 0, 0]
]

Example

Code

App(className="Maze", width=50, height=30, zoom=6)

Result

(4) Example of the program

Dependencies

All dependencies are listed in the file requirements.txt.

License

maze is licensed under the MIT License.