In Manual maze, we define the block data structure and use it to draw a maze. If you can generate the block data automatically, the maze will have a different path. There are many maze algorithms. Here, I'll introduce the easiest binary tree algorithm.

Binary tree algorithm

The concept behind binary tree algorithm is easy, but it also has an apparent defect which we'll see soon. However, it helps us to understand why we can generate a maze automatically. The generated maze is a perfect maze, which means it has exactly one path between any two blocks.

Take a 4x4 maze for example. First, draw a maze with no wall carved. We start from the lower-left block.

Now, let's flip a coin. If it's “heads”, we carve the right wall, otherwise, the upper wall. Then, we can move to the next block. For example, we get “tails” first.

It doesn't matter which one is the next block. Binary tree algorithm doesn't care about it. For convenience, we always move to the right block if possible. Suppose we get “heads” and “tails” after two coin flipping. The status of the maze is:

We've reached the rightmost column. What should we do now? You cannot carve the right wall if it's not an exit. For the rightmost column, we cut their upper walls directly without flipping a coin.

Similarly, we cannot remove the upper wall of the uppermost row. We directly cut their right walls.

Now, let's deal with the remaining blocks. We back to the (1, 2) block first.

Suppose we get “heads”, move to the right block, get “tails”, move to the right block, and then get “tails”.

There's still one row we have to carve. Let's start from the leftmost block. This time, we get three “heads”.

Ya, we create a maze!

Is it a binary tree?

We can draw paths on the generated maze.

Now remove all walls and rotate the paths 45 degrees.

It's a binary tree, right? Every time we decide to carve a wall, we select a parent node. If you look inversely, a parent node has at most two child nodes. It's undoubtedly a binary tree, and the upper-left block is the root. In a binary tree, any two nodes have exactly one path. No matter what maze algorithm, it'll form a tree structure if it generates a perfect maze. There's no loop on these mazes.

And you might find that binary tree algorithm has a bias. Suppose you start from the root, you can reach any child node if you only go left or down.

Inversely, suppose that the left-lower block is the starting point and the upper-right block is an exit, you can easily find a way through the maze by only going right or up.

We can add more rules or randoms to improve the bias. For example, I'll show how to walk randomly and carve the wall we encounter in the later doument.

Different algorithms will bring different mazes. If you are interested in maze algorithms, I suggest the book Mazes for Programmers.

Implementing binary tree algorithm

In OpenSCAD, we define a function to simulate coin flipping first.

function flip_coin() = round(rands(0, 1, 1)[0]) + 1;

The rands function is a built-in function of OpenSCAD. You can pass the random number range and the number of random numbers to return a vector. For example, rands(n, m, x) returns a vector containing x random numbers range from n to m. Therefore, rands(0, 1, 1)[0] generate a random number between 0 and 1.

The built-in round function returns the closest integer. Thus, round(rands(0, 1, 1)[0]) gets either 1 or 0. We add 1 to it so flip_coin returns either 1 or 2, which correspond with the wall constant UP_WALL or RIGHT_WALL respectively.

Then, we flip a coin for each block. Remember, you don't have to flip for the rightmost column and the uppermost row.

function binary_tree_block(x, y, rows, columns) = 
    y == rows ? block_data(x, y, 1) : (        // the uppermost row
        x == columns ? block_data(x, y, 2) :   // the rightmost column
            block_data(x, y, flip_coin())      // flip a coin
    );

We go through the maze from left to right and lower to upper to generate all blocks.

function binary_tree_algorithm(rows, columns) = 
    [
        for(y = [1:rows]) 
            for(x = [1:columns]) 
                binary_tree_block(x, y, rows, columns)
    ];

The following list all code for generating a maze. We don't change any code developed in Manual maze for representation and only use binary tree algorithm to generate the block data referred by maze_blocks.

module line(point1, point2, width = 1, cap_round = true) {
    angle = 90 - atan((point2[1] - point1[1]) / (point2[0] - point1[0]));
    offset_x = 0.5 * width * cos(angle);
    offset_y = 0.5 * width * sin(angle);

    offset1 = [-offset_x, offset_y];
    offset2 = [offset_x, -offset_y];

    if(cap_round) {
        translate(point1) circle(d = width, $fn = 24);
        translate(point2) circle(d = width, $fn = 24);
    }

    polygon(points=[
        point1 + offset1, point2 + offset1,  
        point2 + offset2, point1 + offset2
    ]);
}

module polyline(points, width = 1) {
    module polyline_inner(points, index) {
        if(index < len(points)) {
            line(points[index - 1], points[index], width);
            polyline_inner(points, index + 1);
        }
    }

    polyline_inner(points, 1);
}

// Wall constants

NO_WALL = 0;    
UP_WALL = 1;  
RIGHT_WALL = 2;  
UP_RIGHT_WALL = 3; 

function block_data(x, y, wall_type) = [x, y, wall_type];
function get_x(block_data) = block_data[0];
function get_y(block_data) = block_data[1];
function get_wall_type(block_data) = block_data[2];

module draw_block(wall_type, block_width, wall_thickness) {
    if(wall_type == UP_WALL || wall_type == UP_RIGHT_WALL) {
        // the upper wall
        polyline(
            [[0, block_width], [block_width, block_width]], wall_thickness
        ); 
    }

    if(wall_type == RIGHT_WALL || wall_type == UP_RIGHT_WALL) {
        // the right wall
        polyline(
            [[block_width, block_width], [block_width, 0]], wall_thickness
        ); 
    }
}

module draw_maze(rows, columns, blocks, block_width, wall_thickness) {
    for(block = blocks) {
        // move the block to its correspond position
        translate([get_x(block) - 1, get_y(block) - 1] * block_width) 
            draw_block(
                get_wall_type(block), 
                block_width, 
                wall_thickness
            );
    }

    // the lowermost wall
    polyline(
        [[0, 0], [block_width * columns, 0]], 
        wall_thickness);
    // the leftmost wall
    polyline(
        [[0, block_width], [0, block_width * rows]], 
        wall_thickness);
} 

block_width = 3;
wall_thickness = 1;
maze_rows = 10;
maze_columns = 10; 

function flip_coin() = round(rands(0, 1, 1)[0]) + 1;

function binary_tree_block(x, y, rows, columns) = 
    y == rows ? block_data(x, y, 1) : (        // the uppermost row
        x == columns ? block_data(x, y, 2) :   // the rightmost column
            block_data(x, y, flip_coin())      // flip a coin
    );

function binary_tree_algorithm(rows, columns) = 
    [
        for(y = [1:rows]) 
            for(x = [1:columns]) 
                binary_tree_block(x, y, rows, columns)
    ];

maze_blocks = binary_tree_algorithm(maze_rows, maze_columns);

draw_maze(
    maze_rows, 
    maze_columns, 
    maze_blocks, 
    block_width, 
    wall_thickness
);

Now, you can change the value of maze_rows or maze_columns to generate a bigger maze. If your friends don't know binary tree algorithm, it should be enough to deceive them :p