Binary Tree Algorithm

Binary Tree Algorithm

·

3 min read

Binary tree algorithm is a maze generation algorithm. It's very simple and efficient. Let's see how it works in this article.

To generate a maze, we first need to define a table like below.

Screen Shot 2022-08-08 at 15.38.26.png

As you can see, it is a normal table, with rows and columns. We can think each cell as the empty road in a maze and each edges as wall. Currently, there are all walls, we can't move to anywhere. What we will do now is to iterate all the cells of the table. For each iteration, we have 2 choices, either break the wall in the north, or break the wall in the left. We make the choice randomly.

Some special edge cases need to be handled. Say we are at the first row. We can't break the wall in the north now because that will break out the maze. Same thing happens when we are at the first column. So in the first row, we can only choose to break the wall in the west, and in the first column, we can only choose to break the wall in the north. And if we are at the first cell now, we can't do both.

So follow this procedure, 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:last-child {
            border-right: 1px solid black;
        }

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

        .left-wall {
            border-left: 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("left-wall");
                        break;
                    case 0:
                        item.classList.add("left-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);
        }

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

        function random(maze) {
            for (let i = 0; i < maze.length; i++) {
                for (let j = 0; j < maze[i].length; j++) {
                    if (i === 0 && j === 0) {
                        maze[i][j] = [1, 1];
                    } else if (i === 0) {
                        maze[i][j] = [0, 1];
                    } else if (j === 0) {
                        maze[i][j] = [1, 0];
                    } else {
                        if (Math.random() < 0.5) {
                            maze[i][j] = [1, 0];
                        } else {
                            maze[i][j] = [0, 1];
                        }
                    }
                }
            }
        }

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

    </script>
</body>

</html>

Run the code in the browser, we can generate a random maze like below.

Screen Shot 2022-08-08 at 15.29.12.png