A grid is a graph

Cells are nodes, neighbours are edges, and breadth first search is the shortest path when every step costs the same.

U9.2PlanningUniversity35 min

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Maze solving robots explained

Once the robot is a point, chop the mat into cells and the planning problem becomes a graph problem, which is a problem computer science solved a long time ago.

• Node: one cell.
• Edge: a cell and its neighbour, if both are free.
• Path: a sequence of edges from the start cell to the goal cell.

That is the whole translation. Every algorithm in this module runs on that graph.

The grid used from here on

The same map appears in this lesson, the next two and the project, so fix the convention now.

The two walls overlap in y, so there is no straight way across. The route has to pass above the first wall and then below the second, which is exactly the sort of map where a planner earns its keep and a reactive rule does not.

Choosing the cell size

A real decision, with a real trade.

• Too large and the passage between the walls disappears, because no cell centre lands in it. The planner reports no route and is not wrong, given the map it was handed.
• Too small and the number of cells grows as the square of the resolution, and so does the time. Halving the cell size on this mat takes 1,600 cells to 6,400.

Five centimetres on a 200 cm mat is a reasonable compromise, but be careful which gap you measure. The bare floor between the two walls is 47 cm across. Growing each wall by the 8 cm margin takes 8 cm off either side, so the narrowest corridor the planner searches is 31 cm, and six columns of cell centres land in it. The 47 cm is what a tape measure on the mat says, the 31 cm is what the search has to fit through, and it is the 31 cm that decides whether a cell size works.

Breadth first search

Take the start cell. Look at its neighbours, then their neighbours, and so on outwards, never visiting a cell twice.

came = {start: None}
queue = [start]
while queue:
    cur = queue.pop(0)
    if cur == goal:
        break
    for nxt in free_neighbours(cur):
        if nxt not in came:
            came[nxt] = cur
            queue.append(nxt)

came does two jobs at once: it is the visited set, and it is the record of which cell each one was reached from, so the path is recovered by walking backwards from the goal.

Breadth first is complete: if a route exists it finds one, and if none exists it terminates having looked at everything reachable. It is also optimal, but only in a narrow sense: it finds a path with the fewest edges. When every edge costs the same, fewest edges is shortest. When they do not, it is not, which is the whole of the next lesson.

Complexity is O(V + E): every cell is dequeued once and every edge is looked at once. On a 40 by 40 four-connected grid that is 1,600 nodes and 3,120 edges, each looked at once from either end, about 6,000 checks in all, which is nothing.

Four neighbours or eight

With four neighbours, every step costs one cell and the geometry is honest. The path is then made of horizontal and vertical runs only, so its true length is the Manhattan distance, which on a diagonal route is about 41 percent longer than a straight line.

With eight neighbours, the diagonals are available, but a diagonal step is sqrt(2) cells long and breadth first has no way to say so. Run breadth first on an eight-connected grid and it will count a diagonal as one step, the same as a straight one, and confidently return a path that is not the shortest. Breadth first belongs on a four-connected grid, or on any graph where all the edges genuinely cost the same. If you want diagonals, you want Dijkstra.

from bugbot import *
connect()

CELL, N, INFLATE = 5.0, 40, 8.0
WALLS = [(70.0, 0.0, 8.0, 115.0), (125.0, 85.0, 8.0, 115.0)]

def blocked(i, j):
    x, y = i * CELL + 2.5, j * CELL + 2.5
    if x < INFLATE or y < INFLATE or x > 200 - INFLATE or y > 200 - INFLATE:
        return True
    return any(ox - INFLATE <= x <= ox + ow + INFLATE and oy - INFLATE <= y <= oy + oh + INFLATE
               for ox, oy, ow, oh in WALLS)

grid = [[blocked(i, j) for j in range(N)] for i in range(N)]
print("free cells:", sum(1 for i in range(N) for j in range(N) if not grid[i][j]), "of", N * N)

for j in range(N - 1, -1, -2):
    print("".join("#" if grid[i][j] else "." for i in range(N)))

Run this in the simulator

The printed map is the thing to look at. Two thick bars, and one winding corridor between them.

Task: breadth first across the mat

Build the grid, run breadth first from cell (6, 6) to cell (34, 34) with four neighbours, and print steps:, how many moves long the path is, and expanded:, how many cells came off the front of the queue before the goal did.

from bugbot import *
connect()

CELL = 5.0
N = 40
INFLATE = 8.0
WALLS = [(70.0, 0.0, 8.0, 115.0), (125.0, 85.0, 8.0, 115.0)]

Challenges

1. Count how many cells breadth first expanded and compare it with the number of free cells. What does the ratio tell you about how much of the mat it searched for nothing?
2. Run it with the goal set to a cell inside a wall. What happens, and how long does it take to happen?
3. Run it with eight neighbours and measure the true length of the path in centimetres. Is it shorter or longer than the four-connected one?