Project: plan the route

Model the mat as a graph, find the shortest route with breadth-first search, and drive it.

A4.8Trees and graphsA level35 min

This project puts the whole module to work. BugBot is on a mat divided into a 4 by 4 grid of squares, and four of the squares are blocked. You will model the mat as a graph, choose how to store it, find the shortest route with breadth-first search, read the route out of the tree the search builds, and drive it.

The brief

The mat is a 4 by 4 grid of squares 25 cm across, lettered A to P in reading order from the far left corner. In GRID, a blocked square is # and a free square is .. The robot may move from a free square to a free square directly above, below, left or right of it: never diagonally, never onto a blocked square. Build the graph and print how many vertices and edges it has. Find the route from A to O with the fewest moves using breadth-first search, print it and its number of moves, then drive it.

The plan

Decide before coding, and write down why:

Step 1: from grid to graph

Here is the idea on a smaller mat, 3 squares wide and 2 deep, with E blocked:

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

GRID = ["...",
        ".#."]
NAMES = "ABCDEF"
ROWS = 2
COLS = 3

graph = {}
for r in range(ROWS):
    for c in range(COLS):
        if GRID[r][c] == ".":
            here = NAMES[r * COLS + c]
            graph[here] = []
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:        # above, below, left, right
                nr = r + dr
                nc = c + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] == ".":
                    graph[here].append(NAMES[nr * COLS + nc])
for square in graph:
    print(square, graph[square])

Run this in the simulator

Row 0 is the far end of the mat. A square's letter comes from its row and column, r * COLS + c, the same arithmetic that stores a two-dimensional array in one dimension. The bounds check 0 <= nr < ROWS stops a square on the edge looking off the mat.

How many edges? Each undirected edge is in two lists, so add up the lengths of all the lists and halve the total. Check it against the figure: A to B, B to C, A to D and C to F, 4 edges from 8 list entries.

Step 2: search, then read the route

Lesson A4.4's shortest_path already does this job: a breadth-first search that records every square's parent, then a walk back from the goal. On the project mat you can also stop the search as soon as O comes off the queue, because by then every square nearer than O has been dealt with.

Why not depth-first? A depth-first search from A that tries right before down runs along the top row to D, down through H and L to P, then left to O: a route of 7 moves. It finds a route, but not the shortest, and nothing in the search tells it so. On this mat the shortest route is 5 moves.

Step 3: drive it

The robot starts in the centre of A, facing up the mat. Each square is 25 cm across, so the centre of the square in row r, column c is 25 × c cm to the right of A and 25 × r cm back towards you, which in position() terms is (25 * c, -25 * r). Drive to each square on the route in turn. Aim for each centre from where position() says the robot is, rather than blindly driving 25 cm per move, so a small error on one move does not add up over the next.

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

def centre(r, c):
    return 25 * c, -25 * r

for r, c in [(0, 1), (0, 2)]:                     # squares B and C
    tx, ty = centre(r, c)
    x, y = position()
    right(60, distance=tx - x)
    print("now at", position(), "aiming for", (tx, ty))

Run this in the simulator

Testing

• Count by hand first. Count the free squares and the pairs of free squares side by side in the figure, before trusting the program's vertices: and edges: lines.
• Print before you drive. Print the route and check every step is a legal move before the robot moves at all.
• Try other goals. L is 5 moves along the top; D is 3. A search that gets those right is probably right for O.
• Change the grid. Block N and P as well. O can no longer be reached, and your program should say so rather than crash.

Task: plan the route

GRID is the mat from the brief, with row 0 at the far end of the mat and column 0 on the left, and NAMES gives the letters in reading order. The robot starts in the centre of square A facing up the mat, and square centres are 25 cm apart. Build an adjacency list for the free squares. Print vertices: and the number of free squares, then edges: and the number of edges. Find the route from A to O with the fewest moves, using a breadth-first search that takes squares from the front of a queue with popleft() or pop(0). Print route: followed by the letters of the squares from A to O separated by single spaces, and then moves: followed by the number of moves. Finally drive the route square by square, without touching a blocked square, finishing in O.

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

from collections import deque

GRID = ["....",
        ".##.",
        "..#.",
        "#..."]
NAMES = "ABCDEFGHIJKLMNOP"

graph = {}

Challenges

1. Make the program print no route instead of crashing when the goal cannot be reached. Test it by blocking N and P.
2. Suppose a sideways move takes the robot twice as long as a forward or backward move. What does "shortest" mean now, and why can breadth-first search no longer find it?
3. Replace the breadth-first search with a depth-first one and print the route it finds. How many moves does it take, and does that depend on the order you try the neighbours in?