# Navigating Through a Maze

When you run it, the code in this quiz will produce an animation of a short story: first, a maze being constructed, and then a small, red "turtle" moving through the maze from the yellow dot to the green dot.

For now, you'll only need to tell the turtle navigating the maze what to do. You don't need to worry about drawing the maze just yet, although we did use Python to do that part too, and we'll show you how before the end of this course!

# Navigating Through a Maze

Instead of navigating the maze in real time, you'll need to enter the whole sequence of navigational commands as a single, long list.

You can instruct the turtle to move using three kinds of commands:

• advance() moves the turtle one step forward.
• turn_left() makes the turtle turn left on the spot (i. e. without moving).
• turn_right() works similarly

Hit "Run code", and look: the turtle is almost at its goal! Add the missing command(s). What do the instructions you're adding command the turtle to do?

from brilliant.turtle_maze import *
import random
random.seed(42)

### WAY-FINDING ###

# available commands:
### advance() # move one step forward
### turn_left() # turn left on the spot (without advancing)
### turn_right() # turn right on the spot

turn_left()
turn_right()
turn_left()

bye()

This is the part of the program that steers the turtle through the maze. This sequence of commands moves the turtle almost to its target.

Can you help it to the finish line? Put your own commands here.

Python 3
You need to be connected to run code

# Navigating Through a Maze

Run the code below to produce another maze, in which your task is to steer the turtle all the way from start to finish. If you navigate the turtle as efficiently as possible, how many times will the turtle need to advance()?

from brilliant.turtle_maze import *
import random
random.seed(32)

### WAY-FINDING ###

# available commands:
### advance() # move one step forward
### turn_left() # turn left on the spot (without advancing)
### turn_right() # turn right on the spot

bye()

Put the commands that steer the turtle here. All of the commands need to be listed before the "bye()" command which gets a line of its own at the very end.

Python 3
You need to be connected to run code

# Navigating Through a Maze

This program here is slightly different. First, run the code, then try to add directions to guide the turtle to its goal, but don't try too hard. What has changed compared to the previous programs?

from brilliant.turtle_maze import *
import random

### WAY-FINDING ###

# available commands:
### advance() # move one step forward
### turn_left() # turn left on the spot (without advancing)
### turn_right() # turn right on the spot

bye()

Add more steering commands here and observe the results.

Python 3
You need to be connected to run code

# Navigating Through a Maze

As opposed to the versions in previous questions, this last program generates a completely new maze each time it runs. So guiding the turtle step-by-step in the code does not work, since we cannot know in advance which maze it will find itself in!

What is needed here is a general maze-solving solution, one that is not comprised of a sequence of "hard-coded" commands. Instead, it should adapt the turtle's motion to the surrounding walls as it encounters them, following an algorithm. As an illustration, below is how the turtle might find the salad using the rule of "hugging the right wall" as it moves.

In future chapters, this course explores both randomness and algorithms that succeed in spite of unknowns and randomness. Both of these topics are powerful and necessary programming tools!

# Navigating Through a Maze

DON'T PANIC

So far, we've been hiding away most of the Python code for this program, but the entire program is visible below and it's more than 200 lines of code! This code is split up into sections that control different parts of the program's behavior:

• commanding the turtle to move,
• drawing the maze, and
• defining how the turtle should behave when it moves, hits walls, and reaches the salad.

And this brings us to the last and most important conclusion in this quiz: you don't need to understand the whole program in order to understand and fix a small piece of it. If you want to try to play with (and potentially break) other parts of the program, go for it! However, to complete this challenge, just run the code and find the single, small mistake that was made in one of the lines controlling the turtle's navigation. Then fix the mistake so that the turtle successfully navigates the maze!

When you saw the 200+ lines of code below, did you panic?

from turtle import *
import random, tkinter
random.seed(25)

### WAY-FINDING ###

def turtle_moves():
# available commands:
### advance() # move one step forward
### turn_left() # turn left on the spot (without advancing)
### turn_right() # turn right on the spot

turn_left()
turn_right()
turn_right()
turn_left()
turn_right()
turn_right()
turn_left()

# parameters
maze_width = 5
maze_height = 5
cell_size = 50
wall_width = 10
hideturtle()
speed(7)

