# Maze solver and generator in Python

After watching Computerphile's video I decided to create my own maze solver and generator in Python. I've never written anything in Python so I'd like to get some feedback about my code, specifically about:

• code style
• project structure
• algorithms implementation

This is my first mini-project and as such I have no idea what is the correct way of doing things (e.g. arguments parsing baffles me a lot, I've no idea how to do it "properly").

mazr.py:

#!/usr/bin/env python3

import argparse
import generator
import solver

def parse_arguments():
parser = argparse.ArgumentParser()

# generator arguments
, help="filename used for generated maze")
, help="size NxN of generated maze")

# solver arguments
, help="maze file to solve")
, default=False, help="generate and then solve a maze")
, default=False, help="solve using dfs algorithm")
, default=False
, help="solve using djikstra algorithm")

return parser.parse_args()

def main():
arguments = parse_arguments()

if not arguments.generate == "":
generator.create(arguments.generate, arguments.size)
if arguments.solvegenerated:
solver.solve(arguments.generate+".png", arguments.dfs,
arguments.djikstra)
if not arguments.solve == "":
solver.solve(arguments.solve, arguments.dfs, arguments.djikstra)

if __name__ == "__main__":
main()


generator.py:

#!/usr/bin/env python3

import random
import time
from PIL import Image

def generate_graph(size):
graph = [[] for i in range(size*size)]
graph_time = time.time()
verticies = 0
edges = 0

print("[*] generating graph")

posx = 1
for x in range(size):
posy = 1
for y in range(size):
verticies += 1

# graph[vertex's number] = [(it's real position), [connected
# vertex's number, (wall between verticies position)]]

# vertex's number
v = x*size+y

# append vertex's real position
graph[v].append((posx, posy))

if not x < 1:
graph[v].append([v-size, (posx-1, posy)])
edges += 1
if x+1 < size:
graph[v].append([v+size, (posx+1, posy)])
edges += 1
if not y < 1:
graph[v].append([v-1, (posx, posy-1)])
edges += 1
if y+1 < size:
graph[v].append([v+1, (posx, posy+1)])
edges += 1

# skip one pixel for wall
posy += 2
posx += 2

print(verticies, "verticies")
print(edges, "edges")
print("[#] finished in", time.time()-graph_time, "seconds")

return graph

def generate_maze(graph):
stack = []
path = []
visited = [False for i in range(len(graph))]

maze_time = time.time()
print("[*] generating maze")

# current vertex
v = random.randint(1, len(graph)) - 1
stack.append(v)

while stack:
visited[v] = True
path.append(graph[v][0])

valid = []
for i in range(1, len(graph[v])):
if not visited[graph[v][i][0]]:
valid.append(graph[v][i])

if valid:
choice = random.choice(valid)
path.append(choice[1])
stack.append(v)
v = choice[0]
else:
v = stack.pop()

print("[#] finished in", time.time()-maze_time, "seconds")
return path

def generate_image(filename, size, path):
print("[*] generating image")
image_time = time.time()

maze = Image.new('RGB', (size, size))

for p in range(len(path)):
maze_matrix[path[p]] = (255, 255, 255)
# entrance and exit points
print("creating entry point at (1, 0)")
maze_matrix[(1, 0)] = (255, 255, 255)
print("creating exit point at", (size-1, size-2))
maze_matrix[(size-1, size-2)] = (255, 255, 255)

maze.save(filename)

print("[#] finished in", time.time()-image_time, "seconds")

def create(filename, size):
# correcting and setting up variables
filename += ".png"
size_real = (2 * size) + 1

creation_time = time.time()

print("[*] creating", filename)
print("size =", size_real, "x", size_real)

graph = generate_graph(size)
path = generate_maze(graph)
generate_image(filename, size_real, path)

print("[#] finished in", time.time()-creation_time, "seconds")


solver.py:

#!/usr/bin/env python3

import time
import os
from PIL import Image
import solve_dfs
import solve_dji

def save(filename, path, entrance, exit, algorithm):
solve = (204, 52, 53)
point = (57, 129, 237)

print("[#] generating image")
saving_time = time.time()

solved = Image.open(filename)
solved.mode = 'RGB'

for i in range(len(path)):
solved_matrix[path[i]] = solve

solved_matrix[entrance] = point
solved_matrix[exit] = point

