ProcGen Fun 3: Simple mazes

[List of posts | source code for this post]

So far in this series we have given ourseleves the ability to generate random values corresponding to some distribution. In this post we're going to actually start generating something pretty, namely some mazes!

Much of the next few posts takes inspiration from the book Mazes for Programmers by Jamis Buck. It's well worth a read!

Since the last post in this series, I've put together a playground website where you can run the algorithms for yourself and see the results. This will be particularly fun to watch as we look at procedural generation of mazes.

Representing a maze in code

To start with, we need a grid to work on. A grid is made up of cells, which we can partition into rows and columns.

We can refer to columns using an X coordinate and rows using a Y coordinate (0-indexed, of course!). For example, the highlighted cell in the below image is the cell with X=4 and Y=6.

We can represent this in code with Cell and Grid types.

public record Cell(int X, int Y);

public class Grid
{
    public Grid(int width, int height)
    {
        this.Width = width;
        this.Height = height;
        this.Cells =
            (from y in Enumerable.Range(0, this.Height)
             from x in Enumerable.Range(0, this.Width)
             select new Cell(x, y))
             .ToList();
    }

    public int Width { get; }

    public int Height { get; }

    public IEnumerable<Cell> Cells { get; }
}

We also need to keep track of which walls are present between cells in any particular maze. I've chosen to represent this using the four cardinal directions on a map, but another approach could be to store a wall as the pair of cells on either side of the wall.

public enum Direction { North, East, South, West }

public class Maze
{
    private readonly ImmutableDictionary<Cell, ImmutableList<Direction>> cellWalls;

    private Maze(
        Grid grid,
        ImmutableDictionary<Cell, ImmutableList<Direction>> cellWalls)
    {
        this.Grid = grid;
        this.cellWalls = cellWalls;
    }

    public Grid Grid { get; }

    public static Maze WithAllWalls(Grid grid)
    {
        var cellWalls = ImmutableDictionary<Cell, ImmutableList<Direction>>.Empty;

        foreach (var cell in grid.Cells)
        {
            cellWalls = cellWalls.Add(
                cell,
                [Direction.North, Direction.East, Direction.South, Direction.West]);
        }

        return new Maze(grid, cellWalls);
    }

    public bool WallExists(Cell cell, Direction direction) =>
        this.cellWalls[cell].Contains(direction);
}

Here I'm using a couple of types from the System.Collections.Immutable namespace. The idea behind these is that instead of (say) adding a new value to a list, you call a method which returns you a new list with that value added.

The Maze class works in the same way: you can't modify it, but you can call a method to give you a new maze with one wall removed.

public Maze RemoveWall(Cell cell, Direction direction)
{
    var adjacentCell = this.Grid.AdjacentCellOrNull(cell, direction);

    if (adjacentCell == null)
    {
        throw new InvalidOperationException(
            $"{direction} wall cannot be removed.");
    }

    return new Maze(
        this.Grid,
        this.cellWalls
            .SetItem(cell, this.cellWalls[cell].Remove(direction))
            .SetItem(
                adjacentCell,
                this.cellWalls[adjacentCell].Remove(direction.Opposite())));
}

To keep the set of walls consistent, we must remove the wall from the cells on both side of the wall.

The binary tree algorithm

Enough chat; you came here for mazes, so let's make one!

The binary tree algorithm is probably the simplest maze generation algorithm. For each cell in the grid, choose randomly between South and East, and remove the wall in that direction. That's it!

If you try and implement this yourself, you'll notice that there are a few edge cases (quite literally). Along the South edge, you can't remove the South wall because it's the edge of the grid, so you only have one option: to remove the East wall. Similarly, along the East edge, you can only remove the South wall. You then ignore the South-East cell entirely, as there are no walls you can remove.

Here's what you end up with!

Notice the unbroken corridors along the South and East sides of the maze. The binary tree algorithm unfortunately always generates mazes like this, but it's a good first start as we explore maze generation. Later in the series we'll generate mazes with less obvious biases.

Binary tree algorithm in code

The code for this demonstrates really nicely the idea of composing distributions to create new ones. All the functions shown below are entirely pure: they only depend on their inputs and produce no side-effects. The final result is not a maze, but a distribution which when sampled produces a maze.

