Maze solving robots explained
How a maze solving robot finds the way out: the left hand rule, why it fails on some mazes, flood fill as used in micromouse, and planning the shortest route. Watch each one drive a maze on a live robot, in Python you can change.
A maze solving robot has to find its way from a start to a goal through corridors it may never have seen. There are three main ways to do it. It can keep one hand on a wall and follow it, which needs no memory at all. It can mark where it has been, so it never wastes time in the same place twice. Or it can keep a map, and work out from the map which way is shortest, which is what micromouse robots do with flood fill. On this page a small robot solves two mazes on a 1 metre mat, and each demo below is a real program you can change and run.
In the overhead view of each demo, the blue line is where the robot has been. In the flood fill demos, the shaded squares are the numbers the robot has worked out for each cell: pale near the goal, darker further away. The dark grey squares are blocks the robot has found, and the red line is the route it plans to take from where it is now. The chart shows how far the robot is from the goal: in a straight line for wall following, and in steps for flood fill.
The first maze
The mat is cut into five rows of five cells, each 20 cm square. Seven of the cells are 20 cm blocks. The robot starts in the bottom left cell, S, and the goal is the top right cell, G:
. . . # G
. # # # .
. # . . .
. # . # .
S . . . .
It is small, but it has the two things that make mazes hard. At the top left there is a dead end: a corridor that goes nowhere. And the block second from the right in the fourth row stands on its own, with open cells all round it. Blocks like that are called an island, and the corridor round it is a loop: you can go round and come back to where you started. There are two shortest routes from S to G, one each side of the island, and both are 8 cells long.
The robot has one distance sensor, on its front. From the middle of a cell it reads about 10 cm if the next cell is a block or the edge of the mat, and 30 cm or more if the next cell is open. To look in a direction, it turns to face it.
Wall following: the hand rule
Put your left hand on the wall at the entrance and walk, never letting go. You will turn into every opening on your left, go to the end of every dead end and come back out, and in the end you will walk out of the exit. This is the left hand rule, or wall following. The right hand rule is the same with the other hand.
It works because of how the walls fit together. In a maze where every wall is joined to the outside wall, all the walls together are one long wall, bent round into corridors. Walking with your hand on it takes you along the whole of that wall, and the exit is somewhere on it.
For a robot, one step of the rule is:
each cell:
turn to the left
while there is a wall ahead: turn right
move forward one cell
That tries left first, then straight on, then right, then back the way it came. With one sensor on the front, turning to look is how the robot finds out which ways are open. The program does not know where the blocks are. It counts cells as it moves so that it knows when it has reached the goal.
The program
from bugbot import *
import math
connect()
# change HAND and press Run
HAND = "left" # "left" or "right"
START = (10, 10) # the robot, in cm on the mat
GOAL = (90, 90) # the middle of the goal cell
CELL = 20 # each cell is 20 cm
def face(h):
# turn on the spot to face h degrees
# (0 is up the mat, 90 is to the right)
turn = (h - heading() + 180) % 360 - 180
if abs(turn) > 1:
turn_right(100, angle=turn)
def step(x, y):
# drive to the middle of the cell at (x, y),
# correcting any drift to the side first
px, py = position()
dx = x - START[0] - px
dy = y - START[1] - py
h = math.radians(heading())
ahead = dx * math.sin(h) + dy * math.cos(h)
side = dx * math.cos(h) - dy * math.sin(h)
if side > 1:
right(60, distance=side)
elif side < -1:
left(60, distance=-side)
forward(100, distance=ahead)
if HAND == "left":
first = -90 # try a quarter turn left first
else:
first = 90 # try a quarter turn right first
x, y = START
facing = 0
trail = [START]
while (x, y) != GOAL:
# the hand rule: turn to the hand side, then
# turn back the other way until it is open
facing = (facing + first) % 360
face(facing)
while distance() < 15:
facing = (facing - first) % 360
face(facing)
x += round(CELL * math.sin(math.radians(facing)))
y += round(CELL * math.cos(math.radians(facing)))
step(x, y)
trail.append((x, y))
draw("robot", trail, "blue", "line", 2)
plot("cm to the goal", math.dist((x, y), GOAL))
print("cells moved:", len(trail) - 1)
print("time:", round(clock()), "s")
The left hand keeps the robot against the left edge of the mat all the way up, so it goes into the dead end at the top left. The chart falls to 40 cm as it goes along the top, rises to 113 cm as it comes back down to the start, then falls to 0 on the way to the goal. It gets there, but it moves 20 cells when 8 would do.
Change HAND to "right" and the robot keeps the bottom edge on its right, goes along the bottom and up the right side, and reaches the goal in 8 cells and 43 s. Neither hand is better in general. Which one is quicker depends on where the dead ends happen to be, and the robot cannot know that in advance. Wall following finds a route, not the shortest one.
When wall following fails
The argument above needs every wall to be joined to the outside wall. A block or group of blocks that is not joined to it is an island, and if the goal is on an island, a robot with its hand on the outside wall never reaches it. It walks round the edge of the maze, comes back to where it started, and then does exactly the same again, for ever.
This second maze is on the same 1 metre mat. The goal is in the middle cell, inside a ring of seven blocks, and the only way in is a gap at the top of the ring:
. . . . .
. # . # .
. # G # .
. # # # .
S . . . .
The ring does not touch the edge of the mat, so it is an island. The robot starts in the corner with the edge of the mat on its left. The program stops it when it is in the same cell, facing the same way, for a second time.
The program
from bugbot import *
import math
connect()
# change HAND and press Run
HAND = "left" # "left" or "right"
START = (10, 10) # the robot, in cm on the mat
GOAL = (50, 50) # the goal: the middle cell
CELL = 20 # each cell is 20 cm
def face(h):
# turn on the spot to face h degrees
# (0 is up the mat, 90 is to the right)
turn = (h - heading() + 180) % 360 - 180
if abs(turn) > 1:
turn_right(100, angle=turn)
def step(x, y):
# drive to the middle of the cell at (x, y),
# correcting any drift to the side first
px, py = position()
dx = x - START[0] - px
dy = y - START[1] - py
h = math.radians(heading())
ahead = dx * math.sin(h) + dy * math.cos(h)
side = dx * math.cos(h) - dy * math.sin(h)
if side > 1:
right(60, distance=side)
elif side < -1:
left(60, distance=-side)
forward(100, distance=ahead)
if HAND == "left":
first = -90 # try a quarter turn left first
else:
first = 90 # try a quarter turn right first
x, y = START
facing = 0
trail = [START]
seen = {} # when it was at each cell, facing each way
while (x, y) != GOAL:
state = (x, y, facing)
if state in seen:
print("back at", (x, y), "facing", facing,
"after a lap of", len(trail) - seen[state], "cells")
break
seen[state] = len(trail)
facing = (facing + first) % 360
face(facing)
while distance() < 15:
facing = (facing - first) % 360
face(facing)
x += round(CELL * math.sin(math.radians(facing)))
y += round(CELL * math.cos(math.radians(facing)))
step(x, y)
trail.append((x, y))
draw("robot", trail, "blue", "line", 2)
plot("cm to the goal", math.dist((x, y), GOAL))
print("closest to the goal:",
round(min(math.dist(c, GOAL) for c in trail)), "cm")
print("time:", round(clock()), "s")
The robot goes up the left side, along the top, down the right side and back along the bottom, with its left hand on the edge of the mat the whole way. The chart goes 44.7, 40, 44.7, 56.6 cm and round again, once for each side. At the top it passes the cell right above the way in, 40 cm from the goal, and goes straight on, because the opening is on its right and the left hand rule only turns right when it has to. It is back in the first cell it moved to, facing up again, after a lap of 16 cells and about 94 s. Change HAND to "right" and it goes round the other way, 16 cells a lap: the right hand is on the edge of the mat too, and the way in is always on its left.
The stopping test is worth copying. A wall follower decides what to do from its cell and the way it is facing and nothing else. So if it is ever in the same cell facing the same way twice, everything after that will repeat, and it is going round a loop.
This is why wall following is no use in micromouse, the contest where small robots race to the middle of a maze. The goal is the middle of the maze, and the mazes are built so that the walls round it are not joined to the outside wall. A mouse that follows a wall from the start goes round and round, like the robot above. A robot that starts with its hand on an island has the same problem the other way round: it circles the island and never finds the exit on the outside wall.
Marking the way: Trémaux's method
A method that works in any maze, loops and islands included, is to leave marks. It is named after Charles Pierre Trémaux, a French engineer of the 1800s. Mark each corridor every time you go along it. At a junction you have not been to before, take any corridor with no marks. If you come to a junction you have already been to, by a corridor you had not used before, turn round and go back, because you have found a loop. Otherwise take the corridor with the fewest marks, and never go along one that already has two. Every corridor is walked at most twice, once in each direction, so you must find the goal. When you do, the corridors marked once make a route back to the start.
This is depth-first search done from inside the maze, with chalk marks instead of a list of visited cells. A robot keeps its marks in memory, which means it has to know which cell it is in. Like wall following, it finds a route, and not necessarily the shortest one.
Flood fill: how a micromouse solves a maze
A micromouse does not know where the walls are when it starts. It gives every cell a number: how many steps it is from the goal, going round any walls it knows about. It then drives downhill, always to the neighbouring cell with the smallest number. When it finds a wall it did not know about, it works the numbers out again and carries on downhill from where it is.
At the start the robot knows no blocks, so the numbers are just the steps to the goal across an empty grid:
4 3 2 1 0
5 4 3 2 1
6 5 4 3 2
7 6 5 4 3
8 7 6 5 4
Working the numbers out is a flood: give the goal 0, its open neighbours 1, their open neighbours that have no number yet 2, and so on outwards, like water spreading from the goal. It is breadth-first search from the goal, with a queue.
Here the robot only finds a block when it faces a cell it wants to move into and the sensor reads under 15 cm. When it does, it adds the block to its set, floods again and chooses again. Ties are broken by the order in WAYS: up, then right, then down, then left.
The program
from bugbot import *
from collections import deque
import math
connect()
# change the order of WAYS and press Run
# up, right, down, left, as headings in degrees
WAYS = [0, 90, 180, 270]
START = (10, 10) # the robot, in cm on the mat
GOAL = (90, 90) # the middle of the goal cell
CELL = 20 # each cell is 20 cm
def next_to(cell, h):
# the cell next door in direction h
return (cell[0] + round(CELL * math.sin(math.radians(h))),
cell[1] + round(CELL * math.cos(math.radians(h))))
def on_mat(cell):
return 0 < cell[0] < 100 and 0 < cell[1] < 100
def flood(blocked):
# steps from every cell to the goal, spreading
# out from the goal and never into a block
steps = {GOAL: 0}
queue = deque([GOAL])
while queue:
cell = queue.popleft()
for h in WAYS:
n = next_to(cell, h)
if on_mat(n) and n not in blocked and n not in steps:
steps[n] = steps[cell] + 1
queue.append(n)
return steps
def downhill(cell, steps):
# the way to the neighbour with the smallest number
best = None
for h in WAYS:
n = next_to(cell, h)
if n in steps and (best is None or steps[n] < steps[best[1]]):
best = (h, n)
return best
def show(cell, steps, blocked, trail):
# the numbers as shades: pale is near the goal
shades = ["#fff3c4", "#ffd88a", "#f6ad55", "#dd6b20", "#9c4221"]
for i, colour in enumerate(shades):
band = [c for c, v in steps.items() if min(v // 3, 4) == i]
draw("flood %d" % i, band, colour, "squares", 16)
draw("blocks found", list(blocked), "#333333", "squares", 18)
route = [cell]
while route[-1] != GOAL:
route.append(downhill(route[-1], steps)[1])
draw("robot", trail, "blue", "line", 2)
draw("route", route, "red", "line", 2)
plot("steps to the goal", steps[cell])
def face(h):
# turn on the spot to face h degrees
turn = (h - heading() + 180) % 360 - 180
if abs(turn) > 1:
turn_right(100, angle=turn)
def step(x, y):
# drive to the middle of the cell at (x, y),
# correcting any drift to the side first
px, py = position()
dx = x - START[0] - px
dy = y - START[1] - py
h = math.radians(heading())
ahead = dx * math.sin(h) + dy * math.cos(h)
side = dx * math.cos(h) - dy * math.sin(h)
if side > 1:
right(60, distance=side)
elif side < -1:
left(60, distance=-side)
forward(100, distance=ahead)
blocked = set() # the blocks it has found
steps = flood(blocked)
cell = START
trail = [START]
show(cell, steps, blocked, trail)
while cell != GOAL:
h, n = downhill(cell, steps)
face(h)
if distance() < 15:
# a block where it wanted to go:
# remember it and flood again
blocked.add(n)
steps = flood(blocked)
else:
step(*n)
cell = n
trail.append(cell)
show(cell, steps, blocked, trail)
print("cells moved:", len(trail) - 1)
print("blocks found:", len(blocked))
print("time:", round(clock()), "s")
Watch the chart and the red line together. The number falls by one with every move, from 8 at the start to 2 in the cell two to the left of the goal, along the top. There the robot finds the block to its right, floods again, and its number goes up to 4. Then it finds the block below it, and its number jumps to 8: the goal is now a long way round. The red line swings back down the left side. On the way down the robot tries each opening on the right, finds three more blocks, and its number goes up to 9 twice. Back at the start it is 8 again, and from there the number falls to 0 along the bottom and up the middle. Near the end it finds a sixth block, above the cell to the right of the middle, but that changes nothing, because going right was just as short. The one block it never met is the island: at the cell below the middle, going up and going right onto the island were both 4, and up comes first in WAYS.
On this first run flood fill moved the same 20 cells as the left hand rule, and it was quicker only because it turned less. Change WAYS to [90, 0, 180, 270], so ties go right first, and it goes along the bottom and up the right side: 8 cells in 21 s, without finding a single block. With no map, the first run is always partly luck.
What flood fill has that wall following does not is a guarantee. Between two blocks found, every move takes the robot one step nearer the goal on its current numbers. There are only so many blocks to find, so if there is any way to the goal, it gets there. Islands and loops make no difference, because it never follows a wall.
Here is the same program on the maze that beat the wall follower, with the goal in the middle. Only GOAL has changed.
The program
from bugbot import *
from collections import deque
import math
connect()
# change the order of WAYS and press Run
# up, right, down, left, as headings in degrees
WAYS = [0, 90, 180, 270]
START = (10, 10) # the robot, in cm on the mat
GOAL = (50, 50) # the goal: the middle cell
CELL = 20 # each cell is 20 cm
def next_to(cell, h):
# the cell next door in direction h
return (cell[0] + round(CELL * math.sin(math.radians(h))),
cell[1] + round(CELL * math.cos(math.radians(h))))
def on_mat(cell):
return 0 < cell[0] < 100 and 0 < cell[1] < 100
def flood(blocked):
# steps from every cell to the goal, spreading
# out from the goal and never into a block
steps = {GOAL: 0}
queue = deque([GOAL])
while queue:
cell = queue.popleft()
for h in WAYS:
n = next_to(cell, h)
if on_mat(n) and n not in blocked and n not in steps:
steps[n] = steps[cell] + 1
queue.append(n)
return steps
def downhill(cell, steps):
# the way to the neighbour with the smallest number
best = None
for h in WAYS:
n = next_to(cell, h)
if n in steps and (best is None or steps[n] < steps[best[1]]):
best = (h, n)
return best
def show(cell, steps, blocked, trail):
# the numbers as shades: pale is near the goal
shades = ["#fff3c4", "#ffd88a", "#f6ad55", "#dd6b20", "#9c4221"]
for i, colour in enumerate(shades):
band = [c for c, v in steps.items() if min(v // 3, 4) == i]
draw("flood %d" % i, band, colour, "squares", 16)
draw("blocks found", list(blocked), "#333333", "squares", 18)
route = [cell]
while route[-1] != GOAL:
route.append(downhill(route[-1], steps)[1])
draw("robot", trail, "blue", "line", 2)
draw("route", route, "red", "line", 2)
plot("steps to the goal", steps[cell])
def face(h):
# turn on the spot to face h degrees
turn = (h - heading() + 180) % 360 - 180
if abs(turn) > 1:
turn_right(100, angle=turn)
def step(x, y):
# drive to the middle of the cell at (x, y),
# correcting any drift to the side first
px, py = position()
dx = x - START[0] - px
dy = y - START[1] - py
h = math.radians(heading())
ahead = dx * math.sin(h) + dy * math.cos(h)
side = dx * math.cos(h) - dy * math.sin(h)
if side > 1:
right(60, distance=side)
elif side < -1:
left(60, distance=-side)
forward(100, distance=ahead)
blocked = set() # the blocks it has found
steps = flood(blocked)
cell = START
trail = [START]
show(cell, steps, blocked, trail)
while cell != GOAL:
h, n = downhill(cell, steps)
face(h)
if distance() < 15:
# a block where it wanted to go:
# remember it and flood again
blocked.add(n)
steps = flood(blocked)
else:
step(*n)
cell = n
trail.append(cell)
show(cell, steps, blocked, trail)
print("cells moved:", len(trail) - 1)
print("blocks found:", len(blocked))
print("time:", round(clock()), "s")
With no blocks known, the middle is only 4 steps from the start. The robot goes up the left side and tries to turn right into the ring twice. Each block it finds pushes its number up, to 4 and then 5, and moves the red line further round. By then the only way in it has not ruled out is the gap at the top, so it goes along the top and in. That is 8 cells, which is as short as any route to the middle of this maze. Change WAYS to [90, 0, 180, 270] and it goes along the bottom first. It finds 4 blocks down the right side of the ring before it gets round to the gap, and takes 12 cells and 46 s. Either way it gets there, where both hands of the wall follower went round for ever.
The fast run: the shortest route on a known map
A micromouse is allowed several runs. The first ones are for exploring, and the robot keeps the walls it has found. On the last run it floods with everything it knows and drives downhill as fast as it can. Here the robot is given the whole map, the seven blocks, before it moves. It prints the numbers, draws the route, then drives it without turning, because this robot can drive sideways as well as forwards.
The program
from bugbot import *
from collections import deque
import math
connect()
START = (10, 10) # the robot, in cm on the mat
GOAL = (90, 90) # the middle of the goal cell
CELL = 20 # each cell is 20 cm
# the middle of each 20 cm block: the whole map
BLOCKS = {(70, 90), (30, 70), (50, 70), (70, 70),
(30, 50), (30, 30), (70, 30)}
# up, right, down, left, as headings in degrees
WAYS = [0, 90, 180, 270]
def next_to(cell, h):
# the cell next door in direction h
return (cell[0] + round(CELL * math.sin(math.radians(h))),
cell[1] + round(CELL * math.cos(math.radians(h))))
def on_mat(cell):
return 0 < cell[0] < 100 and 0 < cell[1] < 100
def flood(blocked):
# steps from every cell to the goal, spreading
# out from the goal and never into a block
steps = {GOAL: 0}
queue = deque([GOAL])
while queue:
cell = queue.popleft()
for h in WAYS:
n = next_to(cell, h)
if on_mat(n) and n not in blocked and n not in steps:
steps[n] = steps[cell] + 1
queue.append(n)
return steps
def downhill(cell, steps):
# the way to the neighbour with the smallest number
best = None
for h in WAYS:
n = next_to(cell, h)
if n in steps and (best is None or steps[n] < steps[best[1]]):
best = (h, n)
return best
steps = flood(BLOCKS)
# print the numbers as a grid, top row first
for y in (90, 70, 50, 30, 10):
print(" ".join("%2s" % steps.get((x, y), "#")
for x in (10, 30, 50, 70, 90)))
# the numbers as shades: pale is near the goal
shades = ["#fff3c4", "#ffd88a", "#f6ad55", "#dd6b20", "#9c4221"]
for i, colour in enumerate(shades):
band = [c for c, v in steps.items() if min(v // 3, 4) == i]
draw("flood %d" % i, band, colour, "squares", 16)
route = [START]
while route[-1] != GOAL:
route.append(downhill(route[-1], steps)[1])
draw("route", route, "red", "line", 2)
print("route:", len(route) - 1, "cells")
# drive it, always to the lowest number next door
trail = [START]
plot("steps to the goal", steps[START])
for x, y in route[1:]:
px, py = position()
dx = x - START[0] - px
dy = y - START[1] - py
if dx > 1:
right(100, distance=dx)
elif dx < -1:
left(100, distance=-dx)
if dy > 1:
forward(100, distance=dy)
elif dy < -1:
backward(100, distance=-dy)
trail.append((x, y))
draw("robot", trail, "blue", "line", 2)
plot("steps to the goal", steps[(x, y)])
print("time:", round(clock()), "s")
It prints the flood as a grid, with # for each block:
12 13 14 # 0
11 # # # 1
10 # 4 3 2
9 # 5 # 3
8 7 6 5 4
Read it like a contour map. The start is 8, and from any cell there is always a neighbour one lower, so following the numbers down can only take 8 moves. The dead end at the top left is the highest ground on the map, 14, and the robot never goes near it. Give the robot only the 6 blocks it found on its first run, leaving out the island, and the only change is that the island's cell gets a 4. The route is the same 8 cells. A map does not have to be complete to give the shortest route, only complete enough.
Flooding from the goal and walking downhill is the same thing as breadth-first search from the start and following the parents back: both count steps outwards in rings. It gives the route with the fewest cells when every move costs the same. When moves cost different amounts, for example if turns are slow and straights are fast, Dijkstra's algorithm finds the cheapest route instead, and A* does the same while looking at fewer cells, by adding a guess at the distance still to go.
Which method to use
| Wall following | Trémaux | Flood fill | Planning on a known map | |
|---|---|---|---|---|
| Needs a map | no | no, only marks | builds one as it goes | yes |
| Needs to know which cell it is in | no | yes | yes | yes |
| Always reaches the goal | only if the walls round the goal join the outside wall | yes | yes | yes |
| Shortest route | only by luck | only by luck | once the map is complete enough | yes |
| On this page, first maze | 20 cells, or 8 with the other hand | no demo | 20 cells, or 8 with ties broken the other way | 8 cells |
| On this page, goal in the middle | round the outside for ever, with either hand | no demo | 8 cells, or 12 with ties broken the other way |
Use wall following when the maze is simple and the robot is simple: a few lines of code and one sensor. Use flood fill when the goal might be in the middle or there might be loops, or when the robot will do the same maze more than once and should get faster. When the map is known in advance, plan the whole route before moving, with breadth-first search, Dijkstra or A*.
The lessons below build this up a piece at a time. Getting round things and Project: the maze use the distance sensor to find walls and turn at corners, and the last challenge of the maze project is the left hand rule. A grid is a graph, Dijkstra and the cost of a step and A* and the heuristic plan routes on a map.
Questions
What is the best algorithm for a maze solving robot?
For a robot that has to find its way through a maze it has never seen, and then do it again quickly, flood fill. It works with loops and with the goal in the middle, and the map it builds on the way gives the shortest route on later runs. For a simple maze where every wall joins the outside wall, the left or right hand rule is shorter to write and needs no memory.
How does the left hand rule work in a maze?
Keep your left hand on a wall and never let go. At each step, turn left if you can, otherwise go straight on, otherwise turn right, otherwise turn round. If every wall in the maze is joined to the outside wall, this walks you along all of it, so you pass the exit. A robot with one front sensor does it by turning left, then turning right until the way ahead is clear, then moving one cell.
Why does the wall follower algorithm fail?
It only follows the wall it started on. If the goal is not on that wall, for example in the middle of a maze with walls that do not reach the outside, or if the robot starts with its hand on an island, it goes round the same loop for ever. On this page, with the goal in the middle of a ring of blocks, a robot following the edge of the mat went round a 16 cell lap and never came closer than 40 cm to the goal. Flood fill reached it in 8 cells.
Is the left hand rule better than the right hand rule?
Neither is better in general. Both reach the goal in the same mazes. Which is quicker depends on where the dead ends are. On this page the left hand rule took 20 cells, because it went into a dead end, and the right hand rule took 8.
What is the flood fill algorithm in micromouse?
Each cell of the maze gets a number: the steps from it to the goal, going round the walls the robot knows about. The robot moves to whichever neighbour has the smallest number. When it finds a new wall, it works all the numbers out again from the goal outwards, and carries on. Once it knows enough walls, following the numbers down gives the shortest route.
Is flood fill the same as breadth-first search?
Working out the numbers is a breadth-first search that starts at the goal: the goal gets 0, its neighbours 1, and so on outwards using a queue. What makes it the micromouse flood fill algorithm is doing it again every time the robot finds a wall, and driving downhill on the numbers in between.
What is micromouse?
A contest in which small robots, the mice, find their way to the middle of a maze on their own and then race there as fast as they can. The standard maze is 16 by 16 cells of 18 cm each, and the goal is the block of four cells in the middle. Mice explore on their first runs and are timed on their fastest one.
How do you find the shortest path in a maze?
If you know the maze, use breadth-first search from the start, or flood the maze from the goal and walk downhill: both give the route with the fewest steps. If moves cost different amounts, use Dijkstra's algorithm, or A* to look at fewer cells. If you do not know the maze, explore with flood fill first, then plan on the map you built.
What is Trémaux's algorithm?
A way to solve any maze by leaving marks. Mark each corridor as you use it. Prefer corridors with no marks, never use one with two, and turn back if a new corridor brings you to a junction you have already visited. It always finds the goal, even in a maze with loops, because no corridor is walked more than twice. It is depth-first search done by someone inside the maze.
What sensors does a maze solving robot need?
At least a way to tell whether there is a wall ahead, and usually to each side. The robot on this page has one distance sensor facing forwards and turns to look. Micromouse robots usually have several infrared sensors pointing forwards and to the sides, so they can see walls without stopping. Flood fill and Trémaux also need the robot to know which cell it is in, which usually comes from counting how far the wheels have turned.
How do you program a maze solving robot in Python?
Store where the robot is as a cell, and the way it is facing as 0, 90, 180 or 270 degrees. For wall following, loop: turn to one side, turn back the other way while the sensor sees a wall, move one cell. For flood fill, keep a set of the blocks found, fill a dictionary of steps from the goal with a deque, and each time round the loop move to the neighbour with the smallest number, flooding again whenever the sensor finds a new block. The demos on this page are complete programs of 55 to 100 lines that do each of these.
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- 2.4 Getting round things Sensing, Robot club
- 2.6 Project: the maze Sensing, Robot club
- U9.2 A grid is a graph Planning, University
- U9.3 Dijkstra and the cost of a step Planning, University
- U9.4 A* and the heuristic Planning, University
- A2.10 Project: out of the dead end Recursion and computational thinking, A level