filename = os.path.splitext(os.path.basename(filename))[0]+algorithm+".png"
solved.save(filename)

print("saved", filename)

print("[#] finished in", time.time()-saving_time, "seconds")

def generate_graph(maze, width, height):
wall = (0, 0, 0)
verticies = 0
edges = 0
graph = [[] for i in range(width*height)]

print("[*] generating graph")
graph_time = time.time()

for x in range(width):
for y in range(height):
if not maze[x, y] == wall:
verticies += 1

# vertex's number
v = x*width+y

# append position
graph[v].append((x, y))

if not x < 1:
if not maze[x-1, y] == wall:
graph[v].append(v-width)
edges += 1
if x+1 < width:
if not maze[x+1, y] == wall:
graph[v].append(v+width)
edges += 1
if not y < 1:
if not maze[x, y-1] == wall:
graph[v].append(v-1)
edges += 1
if y+1 < height:
if not maze[x, y+1] == wall:
graph[v].append(v+1)
edges += 1

print(verticies, "verticies")
print(edges, "edges")
print("[#] finished in", time.time()-graph_time, "seconds")

return graph

def get_entrance_and_exit(maze, width, height):
wall = (0, 0, 0)

entrance = (0, 0)
exit = (0, 0)

print("[*] searching for entrance and exit")
entry_time = time.time()

for x in range(width):
if not maze[x, 0] == wall:
entrance = (x, 0)
break
for x in range(width):
if not maze[x, height-1] == wall:
exit = (x, height-1)
break
for y in range(height):
if not maze[0, y] == wall:
entrance = (0, y)
break
for y in range(height):
if not maze[width-1, y] == wall:
exit = (width-1, y)
break

print("found entrance at", entrance)
print("found exit at", exit)

print("[#] finished in", time.time()-entry_time, "seconds")

return entrance, exit

def solve(filename, dfs, dji):
print("[*] solving", filename)
solve_time = time.time()

print("opening image file")

try:
maze = Image.open(filename)
except:
print("unable to open file, quiting")
return

width, height = maze.size
print("size =", width, "x", height)
maze.mode = 'RGB'

graph = generate_graph(maze_matrix, width, height)
entrance, exit = get_entrance_and_exit(maze_matrix, width, height)

if dfs:
path = solve_dfs.alg(graph, entrance[0]*width+entrance[1], exit)
save(filename, path, entrance, exit, "DFS")
if dji:
path = solve_dji.alg(graph, entrance[0]*width+entrance[1]
, exit[0]*width+ exit[1])
save(filename, path, entrance, exit, "DJIKSTRA")

print("[#] finished in", time.time()-solve_time, "seconds")


solve_dfs.py:

#!/usr/bin/env python3

import time

def alg(graph, entrance, exit):
visited = [False for i in range(len(graph))]
path = []

print("[*] solving using dfs")
dfs_time = time.time()

def dfs(v):
if graph[v][0] == exit:
return True

visited[v] = True

for i in range(1, len(graph[v])):
if not visited[graph[v][i]]:
if dfs(graph[v][i]):
path.append(graph[v][0])
return True

return False

try:
dfs(entrance)
except:
print("maze is simply to big for recursion, use other algorithm")
return []
print("solved in", len(path)+1, "steps") # +1 because it lacks exit

print("[#] finished in", time.time()-dfs_time, "seconds")
return path


solve_dji.py:

#!/usr/bin/env python3

import heapq
import time

def alg(graph, entrance, exit):
path = []

visited = [False for i in range(len(graph))]
distance = [9999999999 for i in range(len(graph))]
distance[entrance] = 0
previous = [0 for i in range(len(graph))]

print("[*] solving using djikstra")
djikstra_time = time.time()

# priority queue
pqueue = []
heapq.heappush(pqueue, (0, entrance))

while pqueue:
# distance and vertex
d, v = heapq.heappop(pqueue)

if not visited[v]:
for i in range(1, len(graph[v])):
if distance[graph[v][i]] > d + 1:
distance[graph[v][i]] = d + 1
heapq.heappush(pqueue, (d+1, graph[v][i]))

previous[graph[v][i]] = v

visited[v] = True

v = previous[exit]
while not v == entrance:
path.append(graph[v][0])
v = previous[v]

