Every time you play, this Python program digs a brand new maze with a maze generator (depth-first search with backtracking), then lets you walk from S to E with W, A, S and D. Stuck? Type solve and a breadth-first search draws the shortest path.
Two classic algorithms in one small game: perfect for learning how programs explore grids.
Play Maze Runner
Press โถ Play to start the game. When it asks you something, type your answer and press Enter.
View and edit the code (76 lines)
How to play
- You are @. Move with w (up), a (left), s (down), d (right). You can type several at once, like ddss.
- Walls are #. Reach E to escape.
- Type solve to see the shortest way out.
The complete Maze Runner code
Here is the whole program (76 lines). It only uses Python's standard library, so it runs anywhere Python 3 is installed.
import random
from collections import deque
W, H = 7, 5 # maze size in cells
COLS, ROWS = W * 2 + 1, H * 2 + 1 # size in characters
maze = [["#"] * COLS for _ in range(ROWS)]
def carve(cx, cy):
maze[cy * 2 + 1][cx * 2 + 1] = " "
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
random.shuffle(dirs)
for dx, dy in dirs:
nx, ny = cx + dx, cy + dy
if 0 <= nx < W and 0 <= ny < H and maze[ny * 2 + 1][nx * 2 + 1] == "#":
maze[cy * 2 + 1 + dy][cx * 2 + 1 + dx] = " " # knock down the wall between
carve(nx, ny)
def shortest_path(start, goal):
came = {start: None}
queue = deque([start])
while queue:
spot = queue.popleft()
if spot == goal:
break
x, y = spot
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if maze[ny][nx] != "#" and (nx, ny) not in came:
came[(nx, ny)] = spot
queue.append((nx, ny))
path = []
while spot:
path.append(spot)
spot = came[spot]
return path[::-1]
def show(trail=()):
for y in range(ROWS):
line = ""
for x in range(COLS):
if (x, y) == player:
line += "@"
elif (x, y) == goal:
line += "E"
elif (x, y) in trail:
line += "."
else:
line += maze[y][x]
print(line)
carve(0, 0)
player, goal = (1, 1), (COLS - 2, ROWS - 2)
MOVES = {"w": (0, -1), "s": (0, 1), "a": (-1, 0), "d": (1, 0)}
steps = 0
print("MAZE RUNNER - get from @ to E with w a s d")
while player != goal:
show()
keys = input("Move: ").strip().lower()
if keys == "solve":
show(shortest_path(player, goal))
print("Follow the dots!")
player = goal
break
for k in keys:
if k in MOVES:
nx, ny = player[0] + MOVES[k][0], player[1] + MOVES[k][1]
if maze[ny][nx] == "#":
print("Bump! A wall.")
break
player = (nx, ny)
steps += 1
print(f"You escaped the maze in {steps} steps!" if steps else "Maze solved.")How the Maze Runner game works, step by step
01Start with solid walls
Each maze cell sits at an odd row and column of a character grid; the even rows and columns are walls between cells. We start with every character a wall.
maze = [["#"] * COLS for _ in range(ROWS)]02Dig with depth-first search
From a cell, shuffle the four directions and visit each neighbour that hasn't been dug yet, knocking down the wall in between. The function calls itself, so it goes deep down one corridor and backs up when it hits a dead end. That's why the mazes have long winding paths.
random.shuffle(dirs)
for dx, dy in dirs:
...
carve(nx, ny)03Move the player
A dictionary turns keys into steps. Before moving, check the target square isn't a wall. Looping over the typed text lets you enter several moves at once.
MOVES = {"w": (0, -1), "s": (0, 1), "a": (-1, 0), "d": (1, 0)}04Find the shortest way out
Breadth-first search explores in rings: first squares 1 step away, then 2, then 3. A deque is a fast queue. Each square remembers where it came from, so we can walk back from the exit to build the path.
queue = deque([start])
while queue:
spot = queue.popleft()What you'll learn
- Grids of characters
- Recursion: depth-first search
- Queues with
collections.deque - Breadth-first search and shortest paths
- Dictionaries for key controls
Python concepts in this game:
Maze Runner coding challenges
Write the key parts of the game yourself. Press Run to try your code and Check to test it. Each challenge you pass earns a star (saved in this browser).
Can I step there?
Write can_move(maze, x, y): maze is a list of strings. Return True if position (x, y) is inside the maze and not a #. Remember: maze[y][x].
Hint
Check the bounds first, then maze[y][x] != "#".
Show a solution
def can_move(maze, x, y):
if not (0 <= y < len(maze) and 0 <= x < len(maze[0])):
return False
return maze[y][x] != "#"
M = ["#####",
"# E#",
"#####"]
print(can_move(M, 1, 1))Follow the keys
Write walk(maze, start, keys): start at (x, y), move for each letter in keys (w up, s down, a left, d right) and stop early at the first wall. Return the final position.
Hint
For each key, work out the next square. If it's a #, break; otherwise update x, y.
Show a solution
MOVES = {"w": (0, -1), "s": (0, 1), "a": (-1, 0), "d": (1, 0)}
def walk(maze, start, keys):
x, y = start
for k in keys:
dx, dy = MOVES[k]
if maze[y + dy][x + dx] == "#":
break
x, y = x + dx, y + dy
return (x, y)
M = ["#####",
"# #",
"### #",
"# #",
"#####"]
print(walk(M, (1, 1), "ddss"))How far is the exit?
Write distance(maze, start, goal) using breadth-first search: return the smallest number of steps from start to goal, or -1 if it can't be reached.
Hint
Pop a square, return its step count if it's the goal, otherwise add each open, unseen neighbour with steps + 1.
Show a solution
from collections import deque
def distance(maze, start, goal):
steps = {start: 0}
queue = deque([start])
while queue:
x, y = queue.popleft()
if (x, y) == goal:
return steps[(x, y)]
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if maze[ny][nx] != "#" and (nx, ny) not in steps:
steps[(nx, ny)] = steps[(x, y)] + 1
queue.append((nx, ny))
return -1
M = ["#######",
"# #",
"# ### #",
"# # #",
"#######"]
print(distance(M, (1, 1), (5, 3)))Make it your own
Once your challenges pass, try one of these upgrades:
- Add keys and locked doors inside the maze.
- Make bigger mazes and count your moves against the shortest path.
- Draw the maze with turtle instead of text.
- Try a different generator, like Prim's algorithm.
Frequently asked questions
How do you generate a maze in Python?
Start with a grid full of walls and run a depth-first search from one cell: visit unvisited neighbours in random order and remove the wall between the current cell and the next one.
How do you solve a maze in Python?
Breadth-first search with a queue finds the shortest path. Store where each square was reached from, then walk back from the exit to the start.
Why are maze cells on odd rows and columns?
The even rows and columns hold the walls between cells. That way removing one wall character joins two cells.