The Sidewinder Algorithm

Understanding the Sidewinder algorithm

There’s an algorithm called Sidewinder, which, though closely related to the Binary Tree algorithm, still manages to reduce the biases a little. Recall that Binary Tree chooses between north and east at every cell; Sidewinder, on the other hand, tries to group adjacent cells together before carving a passage north from one of them. Let's go ahead and grab another piece of paper, sketch another grid on it, and we’ll jump right in.

The Sidewinder algorithm explained and illustrated

Now, unlike Binary Tree, Sidewinder won't easily let us start carving anywhere we like. It has a strong preference for beginning in the western column, so that’s where we’ll start. In fact, we might as well start where we did before, in the southwest corner. We'll just flip a coin for us, as before. Once again, tails means “carve east,” but we’ll see that heads means something a little different this time around.

Let's start!

The algorithm can be better understood by looking at the steps and the given slides side by side.

1. Starting in that southwest corner, our first flip of the coin yields tails and tells us to erase the cell’s eastern wall. We then move to the next cell in that direction.

2. Once at this new cell, we flip the coin as before. It comes up tails again. We'll go ahead and erase the eastern wall and move to the next neighbor.

3. Once at this new cell, we again flip our coin, and we get heads. When the coin comes up heads, we look back on the path we just made, at that group of cells that were most recently joined by carving through walls. It's the three cells in a row that we just visited. We’ll call this cluster a run of cells. We’re going to randomly choose one cell from that run and then erase its northern wall, joining it with its northern neighbor. After that, we’re done with those three cells, and no further changes will be made to them. We’ll call this closing out the run.

Note: The run here involves just those three cells, and not the cell to the north that we linked to. This is important. That cell to the north has not yet been visited, and will be fair game when the algorithm moves on to that second row.

4. Next, we very intentionally do not remove the eastern wall (because that would change those closed-out cells) and instead, just move to the next cell over. When we’re all comfortable, the process begins again with a new run of cells, starting at our new position.

5. In our case, though, we’ve reached the eastern boundary of our grid, and no matter how much that coin of ours insists that we’re supposed to keep going east, we just can’t. The edge of our world is pretty immutable. When we find ourselves in that situation, we fall back to the same strategy we used with Binary Tree: we don’t bother flipping the coin. We'll treat that eastern boundary as an instant heads, and just close out the run. (Here, it’s easy, we have only one cell in the run, so we choose it and erase the northern wall).

The algorithm has been explained with illustrations in the slides below.