Maze solver and generator in Python

Question

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
    parser.add_argument("-g", "--generate", default=""
                        , help="filename used for generated maze")
    parser.add_argument("-s", "--size", type=int, default=50
                        , help="size NxN of generated maze")

    # solver arguments
    parser.add_argument("-si", "--solve", default=""
                            , help="maze file to solve")
    parser.add_argument("-sg", "--solvegenerated", action="store_true"
                        , default=False, help="generate and then solve a maze")
    parser.add_argument("-dfs", "--dfs", action="store_true"
                        , default=False, help="solve using dfs algorithm")
    parser.add_argument("-dji", "--djikstra", action="store_true"
                        , 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))
    maze_matrix= maze.load()

    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'
    solved_matrix = solved.load()

    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'
    maze_matrix = maze.load()

    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

Answer 1

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()
   

   and instead of testing:

   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:
                graph[x, y].add((nx, ny))
    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:
        path.add(v)
        neighbours = graph[v] - path
        if neighbours:
            x, y = v
            nx, ny = neighbour = random.choice(list(neighbours))
            wall = (x + nx) // 2, (y + ny) // 2
            path.add(wall)
            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))
    pixels = image.load()
    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)
        # Add entrance and exit.
        path.update([(1, 0), (size_real - 1, size_real - 2)])
        with timer("generating image"):
            generate_image(filename, size_real, path)

Answer 2

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
parser.add_argument("-g", "--generate", default="",
                    help="filename used for generated maze")

or

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

or

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

---

Instead of

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 an arbitrary of it will appear as change of all of them. (Thanks Gareth Rees for his comment.)

Answer 3

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?