### DRAWING COMMANDS ###

# position of cell on screen (for drawing)
def cell_pixel_coords(c):
x = (-maze_width/2 + c[0] + 0.5)*cell_size
y = (-maze_height/2 + c[1] + 0.5)*cell_size
return (x, y)

def draw_edge(c1, c2):
(x1, y1) = cell_pixel_coords(c1)
(x2, y2) = cell_pixel_coords(c2)
penup()
goto(x1, y1)
pendown()
goto(x2, y2)
penup()

def draw_graph(graph):
for (c1, c2) in graph:
draw_edge(c1, c2)

### MAZE LOGIC ###

# given a cell and a heading, which cell is directly in front?
(i, j) = cell
if i < maze_width-1 and heading % 360 == 0: # facing east
return (i+1,j)
elif j < maze_height-1 and heading % 360 == 90: # facing north
return (i,j+1)
elif i > 0 and heading % 360 == 180: # facing west
return (i-1,j)
elif j > 0 and heading % 360 == 270: # facing south
return (i,j-1)
else: # facing edge of maze
return None

def neighbors(cell): # inner cells have 4 neighbors, border cells 3 or 2
# cells at border can have 'None' entries, remove them
return [c for c in n if c != None]

### CREATE MAZE ###

## Method: grow a graph of connected cells

# start at a randomly chosen cell
c1 = (random.randint(0,maze_width-1), random.randint(0,maze_height-1))
visited_cells = [c1] # keep track of which parts have already been reached
maze_graph = [] # this will be filled with edges (pairs of cells)

# now successively add cells like branches on a tree
while len(visited_cells) < maze_width * maze_height:
# pick a visited cell at random
c1 = random.choice(visited_cells)
# which new cells can we reach from here?
unvisited_neighbors = [n for n in neighbors(c1) if n not in visited_cells]
# if none, pick a new cell to look there
if len(unvisited_neighbors) == 0:
continue
# if there are, pick one and incorporate it into the growing graph
else:
c2 = random.choice(unvisited_neighbors)
visited_cells.append(c2)
maze_graph.append((c1, c2))

def wall_between(c1, c2):
return ((c1,c2) not in maze_graph and (c2,c1) not in maze_graph)

def goto_cell(c):
goto(cell_pixel_coords(c))

### DRAW THE MAZE ###

tkinter.ROUND = 'projecting' # line cap style to fill the maze properly
color('burlywood')
width(cell_size + wall_width)
begin_fill()
draw_edge((0,0), (maze_width-1,0))
draw_edge((maze_width-1,0), (maze_width-1,maze_height-1))
draw_edge((maze_width-1,maze_height-1), (0,maze_height-1))
draw_edge((0,maze_height-1), (0,0))
end_fill()
penup()

width(cell_size - wall_width)
color('black')
draw_graph(maze_graph)

### SETTING UP THE START, TARGET AND TURTLE ###

width(1)
tkinter.ROUND = 'round'
goto_cell((0,0))
color('black')
dot() # hacky line to trigger the new cap style
color('yellow')
dot(0.4 * cell_size)

# place the target (a tasty salad) in the top right corner
target_pos = (maze_width-1, maze_height-1)
goto_cell(target_pos)
color('green')
dot(0.4 * cell_size)

# place the turtle in the bottom left corner
cur_pos = (0,0)
goto_cell(cur_pos)
showturtle()
speed(1)
color('red','red')
pendown()

### TURTLE STEERING ###

global cur_pos
# can we actually go there?
if not wall_between(cur_pos, next_pos):
forward(cell_size)
cur_pos = next_pos
if cur_pos == target_pos:
do_victory_dance()
# if not, bounce off the wall in front
else:
bounce_off_wall()

def turn_left():
left(90)

def turn_right():
right(90)

def bounce_off_wall():
penup()
forward(cell_size/2)
back(cell_size/2)
pendown()

def do_victory_dance():
penup()
back(13)
right(67.5)
for i in range(16):
forward(10)
left(45)
left(67.5)
forward(13)

# turtle tries to solve the maze
turtle_moves()

bye()
Python 3
You need to be connected to run code

×