print("solved in", len(path)+2, "steps") # +2 because it lacks entrance and
# exit
print("[#] finished in", time.time() - djikstra_time, "seconds")

return path


Just reviewing generator.py.

### 1. Review

1. There are no docstrings. What do these functions do? What arguments do they take? What do they return?

2. "verticies" is a typo for "vertices".

3. There's repetitive code for printing progress messages and measuring the time taken. I would avoid this repetition using a context manager, like this:

from contextlib import contextmanager

@contextmanager
def timer(message):
"Context manager that reports the time taken by a block of code."
print("[*]", message)
start = time.time()
yield
print("[#] finished in {:.3f} seconds".format(time.time() - start))


and then in create you can write:

with timer("creating {}".format(filename)):
print("size =", size_real, "x", size_real)
with timer("generating graph"):
graph = generate_graph(size)
with timer("generating maze"):
path = generate_maze(graph)
with timer("generating image"):
generate_image(filename, size_real, path)


This keeps the timing code out of the individual functions, making them shorter, simpler, and easier to test.

4. The graph data structure is complicated, and the only clue as to how it works is this comment:

# graph[vertex's number] = [(it's real position), [connected
# vertex's number, (wall between verticies position)]]


Lists and tuples are very convenient for building simple data structures, but code that accesses them is hard to understand. For example, what does this line test?

if not visited[graph[v][i][0]]:


By reading the comment, we can figure out that graph[v][i][0] is the vertex number of the i-1-th neighbour of vertex number v. But it takes considerable effort to figure this out — first you have to find the comment explaining the data structure, and then you have to figure out that the comment isn't telling the whole truth (because there can be multiple connected vertices, not just one as in the comment).

So let's see if we can simplify this data structure. The first thing to observe is that vertices are represented by integers, not by their coordinates. Why is that? There are two places where this fact is used. First, in the visited list:

visited = [False for i in range(len(graph))]


But we could make this a set instead:

visited = set()


if not visited[graph[v][i][0]]:


we can test for membership in the set:

if graph[v][i][0] not in visited:


Second, in this line picking a random vertex:

v = random.randint(1, len(graph)) - 1


But there are other ways of doing this, for example like this:

v = random.choice(list(graph))


After making these two changes, the vertices can be represented by any hashable objects, in particular by tuples (posx, posy).

The other redundant piece of information in the graph data structure is the position of the wall between a vertex and its neighbour. This is redundant because if you have a vertex at $v_x, v_y$ and a neighbouring vertex at $w_x, w_y$, then the wall must be exactly halfway between them, that is, at $${v_x + w_x \over 2}, {v_y + w_y \over 2}.$$ So we can omit the wall from the data structure, simplifying it to:

# Mapping from vertex coordinates to set of coordinates of
# neighbouring vertices: graph[x, y] = {(x1, y1), (x2, y2), ...}


(We'll see later why it's convenient to have a set of neighbours instead of a list.)

A convenient way to construct such a data structure is to use a collections.defaultdict.

5. This code iterates over the logical coordinates x, y and maintaining separate real coordinates posx, posy:

posx = 1
for x in range(size):
posy = 1
for y in range(size):
# ...
# skip one pixel for wall
posy += 2
posx += 2


Instead, iterate directly over the real coordinates:

# Vertices are at odd coordinates (leaving room for walls).
coords = range(1, size * 2, 2)
for x in coords:
for y in coords:


Now you can use itertools.product to loop over both coordinates simultaneously:

for x, y in product(coords, repeat=2):

6. There's repetitive code for adding the neighbours. The repetition can be avoided by making a list of cardinal directions:

# List of cardinal directions.
_DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)]


and then iterating over it:

for x, y in product(coords, repeat=2):
for dx, dy in _DIRECTIONS:
nx, ny = x + dx * 2, y + dy * 2
if nx in coords and ny in coords:
graph[x, y].append((nx, ny))

7. In generate_maze, there are two data structures visited (containing all the visited vertices) and path (containing all the visited vertices plus the walls between them). But the only thing we use visited for is to get a list of unvisited neighbours, so we could use path for this, and avoid the need for visited at all.

8. Since the image is black-and-white, it's wasteful to use format 'RGB' which has 24 bits per pixel. Format '1' uses 1 bit per pixel. (The saving on disk is only about 50% since PNG is compressed, but still worth it.)

