Maze Generation (Advanced)

Difficulty: Advanced

Prerequisites

• This project requires knowledge of how to code in Python.
• This project requires the following Python modules to be installed on your computer:
  matplotlib numpy

Need help with Python?

Background

Solving mazes can be done just for fun, but it can also help introduce some important concepts in computer science and programming. A simple maze can be made from an arrangement of open rectangular cells (paths) with filled cells (walls) between them.

Part 1 – Implementing an Algorithm

The King of Programmia has hired you to inspect one of the many giant mazes he has built. Halfway through your inspection, your phone battery dies, leaving you trapped on the far side of the maze. What’s more, your map of the maze was on your phone! You need to find your way back through the maze to get home.
Thinking hard, you remember that, as long as the entrance and exit of a maze are both on the maze’s edge (so neither is in the center of the maze), you can always get from the entrance to the exit by always following the wall on your right – that is, taking right turns at every intersection, and turning around at every dead end. As you are navigating the maze this way, you realize that you could implement this as a Python program.

What to Do

1. Download maze_util.py and solve_maze.py. Make sure to put them in the same folder.
2. What are these files? maze_util.py is already completely written for you; you don’t need to worry about how it works (though you can look if you want). You just need to have it in the same folder as the file you will be working with, solve_maze.py.
3. Run solve_maze.py. The result should look something like this:



4. This shows a random maze, but you will notice that, though the file is named solve_maze.py, there is no solution visible. This is because you have not provided one yet!
5. Open solve_maze.py and read through the comments. When you are ready, write some python code to walk through the maze fill in the solution list with all the points along the way as you continuously follow the wall on your right from the start of the maze to the end.
6. Hint: create one variable to keep track of your current position, and one to keep track of what direction you are facing. “Walk” through the maze by updating these based on if there are to your front, left, right, and back. Add each new position you reach to solution. Do this until you reach the end of the maze.
7. Don’t worry if your code doesn’t work the first time, or even the tenth time. Test your code often to make sure it works how you think it does. Don’t be afraid to ask a teacher or other mentor for help if you get stuck!