Maze Program

Introduction

This is part of an old program series I’ll be writing up. During college I was into Computer Graphics, Compilers, Operating Systems, anything that got to the “heart” of practical computing. Our lab machines were running Solaris at the time (or maybe it was Ubuntu at that point?) and there was a pretty generous screensaver collection installed on them. One day something like this Maze Screensaver was running and I got curious how mazes were generated.

After some googling I found that it’s pretty simple and mostly involves treating the maze cells as a graph and running some standard graph algorithms on it.

Maze Video

This is a video of the OpenGL program I wrote after that investigation. It’s pretty old and uses “old” style OpenGL with glVertex2f() glColor3f() etc. And it looks like there’s some floating point issues with the walls and scaling. But it works! And is interesting to look at.

Building a Maze

You can think of a maze as a graph. Each “box” is a vertex and the space in between represents edges. A wall signals that there is no edge between two neighboring vertices. While a lack of wall indicates the two vertices are connected. A good maze shouldn’t have any “islands”, or areas that aren’t possible to get to. Every node (vertex) should be accessible from any other node, even though the path may be a little indirect.

One simple way to achieve this property is to actually model the maze as a graph and run a standard graph algorithm like Breadth-First-Search or Depth-First-Search. These algorithms will visit each node in the graph once and if we keep track of the edges that were crossed, we can generate our maze! Then, it’s simply a matter of drawing the final graph, putting up walls where there could be an edge, but isn’t.

Wikipedia has an excellent high-level description of the algorithm

The randomized depth-first search algorithm of maze generation can be implemented using a stack:

1. Start with a grid that has no edges (all walls)
2. Make the initial cell the current cell
3. Push the current cell to the stack and mark it as visited
4. While the stack is not empty
    If the current cell has unvisited neighbours
       1. Choose one of these neighbours randomly
       2. Remove the wall (add an edge) between the current
          cell and the chosen neighbor
       3. Push the neighbor to the stack and mark it as visited
       4. Make the neighbor the current cell
    Else
       1. Pop a cell from the stack and make it the current cell

Backtracking occurs when there are no more unvisited neighbors of the current cell. In that case the algorithm pops cells from the stack until it finds a cell with an unvisited neighbor from which a new branch is started.

Some slightly lower-level pseudo code

struct Vertex {
    bool left_edge   = false;
    bool right_edge  = false;
    bool top_edge    = false;
    bool bottom_edge = false;
    bool visited     = false;
};

enum Direction {
    Left, Right, Top, Bottom
}

struct NeighborInfo {
    Vertex vertex;
    Direction direction;
};

struct Maze {
    int width;
    int height;
    Vertex vertices[width][height];
};

Maze BuildMaze(width, height) {
    // Queue, list, vector, etc
    // depends on pick algorithm
    Collection<Vertex> activeSet; 

    Maze maze = { width, height, Vertex[width][height] };

    Point start_loc = { random_int(width), random_int(height) };

    activeSet.add(maze.vertices[loc.x][loc.y]);
    maze.vertices[loc.x][loc.y].visited = true;

    while (!activeSet.is_empty()) {
        Vertex picked = pick(activeSet);

        Collection<NeighborInfo> neighbors = getNeighbors(maze, picked);
        if (neighbors.is_empty()) {
            activeSet.remove(picked);
        } else {
            NeighborInfo ni = pickNeighbor(neighbors);
            ni.vertex.visited = true;
            setEdges(picked, ni);
            activeSet.add(ni.vertex);
        }
    }
}

void setEdges(Vertex picked, NeighborInfo info) {
    if (info.direction == Left) {
        picked.left = true;
        info.right = true;
    }
    if (info.direction == Right) {
        picked.right = true;
        info.left = true;
    }
    ...
}

NeighborInfo pickNeighbor(Collection<NeighborInfo> neighbors) {
    return neighbors.get(random_int(neighbors.length()));
}

Collection<NeighborInfo> getNeighbors(Maze maze, Vertex picked)
{
    // Get Left, Right, Top, Bottom neighbors,
    // but only if they're not visited.
    Collection<NeighborInfo> neighbors;
    Vertex left = getNeighbor(maze, picked, Left); 
    Vertex right = getNeighbor(maze, picked, Right);
    ...
    if (left && !left.visited) {
        neighbors.add(NeighborInfo{left, Left}));
    }
    if (right && !right.visited) {
        neighbors.add(NeighborInfo{right, Right});
    }
    ...
    return neighbors;
}

Interactive Example

Here is a JavaScript+Canvas (written in OCaml) implementation of a couple algorithms. The link to the code is posted below. It uses an implementation similar to the code shown above.

Code

Code can be found here

Note: You’ll have to click “Reset” after any changes in the drop down for it to take effect.

Depth First Search is more or less the ‘Randomized Depth First Search’ from the wikipedia code above.

Breadth First Search is a breadth first search, and as such, generates pretty bad mazes.

Randomized is a bit of a combination of the two. It runs depth first search for a bit, then picks another random starting node and runs some more depth first search.