The Buckblog

Last of the (eleven!) maze algorithms on my list is the Sidewinder algorithm. With a name like that, it’s got to be cool, right?

Well, possibly. It’s got its problems, but it’s quick and easy to implement, and allows arbitrarily tall mazes. It’s closely related to the Binary Tree algorithm, but manages to get away with only one side being spanned by a passage, instead of two.

In a nutshell, it goes like this:

1. Work through the grid row-wise, starting with the cell at 0,0. Initialize the “run” set to be empty.
2. Add the current cell to the “run” set.
3. For the current cell, randomly decide whether to carve east or not.
4. If a passage was carved, make the new cell the current cell and repeat steps 2-4.
5. If a passage was not carved, choose any one of the cells in the run set and carve a passage north. Then empty the run set, set the next cell in the row to be the current cell, and repeat steps 2-5.
6. Continue until all rows have been processed.

So, while it’s related to the Binary Tree algorithm, it’s a bit more complicated. However, words don’t do it justice; it really is a lot more straightforward than it sounds.

Let’s walk through an example.

An example

I’ll use a 4×4 grid, and I’ll move fairly quickly, so pay attention. (You in the back! Eyes to the front!)

I’ll start with the first (top) row, although the algorithm works just fine if you start with the last one and work up. Starting at the top lets us get the one special case out of the way: the entire first row must be a single passage (because you can’t carve north from the northernmost row):

There, we’ve got that done with. Now, let’s get to the interesting bit. Let’s say we manage to carve 3/4 of the way across the row before we decide (randomly and arbitrarily) not to carve eastward:

The cells in red are the current “run set”. Since we’ve ended the current run of horizontal cells, we now choose one of these cells at random, and carve a passage north. Thus:

Then we clear out the run set:

Make the next cell the current cell:

And try to decide whether to carve eastward or not. However, at this point, we can’t carve east. It would take us outside the bounds of the maze, which is not allowed. So we have to end the run there, and choose one of the cells in the set to carve north from. The decision is out of our hands: with only a single cell in the set, we have to choose it. So we carve north:

Then we start the next row. Notice how each row is independent of the row preceding it, much like Eller’s algorithm.

For the next row, we decide immediately that we want to stop carving east on the very first cell:

So we stop, choose a cell from the run set (easy) and carve north:

Continuing, we connect the next two cells:

Randomly choose one of them to carve north from:

And continue:

And since we’re at the end of the row, we’re again forced to stop and carve north:

For the last row, let’s say we connect the first two cells:

Carve north and clear the set:

Then connect the last two cells:

And finish it off by adding a final northward connection:

And that’s our maze, courtesty of the Sidewinder.

Feel free to play with the following demos, to get a feel for how the Sidewinder works on larger grids. The single corridor spanning the top row is hard to miss, but see if you can spot any other properties of the algorithm.

Implementation

All this talk of “run sets” might make you think you actually need to use a set. Well, you can, sure, if you want to. No one’s going to stop you, right? But if you notice that each set consists of consecutive cells, you can take a short-cut and just keep track of the cell that started the run. The “set” is then implied as the sequence of cells between the start of the run, and the current cell.

Aside from that, the algorithm has very few surprises. As you’d expect you need to iterate over each row:

1
2
3
4

height.times do |y|
  run_start = 0
  # ...
end

At the start of each row I initialize the beginning of the current run to the first cell.

Then, within that loop, I iterate over each cell in the current row:

1
2
3

width.times do |x|
  # ...
end

Within that loop is where the magic really happens. There are basically two conditions:

1
2
3
4
5

if y > 0 && (x+1 == width || rand(2) == 0)
  # end current run and carve north
elsif x+1 < width
  # carve east
end

Remember how the first row is always a single corridor? That “y > 0” guard prevents us from ever ending the current run if we’re on the first row. Similarly, the “elsif” clause prevents us from carving east if we’re at the last cell in a row.

The second condition in the first clause makes sure that we always end the current run at the end of the current row (x+1 == width), but also allows us to randomly end the current run (rand(2) == 0).

Ending a run requires us to randomly choose a cell from the current run set, and carve north from it:

1
2
3
4

cell = run_start + rand(x - run_start + 1)
grid[y][cell] |= N
grid[y-1][cell] |= S
run_start = x+1

We also reset the run set to begin at the next cell.

The last bit of code, from the elsif clause, is simple: carving east is merely setting a bit:

1
2

grid[y][x] |= E
grid[y][x+1] |= W

And that’s all there is to it. Like I said, it’s easier to implement than describe.

Conclusion

With a name like “Sidewinder” you can’t help but wish the algorithm was cooler than it is. I’m actually not sure where the name comes from; a Google search reveals a routing algorithm with the same name, but I wasn’t able to find any solid information to compare with the one I describe here. (If anyone has more information, I’m definitely curious.)

The Sidewinder’s greatest “flaw”, if it can be called that, is that it is all but trivial to start at the bottom row of the maze, and work your way to the top. Any maze generated by the Sidewinder algorithm will never have any north-facing dead-ends, which means you can never get stuck when moving from south to north. (This is similar to the Binary Tree algorithm, which will never have any dead-ends in the direction of its bias.) And for quickly generating arbitrarily tall mazes, Eller’s algorithm is probably better (with fewer drawbacks), but is harder to implement.

Would I actually use the Sidewinder algorithm for anything? I’m not sure. I hesitate to say “never”, but I certainly can’t think of anything I’d use it for that another algorithm wouldn’t do better! But it was fun to implement, so it has entertainment value, if nothing else.

Give it a try yourself and share how it goes! For reference, my complete implementation follows:

Enjoy!