Maze Generation: Sidewinder algorithm

Posted by Jamis on February 03, 2011 @ 07:20 AM

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!

Posted in Under the Hood

Comments

Have something to add? Click here to leave a comment.

03 Feb 2011

1. Martijn said...

Funny, it looks really cool and the implementation is easy but it’s not really useful. Your posts are a cool read, though :)

04 Feb 2011

2. Macuyiko said...

Interesting post, as always. This page1 suggests the name comes from the fact that ‘Like binary tree, a sidewinder Maze can be solved deterministically without error from bottom to top, because at each row, there will always be exactly one passage leading up. A solution to a sidewinder Maze will never double back on itself or visit a row more than once, although it will “wind from side to side”.’ So as you traverse the rows, you’ll ‘wave’ from side to side.

You’re right however that there also exists an integer programming-based routing pattern approach called Sidewinder. The relevant paper is available online2, together with slides3. There is no direct link between the two algorithms, at least not as far as I can tell after a quick read through the otherwise interesting paper, although it can be noted that the routing problem as described in the paper also tends to require looking for maze-like patterns :).

I’m looking forward to more posts in this style, be it about mazes or other topics. Your code samples in particular are a nice contribution to anyone wanting to explore maze generation.

http://www.astrolog.org/labyrnth/algrithm.htm
http://www.eecs.umich.edu/~imarkov/pubs/conf/slip08-side.pdf
http://www.sliponline.org/SLIP08/presentations/5b.ppt

3. Jamis said...

@Macuyiko, the “Think Labyrinth” site inspired all of these maze articles I’ve written, and yet I managed to overlook that bit about a solution to a Sidewinder maze winding “from side to side”! Thank-you for pointing that out; that makes a lot of sense.

Thanks also for researching the other, routing-based algorithm. I had thought there was a chance of a connection there, because as you said, routing problems relate to mazes (both being associated with spanning trees).

And thank-you, especially, for the kind words!

06 Feb 2011

4. Tim said...

I stumbled upon your posts awhile ago and just decided to start implementing them in flash and adding in some ui to generate mazes from 3×3 cells to 100×100 cells. Very informative, I had no idea how mazes could be generated prior.

http://tim.ibocreative.com/flash/mazeGen/

5. Jamis said...

@Tim, thanks for the link to your maze implementations! I’m glad you’ve been inspired to work on these, it’s a lot of fun. :)