My MATLAB® program, amaze, generates mazes by combining old friends, numgrid and delsq, with a new friend, the graph object. Let's see how we make this example maze.

Contents

Beginnings

Select a maze size. Our example is 15-by-15.

    n = 15;

We are going to make two graphs, the barriers and the cells. The barriers, B, is the graph of the classic five-point discrete Laplacian on an n-by-n square grid. Each node is the interior is connected to its four closest neighbors and each node on the boundary has two or three neighbors. The functions delsq and numgrid have been in the sparfun directory since sparse matrices were introduced in 1992. The graph object was introduced in R2015b. We are going to carve a path through this grid.

    Db = delsq(numgrid('S',n+2));
    B = graph(logical(Db),'omitselfloops');

The cells, C, are also based on the five-point discrete Laplacian, but on an (n-1)-by-(n-1) grid. Initially C has just the nodes, no edges. When we plot B and C together, the nodes of C are centered in the squares of B.

    m = n-1;
    Dc = delsq(numgrid('S',m+2));
    C = graph(logical(Dc),'omitselfloops');

Random walks

    available = 1:m^2; % Nodes we haven't visited yet.
    branches = [];
    branching = 'middle';
    tree = zeros(0,2); % Depth first search.
    p = 1;

Now we make a series of random walks on C.

   while true  % Break when available is empty

        available(p) = 0;
        if ~any(available)
            break
        end

Each step is from a node to a random choice of one of its neighbors that has not already been visited.

        [~,~,ngh] = find(available(neighbors(C,p)));

        if ~isempty(ngh)

            idx = randi(length(ngh));  % Random choice.
            q = ngh(idx);              % Next cell.
            tree(end+1,:) = [p q];

At the same time, the edge in the barrier B that is blocking the step is removed.

            [i,j] = wall(p,q);
            B = rmedge(B,i,j);

We keep a list of the nodes where a random choice between two or three neighbors is made.

            if length(ngh) > 1
                branches(end+1) = p;
            end

            p = q;

Eventually the walk reaches a dead end, a node whose neighbors have all been visited. Here is the first such walk in our example.

Backtrack

When we reach a dead end, we backtrack to one of the nodes on our list of nodes where we had a choice of available neighbors. Here another kind of choice is made. We can go back to the first node on the list, to the node in the middle of the list, or to the last node on the list.

        else

            switch branching
                case 'first'
                    idx = 1;
                case 'last'
                    idx = length(branches);
                otherwise
                    idx = round(length(branches)/2);
            end

            p = branches(idx);
            branches(idx) = [];
        end

Here is the result of backtracking to the middle and then walking to a second dead end.

Here is the result after several more backtracks.

    end
    C = graph(tree(:,1),tree(:,2));

Near the end of this process, the length of a path before a dead end and a backtrack becomes shorter and shorter. A path may involve a single point. Eventually all the nodes in C are covered. Here is the final result.

When the entire path is plotted with linestyle = 'none' we have the maze.

Shortest path

We can easily "solve" the maze by asking for the shortest path from one corner to another.

    path = shortestpath(C,1,m^2);

(Exercise: How does the branching parameter affect the average length of this path?)

Animation

Software

I have a program called amazing that allows you to investigate amaze. I've submitted it to the MATLAB Central File Exchange and will put the link here. I will also add amazing to version 4.40 of Cleve's Laboratory.

Thanks

Thanks to Pat Quillen who provided invaluable help.

Get the MATLAB code

Published with MATLAB® R2018b