Page 1: Robot in a Maze
Unit 3, Lab 1, Page 1
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
- Come up with an algorithm to escape from any maze. Write it down on paper.
-
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)
- 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.
- If your algorithm didn’t work, debug it.
AAP-2.A, AAP-2.G, AAP-2.J
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.
- 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!:
-
The
MOVE_FORWARD ()
moves the sprite forward one grid square. (You need to call it repeatedly to move more than one grid square.)
-
The
ROTATE_LEFT ()
or
ROTATE_RIGHT ()
blocks always turn exactly 90 degrees. (They are used only to move a robot in a grid.)
-
The
CAN_MOVE (direction)
block returns true or false depending on whether or not the robot can move in the input direction without running into a wall or walking off of the maze.
You can read more about these AP language procedures on the Snap! Cheat Sheet in the Robot section at the bottom.
-
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.
- See if you can invent a maze for which the left wall algorithm doesn’t work.