Escape the Maze

In this lab we begin our exploration of algorithms, the conceptual heart of computer science. You’ll develop a simple algorithm to escape a maze and implement it in Java.

1. Algorithm Design and Implementation (50 Minutes)

Let’s learn more about algorithms—systematic ways that we and computers use to solve problems.

1.1. Escape Plans

Open and make a copy of this maze spreadsheet. Click "Add Ons → Maze Creator → Redraw Maze” to generate a random maze. Note that you may have to wait a minute for the "Maze Creator" menu to appear. Click through any scary warnings and the script should run. Feel free to change the number of rows and columns to create a larger or smaller example.

Working with a partner, develop an algorithm to escape from mazes like the ones drawn on the spreadsheet above. You should limit yourself to the following actions:

  • canMove(): returns true if you can move forward, false otherwise (if you are blocked by a wall)

  • move(): moves one square forward if possible; otherwise does nothing

  • turnRight(): turns right, does not change your position

  • turnLeft(): turns left, does not change your position

  • isFinished(): returns true when you have reached the end position

1.2. Evaluating Algorithms

As you begin implementing your maze escape algorithm, think about the different ways that computer scientists evaluate algorithms. Here are some of the components of a good algorithm:

  1. It works. It should definitely solve the problem you are trying to solve, or at least have a good probability of solving it in most cases.

  2. It should perform well. It should not require a huge amount of resources to solve the problem—whether those resources are time, computational horsepower, computer memory, or disk space.

  3. It should be understandable. Good algorithms are easy to understand and reason about. The best ones are simple, and sometimes we even call them elegant. Complex algorithms are hard to understand, making it difficult to think about what they will do in certain cases.

  4. The implementation should be clear and understandable. Many times we encounter algorithms while reading computer code. So just as the algorithm must be clear, the implementation in computer code must also be clear. We will have a lot more to say about code quality throughout the semester—particularly on the MPs.

These are not non-contradictory goals. Frequently the desire for simplicity clashes with attempts to improve performance, or handle all inputs correctly. But particularly when you are starting off as a computer science, err on the side of simplicity. Remember: computation is (increasingly) cheap, humans are expensive. If it takes me 10 times longer to understand or modify your algorithm, it is not worth a only minor improvement in performance. Let your algorithms waste a bit of computer time, but never human time.

1.3. Analyzing Your Algorithm

Once you have developed your algorithm, consider the following questions before proceeding:

  1. What are the limitations of your algorithm? Will it always find its way out of any maze, or just mazes with certain properties?

  2. How could you improve your algorithm? Would it help to keep track of other state, or have other operations (like moveRight()) available to you?

1.4. Implementing Your Algorithm

Now let’s implement the maze solving algorithm that you designed in the first half in Java.

Move over to the lab homework problem at this point. Today’s homework uses the CS 125 mazemaker Java library, which uses a well-known algorithm to automatically generate mazes. You can find the mazemaker source code and documentation on GitHub 1 Note that the version used on the homework problem is bit different than what is posted online, but largely the same.

1.4.1. Your algorithm’s performance

Once you have a working algorithm, spend some time understanding its performance. Answer the following questions 2:

  1. How many steps—each consisting of moving one square—does it take to finish the maze? Because the maze generation is random, you might want to run multiple trials and average the results.

  2. For a maze with dimensions N by M, what is the minimum number of steps required to complete the maze, assuming you start at the bottom left and exit at the top right?

  3. How much worse does your algorithm do? Why?

  4. Can you come up with ways to improve your algorithm?

1.4.2. Your algorithm’s limitations

Now spend some time thinking about the limitations of your algorithm. In particular, the mazes that are generated by our maze creator all have something in common: They have no loops! This is due to the operation of the maze generation algorithm, which uses a simple depth-first search over the two-dimensional space. To make things more interesting, we could have inserted some holes at the end—but we didn’t.

But suppose you ran your algorithm on a maze with loops. Think up one way it could get stuck. So it’s possible that your algorithm may not work! But, assuming that the start and end point are always on the exterior wall of the maze, try to convince your partner that your algorithm will still work.

1.5. A Randomized Algorithm

The maze-solving algorithm you implemented above is deterministic. Provided the same maze, it will always navigate through it in the same way. You may want to rerun your algorithm on the same maze a few times to convince yourself of this.

Deterministic algorithms are great—easy to understand and reason about. But there is a different class of algorithms called randomized algorithms. As their name implies, these algorithms use randomness as part of their logic. In some cases, this allows them to dramatically outperform the best known deterministic algorithm.

IRobot Roomba 780

One randomized algorithm that you may have seen in action is a space-filling algorithm called a random walk. If you’ve ever watched a Roomba 3, you’ve seen a random walk in action. It turns out that mapping is a hard problem for robots to solve. So, rather than trying to map an area, early robotic vacuums 4 just implemented a random walk:

  1. Go straight until you hit something

  2. Turn a random amount but sufficient to not continue into the obstacle

  3. Repeat

To a human observer this looks crazy—how is it ever going to get every spot? But it turns out that there is some fairly sophisticated mathematics that shows that, given a certain number of passes, your random robot maid will get every spot with very high probability. Or at least chase a duck:

1.5.1. Implement a random walk

Inspired by your vacuum, try re-implementing your maze-solving algorithm using a random walk. More or less, here’s how that works:

  1. Go forward until you are facing a wall

  2. Randomly turn right or left

  3. Repeat

Once you are done, compare the running time of your randomized algorithm with the deterministic algorithm you implemented above. Are you surprised? With your partner, try to develop an explanation for the difference in performance.

2. Before You Leave

Don’t leave lab until:

  1. You’ve escape the maze!

  2. And so has everyone else in your lab!

If you need more help completing the tasks above please come to office hours or post on the {forum}.

CS 125 is now CS 124

This site is no longer maintained, may contain incorrect information, and may not function properly.

Created 10/24/2021
Updated 10/24/2021
Commit a44ff35 // History // View
Built 10/24/2021 @ 21:29 EDT