Robot in a Maze

In this project, you will create algorithms to escape from a maze.

Imagine you're a robot trapped in a maze. You don't have a bird's-eye view so you can see all the possibilities (shown below left). Instead, you're inside it, and the walls are taller than you are (shown below right).

Images by Scratch user Legolover8888 and Wikimedia user Oxyman
drawing of maze seen from above photograph of maze of hedges with tall walls seen from the inside

  1. Talk with Another PairCome up with an algorithm to escape from any maze. Write it down on paper.
    2. AAP-2.A, AAP-2.G, AAP-2.J
  2. Looking at your algorithm, find examples of:
    • sequence (several steps done one after another)
    • selection (a place where the algorithm does one of two things depending on some condition)
    • repetition (the algorithm does the same thing over and over)
  3. Without using Snap!, consider: Does your algorithm work on the maze in the first picture on this page? Start at the orange circle, facing north (in the direction of the arrow). Your goal is to reach the red X.
  4. If your algorithm didn't work, debug it.
AAP-2.M.2 bullet 4

One well-known maze algorithm is called "Follow the left wall." The idea is to keep your left hand touching a wall. If suddenly your left hand isn't touching a wall, there's a corridor to the left, and in order to keep your hand on the left wall, you turn left and go down the corridor. If instead you bump into a wall in front of you, then in order to keep your hand on the left wall you'll have to turn right. (Draw a sketch if that doesn't make sense to you.) For many mazes, this simple algorithm will eventually get you to the exit.

  1. Does the left wall algorithm work for the maze in the first picture? If not, can you debug it?

There are problems about a robot in a grid with special procedures that don't exist in Snap!:

You can read more about these AP language procedures on the Snap! Cheat Sheet in the Robot section at the bottom.

  1. Imagine a robot (the sprite) is sitting in the middle of a 5×5 grid facing upwards. On a paper copy of this grid, shade all the squares that the robot can't possibly get to, when the given code is executed.
    set (turns) to (pick random (2) to (3)) repeat (turns) { rotate right } set (steps) to (pick random (1) to (2)) repeat (steps) { move forward } 5×5 grid of squares with an upward-facing sprite in the center square
  1. See if you can invent a maze for which the left wall algorithm doesn't work.