Teaching Kids Programming – How to Design a Random Maze? Random Maze Generation Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Maze, we can use Breadth First Search, Depth First Search, or Iterate Deepening Search Algorithm to Find an Nearest Exit (if there is any) to an entry. We have talked about these three algorithms:

• Teaching Kids Programming – Nearest Exit from Entrance in Maze via Iterative Deepening Search Algorithm (IDS)
• Teaching Kids Programming – Nearest Exit from Entrance in Maze via Depth First Search Algorithm (DFS)
• Teaching Kids Programming – Nearest Exit from Entrance in Maze via Breadth First Search Algorithm (BFS)

Maze Design Algorithm – How to Generate a Random Maze?

So, we need to ask questions to clarify the requirement:

• Does the Maze need to have at least a valid path?
• How Large/Big is the Maze?

Also, we need to make sure the generated maze looks a bit interesting by adding a few other routes with dead-ends.

The straightforward solution would be:

1. Generate a Random Matrix with 0 empty cells and 1 meaning walls/obstacles
2. Check If this is not a maze – with at least a path from entry to exit. The entry and exit need to be on the border cell
3. Go back to step one if it is not maze. Alternatively, remove random walls and go back to step 2

Thus, this could be translated to the following Python code:

1
2
3
4
5

def maze(width, height):
    m = None
    while not check(m):
        m = generate_random_matrix(width, height)
    return m

def maze(width, height):
    m = None
    while not check(m):
        m = generate_random_matrix(width, height)
    return m

Or this (by removing random walls) – after a few steps, we can always get a valid maze, however, the maze might be sparse which doesn’t look that real and interesting.

1
2
3
4
5

def maze(width, height):
    m = generate_random_matrix(width, height)
    while not check(m):
       m = remove_a_random_wall(m)
    return m

def maze(width, height):
    m = generate_random_matrix(width, height)
    while not check(m):
       m = remove_a_random_wall(m)
    return m

Both are not very efficient considering the fact that the maze could be very large, and it might take long time for a valid maze to appear.

We could think the opposite, by generate a valid path first, and then fill the rest. We can use the following algorithms to generate a random maze:

1. Generate a random valid path.
2. Generate a few other random blocked paths.
3. Fill the remaining with walls/obstacles

To generate a random valid path, we can assume the entry is on the top boundary (without the loss of generality, we can transform, rotate, and mirror to make the entry on other borders). Then we can let it walk down, left or right until it hits a boundary. We can use a hash set to remember the pixels so that we don’t walk back the same places. We can ask it to walk down at its first step so that the exit doesn’t end on the top border.

For other blocked paths, we can generate the valid paths first, and randomly choose a position which is not the crossed point with other routes and block it. To avoid a crossed point, so that it doesn’t also block the only valid path.

Finally, fill the remaining pixels with walls, and we are done. Of course, we can tune the parameters to make the maze a bit interesting, and also, think about how to make entry and exit both on the same border?

Here, the ChatGPT/OpenAI AI gives the following similar solution:

1. Choose a starting point and an ending point for the maze.
2. Draw a path between the starting and ending points.
3. Create a grid of squares to represent the maze.
4. Randomly select squares to create walls and pathways.
5. Make sure there is a path between the starting and ending points.
6. Add dead ends and other features to make the maze more interesting.
7. Test the maze to make sure it is solvable.
8. Make any necessary adjustments to the maze.
9. Repeat steps 4-8 until the maze is complete.

Random Maze Generate Algorithm

–EOF (The Ultimate Computing & Technology Blog) —