Difficulty: Beginner
Prerequisites
There are no prerequisites for this project.
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 – Comparison
The King of Programmia needs a new Court Wizard and has posted a public announcement saying so. After waiting several weeks, he has only received two applications: one from Wizard Ava and one from Wizard Ben. To see which is the better Wizard, the King has decided to build a giant maze. The one who gets to the end of maze first wins and gets the job.
Since wizards are magical, both Ava and Ben can use their spells to teleport instantly to any part of the maze that they have been to before, without taking up any time. However, they have to travel on foot through any part of the maze they haven’t explored yet. Ava and Ben travel on foot at the same rate. Given these constraints, Ava and Ben come up with separate strategies:
- Ava will use a Depth-First Search (DFS) strategy. When there is more than one path for her to take, she will choose a random one and run down it. If that one leads her to a dead end or circles back to somewhere she has already been, she will teleport back to the last path she didn’t take and try that one. She does this until she finds the path that leads to the exit.
- Ben will use a Breadth-First Search (BFS) strategy. When there is more than one path for him to take, he will go a step down the first choice, then teleport to the other path, take a step down that way, teleport back to the first choice, take a step, back to the second, take a step … This way, he takes every possible path choice at once! However, since he is splitting his steps between each path, he travels at a fraction of his normal speed.
You want to predict who is more likely to win – Ava with her Depth-First Search or Ben with his Breadth-First Search. You decide to experiment.
What to Do
- Download the interactive maze program here.
- Press the “Maze” button to create a random maze.
- First, select the option you want to test (DFS for Ava, BFS for Ben) and, to save time, shift the “Delay” slider to a low value.
- Click the “Animation” button and watch the algorithm play out.
- When the animation has finished, record how long it took Ava or Ben to complete the maze by writing down the number labeled “Nodes Expanded” at the bottom. Ignore the other numbers. Then, press “Clear” to clear the maze and try the other option (DFS or BFS) on the same maze.
- Now, change the size of the maze, keeping it square, by putting a new number in the “# of rows” and “# of columns” boxes and pressing “Maze”.
- Finally, graph Ava’s and Ben’s times for each of the sizes you tried, with maze size on the x-axis and the “Nodes Expanded” number on the y-axis.
Part 2 – Manipulation
When word of Ava’s and Ben’s intended strategies reached the King, at first he was impressed. Then, had a troubling thought – would people think that these wizards were smarter than him? To put his worries at ease, he has ordered you to create one maze for each wizard’s strategy (so one for Ava’s DFS and one for Ben’s BFS) that will make that wizard lose very badly. That way, no matter which wizard wins, the King can “prove” he is smarter than them by producing a maze in which they their strategy doesn’t work very well. You note that King is very insecure, but also that he commands an army and owns a prison, so you agree to take the job.
What to do
- If you haven’t already, read through Part 1 to see how to use the maze program.
- Run BFS and DFS on a few different auto-generated mazes to understand how they work.
- Next, make the size of the maze area very small (try 9×9) and press “New grid” to create a blank maze.
- Click on the square cells to create or remove walls and make your own maze, then record how well BFS and DFS do on it.
- Try to create a maze that BFS completes very quickly and DFS completes very slowly. In other words, create a maze where (BFS nodes expanded)/(DFS nodes expanded) as small as possible.
- Then, try to do the opposite, such that (DFS nodes expanded)/(BFS nodes expanded) is as small as possible.
