ProcGen Fun 5: The Sidewinder algorithm

[List of posts | source code for this post]

In this post I'll introduce you to the Sidewinder algorithm for maze generation.

The algorithm

The main problem with the Binary Tree algorithm (which we looked at last time) was the obvious bias in its output: each maze generated had an unbroken corridor along the South and East edges. Sidewinder is a modification of Binary Tree which aims to remove some of this bias.

Last time we ran through each cell and randomly chose to remove either the South or East wall. This time round we'll do the same, except that when we remove the South wall we won't necessarily do it from the current cell; instead we'll look back along the connected run of cells we've just made and pick one at random.

They say a picture is worth a thousand words, so let's have a look at an example. We start with the North-West cell in an empty grid.

For each cell, we need to randomly choose either the South or East wall to remove. For this first one, let's say we choose East.

We then move onto the next cell. As we go let's keep track of the current run so we know our options when we eventually want to remove a wall to the South.

Our virtual coin toss comes up East again. Let's remove the East wall and move onto the next cell.

This time, our random choice comes up South. Rather than removing the South wall from the current cell, we can choose from any of the three in the current run. Let's choose the first one.

We repeat this process all the way along the row, and then repeat for each row. Sometimes we'll end up with a large run; for example, this one here has nine cells in it.

Sometimes we only end up with one cell in the run, as in the example below. In this case we only have one choice: to remove the South wall from that cell.

Eventually we make our way to the end of the grid, and here's what we end up with!

Because removing a South wall is done randomly, we don't end up with a corridor along the Eastern edge of the maze, which is nice to see! However we still end up with an unbroken corridor along the South of the maze, so we've still got some bias.

The code

To approach the implementation, let's break it down and consider each row in turn. As we process each cell in a row we'll need to keep track of the current run as well as the maze so far, so let's introduce a type for that.

private record RowState(Maze Maze, ImmutableList<Cell> Run);

Next we need to be able to choose between the two valid actions at any given point. Let's use an enum for that.

private enum Action { RemoveEastWall, CloseRun }

For any cell in the grid, we need to know which actions are available to us. We can remove the East wall if and only if there is a cell to the East; we can close the current run by removing a South wall if and only if there are cells to the South.

private static IEnumerable<Action> GetValidActions(Grid grid, Cell cell)
{
    if (grid.AdjacentCellExists(cell, Direction.East))
    {
        yield return Action.RemoveEastWall;
    }

    if (grid.AdjacentCellExists(cell, Direction.South))
    {
        yield return Action.CloseRun;
    }
}

Next we can add functions for applying the chosen action to the current state. Moving Eastwards is a deterministic process, so the corresponding function returns the subsequent state value. Closing the current run is a stochastic process (we randomly choose a cell whose South wall to remove), so the corresponding function returns a distribution. I really like being able to communicate whether a method is deterministic or stochastic based on its return value!

private static IDistribution<RowState> ApplyAction(
    RowState rowState, Cell cell, Action action) =>
    action switch
    {
        Action.RemoveEastWall => Singleton.New(RemoveEastWall(rowState, cell)),
        Action.CloseRun => CloseRunDist(rowState, cell),
        _ => throw new ArgumentOutOfRangeException(nameof(action), action, null)
    };

private static RowState RemoveEastWall(
    RowState rowState, Cell cell) =>
    new RowState(
        Maze: rowState.Maze.RemoveWall(cell, Direction.East),
        Run: rowState.Run.Add(cell));

private static IDistribution<RowState> CloseRunDist(
    RowState rowState, Cell cell) =>
    from cellToRemoveSouthWallFrom
        in UniformDistribution.Create(rowState.Run.Add(cell))
    select new RowState(
        Maze: rowState.Maze.RemoveWall(cellToRemoveSouthWallFrom, Direction.South),
        Run: []);

Now we have the required building blocks, we can calculate the distribution resulting from processing a single cell. We need to cope with the case when there are no valid actions; that is, there's nothing we can do in the South-East cell.

private static IDistribution<RowState> CellDist(RowState rowState, Grid grid, Cell cell)
{
    var validActions = GetValidActions(grid, cell);
    if (UniformDistribution.TryCreate(validActions, out var actionDist))
    {
        return
            from action in actionDist
            from newRowState in ApplyAction(rowState, cell, action)
            select newRowState;
    }
    else
    {
        return Singleton.New(rowState with { Run = rowState.Run.Add(cell) });
    }
}

For a given row we can apply the cell distribution multiple times.

private static IDistribution<Maze> RowDist(Maze maze, Grid grid, int y)
{
    var initialState = new RowState(maze, Run: []);

    IDistribution<RowState> stateDist = Singleton.New(initialState);

    foreach (var x in grid.ColumnIndices)
    {
        stateDist = stateDist.SelectMany(s => CellDist(s, grid, new Cell(x, y)));
    }

    return stateDist.Select(s => s.Maze);
}

And finally we can loop through the rows to get the final maze distribution!

public static IDistribution<Maze> MazeDist(Grid grid)
{
    var initialMaze = Maze.WithAllWalls(grid);

    IDistribution<Maze> mazeDist = Singleton.New(initialMaze);

    foreach (var y in grid.RowIndices)
    {
        mazeDist = mazeDist.SelectMany(m => RowDist(m, grid, y));
    }

    return mazeDist;
}

There's quite a lot of code here. However it's broken down into many small functions, each of which make sense in their own right. I like how this makes it easier to understand the whole algorithm.

Maintaining the history

As with the Binary Tree algorithm, if we want to make an animation showing how the maze was created (and I do, because it looks cool), then we need to introduce a type to keep track of the steps as we go.

I won't go into too much detail here, but the interesting thing with this algorithm is that each step of the algorithm generates two frames of the animation: we first add the current cell to the run, and then we remove one of the walls bounding the run. This means we need to update the RowState type to include the run before and after a wall was removed.

record RowState(
    Maze Maze,
    ImmutableList<Cell> RunBeforeWallRemoved,
    ImmutableList<Cell> Run);

If you want to see the full details, have a look at the source code.

Results

Here's our example maze from earlier, along with an animation of the steps it took to get there.

I've updated the playground website with support for the Sidewinder algorithm if you'd like to have a go yourself!

Up next

The bias in this algorithm is still pretty obvious: we always get an unbroken corridor along the bottom of the maze. In the next post we'll explore an algorithm with a less obvious bias, which produces more natural-looking mazes (and an even better animation!).