9. I recommend refactoring generate_image so that it doesn't have to know anything about mazes — if its only job is to make the image then it will be simpler and easier to understand. This can easily be done by adding the entrance and exit to path before calling generate_image.

### 2. Revised code

#!/usr/bin/env python3

from collections import defaultdict
from contextlib import contextmanager
from itertools import product
import random
import time
from PIL import Image

# List of cardinal directions.
_DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def generate_graph(size):
"""Return size-by-size maze graph in the form of a mapping from vertex
coordinates to sets of coordinates of neighbouring vertices, that is:

graph[x, y] = {(x1, y1), (x2, y2), ...}

Vertices are placed at odd coordinates, leaving room for walls.

"""
graph = defaultdict(set)
coords = range(1, size * 2, 2)
for x, y in product(coords, repeat=2):
for dx, dy in _DIRECTIONS:
nx, ny = x + dx * 2, y + dy * 2
if nx in coords and ny in coords:
return graph

def generate_maze(graph):
"""Given a graph as returned by generate_graph, return the set of
coordinates on the path in a random maze on that graph.

"""
v = random.choice(list(graph)) # Current vertex.
stack = [v]                    # Depth-first search stack.
path = set()        # Visited vertices and the walls between them.
while stack:
neighbours = graph[v] - path
if neighbours:
x, y = v
nx, ny = neighbour = random.choice(list(neighbours))
wall = (x + nx) // 2, (y + ny) // 2
stack.append(neighbour)
v = neighbour
else:
v = stack.pop()
return path

def generate_image(filename, size, path):
"""Create a size-by-size black-and-white image, with white on path and
black elsewhere, and save it to filename.

"""
image = Image.new('1', (size, size))
for p in path:
pixels[p] = 1
image.save(filename)

@contextmanager
def timer(message):
"Context manager that reports the time taken by a block of code."
print("[*]", message)
start = time.time()
yield
print("[#] finished in {:.3f} seconds".format(time.time() - start))

def create(filename, size):
"Create a size-by-size maze and save it to filename."
ext = '.png'
if not filename.endswith(ext):
filename += ext
size_real = (2 * size) + 1
with timer("creating {}".format(filename)):
print("size =", size_real, "x", size_real)
with timer("generating graph"):
graph = generate_graph(size)
with timer("generating maze"):
path = generate_maze(graph)
path.update([(1, 0), (size_real - 1, size_real - 2)])
with timer("generating image"):
generate_image(filename, size_real, path)


Some notes to your coding styles (different from PEP 8 -- Style Guide for Python Code and others):

parser.add_argument("-g", "--generate", default=""
, help="filename used for generated maze")


(and similar) should be

# Aligned with opening delimiter, but break line after comma
help="filename used for generated maze")


or

# Hanging indents should add a level
"-g", "--generate", default="",
help="filename used for generated maze")


or

# More indentation included to distinguish this from the rest
"-g", "--generate", default="",
help="filename used for generated maze")


if not arguments.generate == "":


(and similar ones) use more transparent

if arguments.generate:


as a non-empty string has logical value True (and it's a common idiom in Python).

Instead of unused variables use the underscore character _ (or - better two underscores __):

Not

graph = [[] for i in range(size*size)]


but

graph = [[] for __ in range(size*size)]


or - the simplest way -

graph = [[]] * size * size


but be careful - the last statement gives you the list where every sublist is the same mutable object, so the change of arbitrary of it will appear as change of all of them. (Thanks Gareth Rees for his comment.)

• [[]] * size * size won't work quite the way you want it to — all the inner lists will be the same. (To see how it goes wrong, try a = [[]] * 2 * 2; a[0].append(1); print(a).) – Gareth Rees Jul 15 '17 at 21:22
• @GarethRees - Oh, my very hard error - and OP does something similar as you shown. Thanks, I am going to edit my answer. – MarianD Jul 15 '17 at 23:04

There are a couple of typo's in your code and filenames. I was going to list them all, but it's a long list.

Edsger W. Dijkstra, is spelled with IJ. Not JI. So every reference to dji or djikstra is a typo. Quite a consistent typo, but a user won't expect having to use -dji or --djikstra as arguments. So it needs to be replaced.

Except djikstra_time though, that simply needs to be renamed to something more obvious. start_time perhaps?