Outline

public static IDistribution<Maze> MazeDist(Grid grid)
{
    IDistribution<Maze> mazeDist = InitialMazeDist(grid);

    foreach (var cell in grid.Cells)
    {
        mazeDist = mazeDist.SelectMany(m => NextStepDist(m, grid, cell));
    }

    return mazeDist;
}

Starting from an initial distribution, we loop through all the cells and update the distribution based on the different (random) outcomes that could occur at each step.

The use of SelectMany() here instead of Select() is crucial: it tells us that for a given maze so far, there could (in general) be multiple different ways for the maze to evolve. This corresponds with the fact that (in general) there are multiple possibilities for which wall we choose to remove.

Initial distribution

private static IDistribution<Maze> InitialMazeDist(Grid grid)
{
    var initialState = Maze.WithAllWalls(grid);

    return Singleton.New(initialState);
}

In future we'll see algorithms with a random initial state, but in this case there is only one way to start the process. For this we use the singleton distribution: a distribution which gives the same value every time it is sampled.

Updating the distribution

private static IDistribution<Maze> NextStepDist(Maze maze, Grid grid, Cell cell)
{
    var validDirections = GetValidDirections(cell, grid);

    if (UniformDistribution.TryCreate(validDirections, out var directionDist))
    {
        return directionDist.Select(dir => maze.RemoveWall(cell, dir));
    }
    else
    {
        return Singleton.New(maze);
    }
}

private static IEnumerable<Direction> GetValidDirections(Cell cell, Grid grid) =>
    new[] { Direction.South, Direction.East }.Where(dir => grid.CanRemoveWall(cell, dir));

The function above takes in a maze (the result so far) and returns a distribution describing the possible ways a maze could look after randomly removing the South or East wall. If it's possible to remove either (or both) of them, then we choose between them randomly (represented as a distribution, of course). If not, we leave the maze as-is.

Visualising the algorithm at work

We now have the ability to generate a maze image.

This is nice enough, but it would be even better to be able to see the algorithm at work, and generate a series of images showing the algorithm as it loops through the cells removing walls.

If we were coding this imperatively (as opposed to functionally), then we'd probably loop through the cells and generate the maze image at each step. However, because we're not allowing ourselves to sample any random values within the functional core, we can't do this.

If you're not used to coding functionally then this sort of problem can seem quite daunting. The solution (as is often the case) is to take a step back. What random value do we actually want? Or, put another way, for which type T do we want an IDistribution<T>?

We currently have a function returning an IDistribution<Maze>; that is, a random maze. In order to visualise the process we need not a random maze, but the random series of steps which got us there.

So, let's introduce a new type which can be used as the T in our IDistribution<T>. We need to store not just the current maze, but also the steps we took to get there.

record BinaryTreeState(
    Maze Initial, ImmutableList<BinaryTreeStep> Steps, Maze Current);

record BinaryTreeStep(Cell Cell, Maze Maze);

We then need to make a few changes to our algorithm. The code remains unchanged for both the initial distribution and how to move from one step to the next, but some changes are needed to the top-level function to compose the distributions differently.

private static IDistribution<BinaryTreeState> StateDist(Grid grid)
{
    var stateDist =
        from maze in InitialMazeDist(grid)
        select new BinaryTreeState(Initial: maze, Steps: [], Current: maze);

    foreach (var cell in grid.Cells)
    {
        stateDist = stateDist.SelectMany(state =>
            from maze in NextStepDist(state.Current, grid, cell)
            select state with
            {
                Steps = state.Steps.Add(new BinaryTreeStep(cell, maze)),
                Current = maze
            });
    }

    return stateDist;
}

The key difference here is within the loop. Once we've got the next step we don't just update the current value; we also add it (with the cell we've just processed) to the history.

Notice how immutability is really helping us here. If we were modifying the maze as we go then we wouldn't be able to keep track of the history, as the previous state would be lost.

If we sample from this distribution and generate a series of images (one for each step), we can turn them into an animation showing how we made our maze.

I don't know about you, but I could sit watching this for hours!

Conclusion

The binary tree algorithm is very easy to implement, but the mazes it generates are noticeably lop-sided. In the next post we'll implement an algorithm with less bias.