Project: out of the dead end

Model a maze, solve it by recursive backtracking, and drive the robot out along the route.

A2.10Recursion and computational thinkingA level30 min

The robot is in the bottom left corner of a small maze, and the charger is in the top right. The obvious way up the left side is a dead end. This project pulls the module together: an abstract model of the maze, a recursive backtracking search that finds the way out, a solution decomposed into subroutines and composed back into one program, and the robot automating the model by driving it.

The model

The maze is built from 20 cm square blocks on the 100 cm mat. The model keeps only what matters for finding a route: which cells are open. Each row is a string, row 0 at the top:

...#G
.###.
.#...
.#.#.
S....

S is the start, in row 4, column 0, and G is the goal, in row 0, column 4. A cell (row, col) is open if its character is not #. Moving up the mat is row − 1, right is col + 1, down is row + 1 and left is col − 1. That is the whole abstraction: no walls with thickness, no robot size, no drift. Those are left to the driving code, which checks the real position as it goes.

Plan before code

Decompose the problem:

get the robot to the charger
├── solve the model: find a path of cells from S to G
│   ├── is a cell usable? (on the grid, not a block, not already visited)
│   └── try each direction from a cell, recursively
└── drive the path
    ├── turn a cell into a point in cm
    └── drive from the current position to that point

Think ahead: the input is the maze and the start cell; the output is a list of cells, and the robot arriving at G. A precondition is that the start cell is open. The visited set is a kind of cache: it records cells already explored, so the search never goes round in circles.

Think logically about the decisions in solve(row, col):

1. Off the grid, a block, or visited already? Return False straight away.
2. Otherwise mark the cell visited and add it to the path.
3. Is it the goal? Return True: the path is complete.
4. Try up, right, down and left, in that order, calling solve on each neighbour. As soon as one returns True, return True.
5. If all four fail, this cell is a dead end: take it back off the path, report it, and return False. That return is the backtrack.

How the search runs

Following those rules from S, the search goes up first. It climbs the left column to row 0, turns right along the top, and at row 0, column 2 finds a block to the right and a block below. Dead end. It backs out of that cell, then out of each cell before it that has nothing else to try, all the way down to S, and only then tries right along the bottom row, which leads up the middle and across to G.

The call stack is doing the remembering. At the dead end, the stack holds a frame for every cell from S up the left column and along the top row to row 0, column 2, each one partway through its list of four directions. Each return False pops a frame and hands control back to the cell before, which carries on with its next direction. That is exactly the backtracking from lesson A2.9, with the stack from lesson A2.1 holding the choices.

The path is a list used as a stack too: append when a cell is entered, pop when it proves to be a dead end. When G is found, what is left on it is the route.

Task: solve the maze model

Write a recursive function solve(row, col) for the maze above, following the five rules, with MAZE as the list of five strings, a set visited and a list path.

• row and col are whole numbers; the grid runs from 0 to 4 in each.
• solve returns True if the goal can be reached from (row, col) without revisiting a cell, and False otherwise.
• A cell that is off the grid, a block or already visited returns False without printing anything.
• An open cell that fails in all four directions prints back from (<row>, <col>), for example back from (0, 2), after taking itself off path.
• Try the directions in the order up, right, down, left.

Call solve(4, 0), then print path: followed by every cell on path, each written (row, col) and separated by single spaces, starting path: (4, 0) (4, 1).

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

MAZE = ["...#G",
        ".###.",
        ".#...",
        ".#.#.",
        "S...."]
visited = set()
path = []

def solve(row, col):
    return False

solve(4, 0)

Task: out of the dead end

Now drive it. Add to your solution from the last task:

• cell_to_cm(row, col), which returns the point (x, y) in cm, measured from where the robot starts, of the centre of that cell. S at row 4, column 0 is (0, 0); each column to the right adds 20 to x, and each row nearer the top adds 20 to y.
• a way to drive from the robot's current position to a point, sliding across and then driving up or down, using position() so small errors do not build up.

Solve the model first and print the path: line as before. Then drive from cell to cell along the path, without touching a block, and finish in the goal cell.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

MAZE = ["...#G",
        ".###.",
        ".#...",
        ".#.#.",
        "S...."]
visited = set()
path = []

def solve(row, col):
    return False

def cell_to_cm(row, col):
    return 0, 0

Challenges

1. Change the direction order to right, up, down, left. Which cells are reported as dead ends now, and is the path different?
2. The path found is not always the shortest. Design a maze where backtracking finds a longer route than necessary, and say which search from module A4 would find the shortest.
3. Draw the call stack at the moment back from (0, 2) is printed. How many frames are on it, counting the main program?
4. Make the robot drive the search as it happens: drive into each cell as solve enters it, and drive back out as it backtracks. What does it cost compared with solving the model first?