Maze Generation (Intermediate)

Difficulty: Intermediate

Prerequisites

• This project requires knowledge of 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 – Coding

The King of Programmia loves building giant mazes.

In fact, he likes mazes so much that he told the Royal Maze Designer to write a Python script to design mazes for him. The Royal Maze Designer is just okay at programming, so all of the mazes his script produced had small areas that were cut off from the rest of the maze:

When he presented these designs to the King, the King became furious that the Royal Maze Designer would waste bricks building walls around nothing, so he threw the Royal Maze Designer in the dungeons. The King has made YOU the new Royal Maze Designer. Can you fix the broken script and make all points in the maze reachable, or will you join your predecessor below the castle?

What to Do

1. Download the broken maze generator script here.
2. Run the script once to make sure that it works on your computer. If not, make sure you have the right Python modules installed (see “Prerequisites”).
3. Open the script in an editor, walk through the code, read the comments, and try to understand how the code works.
4. Once you understand generally how the code works, try to figure out how to prevent it from building walls around closed-off spaces.
5. Finally, run the code and make sure your new maze generator works!

Part 2 – Experiment

The King accepts your improved maze generator.

Your job is not done yet. The King wants to make sure his maze will be hard to solve, and needs to know how big he needs to build it. He has commanded you to figure out the relationship between maze dimensions and difficulty.

What to Do

1. Generate and print out several copies each of at least five square mazes of different sizes (mazes can be saved as image files using the “save” icon on the display, then printed using most image-viewing programs).
2. Enlist a few volunteers and time how long it takes them to solve each of the mazes.
3. Record the data points of maze dimensions versus solving time in a table and graph them (We recommend Google Sheets, Microsoft Excel, or another similar program). Put dimensions on the x-axis and solving time on the y-axis.

Looking Back

Consider the following questions:

• Describe the shape of the graph. Is it flat? Does it follow a line? Does it taper off or start rising faster as dimensions increase?
• How close or spread-out are the points vertically?
• Why do you think the graph looks like it does?
• Can you use the graph to predict how long it would take to solve a maze size you haven’t tried yet?