search

jostbr / pymaze

A maze generator, solver and visualizer for Python
MIT License
265 stars 61 forks source link

Added Binary Tree Algorithm for Generating Mazes #36

Closed AshishS-1123 closed 3 years ago

AshishS-1123 commented 3 years ago

Changes Made

Why?

There are a lot of different algorithms for creating mazes and solving them and each of these algorithms have their pros and cons. To make this repository complete, it is necessary to include as many of these algorithms as possible.

How?

  1. To make the code more intuitive to read and understand, the present algorithm for generating maze has been removed from src/maze.py and moved to src/algorithm.py as a separate function.
  2. In addition to that, an optional parameter algorithm has been given to the constructor of Maze. The default value for this parameter is dfs_backtrack and uses the depth first search method to generate the maze. This way, any code relying on previous versions of the repo can still function.
  3. If the user wants to use some other method for generating their maze, they can give a different value for this parameter. For using the Binary Tree Method, the value to be passed to the constructor is bin_tree.

The Binary Tree Algorithm

The binary tree algorithm is very simple and involves looping through all cells in the maze only once.

  1. We visit each cell in the maze serially.
  2. For each cell randomly choose between removing the top wall or right wall.
  3. For cells in the topmost row, we cannot remove the top wall as that would open the maze. So we remove only right walls for these cells.
  4. For cells in the rightmost column, we do the same with right walls.
  5. Since there is no correct order for visiting the cells, we visit them serially using 2 for loops.

The Generation Path Algorithm

In this algorithm, we are visiting the cells serially, row by row. But for showing the path generation animation, we cannot use this path, because it generates the wrong results.

Instead, we use a hack that generates the correct maze and sheds some light on why the algorithm is called binary tree algorithm.

The Binary Tree Algorithm is called so because, the maze generated can be represented as a binary tree. To understand this better, consider the following maze generated using the binary tree method. Figure_1

This maze can be represented as a binary tree as follows,

  1. The cell in top right corner is the head of the tree.
  2. This cell has two children, one on the left and one on the bottom.
  3. So, if we visit the head cell first, then its children and so on, we are left with a binary tree.
  4. Since at each cell we choose between the top wall and right, each cell has at most 2 children.

So, in the generation algorithm, I have used this concept and traversed the maze using dfs as can be seen using the show_generation_algorithm.

Unittests

Unittests have been added for algorithm.py in tests/algorithm_tests.py. To make testing of new algorithms easier, I have created a list of all maze generation algorithms in algorithm.py. In algorithm_tests.py, each test is run for all the algorithms in this list. This way, when a new maze generation algorithm is added, there is no need to write unittests for it separately.

The following tests have been added,

  1. test that the generation path is not an empty list
  2. test that entry and exit points have been added for the maze
  3. test that after generating maze, all cells have been marked as unvisited
  4. tests that all cells have been processed and no cell has walls on all four sides.
AshishS-1123 commented 3 years ago

@jostbr It's been a long time since I opened this PR. Yet you haven't responded. If this is a dead project, tell me right away so that I can stop wasting my time.

jostbr commented 3 years ago

@AshishS-1123 My apologies for being AWOL! Thank you for your contributions. I merged #35, this means #36 have conlfict in src/maze.py. Are you able to see what that is and then I can proceed to merge #36?

AshishS-1123 commented 3 years ago

@jostbr I have fixed the merge conflict. I modified the generate_maze function in src/maze.py to include the conditional statements that call the different generation algorithms. Branch can now be merged.