The Sidewinder Algorithm

The Sidewinder Algorithm

·

3 min read

In the previous article, I talked about how to generate a maze by Binary Tree Algorithm. In this article, let's learn another algorithm called the sidewinder algorithm to generate a maze.

Remember that in binary tree algorithm, we iterate every cell and choose to break the wall on west or north randomly. For the sidewinder algorithm, we also need to iterate every cell, but with a different way for breaking wall.

For one normal iteration, we also have 2 choices. The first one is to break the wall on the east. Suppose we have broke the walls on the east for 2 consecutive steps. Then we should have a horizontal cube with length of 3 cells. Then we move east for the next cell and flip the coins again. This time we need to take the second choice. The second choice is, choose a cell from the cube randomly, and break the wall on the north. And this time, current cell's east wall is retained.

So only this 2 steps, a little complicated than the binary tree algorithm. Below code snippet should show the process more clearly.

// for every step
// break east or choose one to break north
if (Math.random() < 0.5) {
    maze[i][j] = [0, 1];
} else {
    // choose an index
    const index = chooseNorthIndex(start, j);
    // break north
    maze[i][index][1] = 0;
    // retain east
    maze[i][j][0] = 1;
    // start stands for the start index of the cube
    start = j + 1;
}

OK, still there are edge cases need to handle. If we are at the first row, we shouldn't break the wall on the north and if we are the the last column, we should break the wall on the east.

So, than's all. Let do it in code.

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        .row {
            display: flex;
        }

        .item {
            box-sizing: border-box;
            width: 10px;
            height: 10px;
        }

        .item:first-child {
            border-left: 1px solid black;
        }

        .row:last-child .item {
            border-bottom: 1px solid black;
        }

        .east-wall {
            border-right: 1px solid black;
        }

        .north-wall {
            border-top: 1px solid black;
        }
    </style>
</head>

<body>
    <div id="root"></div>

    <script>

        function draw(maze) {
            function createItem(state) {
                const item = document.createElement("div");
                item.classList.add("item");
                switch (state[0]) {
                    case 1:
                        item.classList.add("east-wall");
                        break;
                    case 0:
                        item.classList.add("east-pass");
                        break;
                }
                switch (state[1]) {
                    case 1:
                        item.classList.add("north-wall");
                        break;
                    case 0:
                        item.classList.add("north-pass");
                        break;
                }
                return item;
            }

            const container = document.createElement("div");

            for (const row of maze) {
                const rowEle = document.createElement("div");
                rowEle.classList.add("row");

                for (const state of row) {
                    rowEle.appendChild(createItem(state));
                }

                container.appendChild(rowEle);
            }

            root.innerHTML = "";
            root.appendChild(container);
        }

        const maze = init(42, 72);
        random(maze);
        draw(maze);

        function init(width, heigth) {
            const maze = Array.from({ length: width }, _ => {
                // cell states as [x, y]
                // x for if east has wall
                // y for if north has wall
                return Array.from({ length: heigth }, _ => [1, 1]);
            });
            return maze;
        }

        function random(maze) {
            function chooseNorthIndex(start, current) {
                const range = current - start + 1;
                const index = Math.floor(Math.random() * range) + start;
                return index;
            }

            for (let i = 0; i < maze.length; i++) {
                let start = 0;
                for (let j = 0; j < maze[i].length; j++) {
                    if (i === 0 && j === maze[i].length - 1) {
                        // northeast, all wall
                        maze[i][j] = [1, 1];
                    } else if (i === 0) {
                        // first row, north wall, east pass
                        maze[i][j] = [0, 1];
                    } else if (j === maze[i].length - 1) {
                        // last column, choose
                        const index = chooseNorthIndex(start, j);
                        maze[i][index][1] = 0;
                        maze[i][j][0] = 1;
                        start = j + 1;
                    } else {
                        // for every step
                        // move forward or choose break north
                        if (Math.random() < 0.5) {
                            maze[i][j] = [0, 1];
                        } else {
                            const index = chooseNorthIndex(start, j);
                            maze[i][index][1] = 0;
                            maze[i][j][0] = 1;
                            start = j + 1;
                        }
                    }
                }
            }
        }

    </script>
</body>

</html>

So with this code, we can generate mazes like below.

Screen Shot 2022-08-09 at 17.16.05.png