Manual maze


After starting my tour on 3D designs with code, I decided to use OpenSCAD, and one thing I wanted to challenge is generating a maze. For reference, I tried to look for the code written in OpenSCAD but cannot find one. After attempting for a period, I eventually come up with my first maze.

Maze generator, pure OpenSCAD

Strictly speaking, maze algorithms are not hard. You can find different maze algorithms on the internet. Thingiverse has several maze generators; however, none of them is written in pure OpenSCAD. Several solutions use other languages to generating the maze data, and then translate them into OpenSCAD code. They are not what I want.

I think one of the reasons is, OpenSCAD is Functional programming. When I tried to implement a maze at the first time, I didn't notice the paradigm and suffered for it.

In short, you have to be skilled at Functional programming to avoid running into snags everywhere when implementing a maze. That's why I put the maze topic last. I suppose that you've been familar with Functional programming though the previous documents.

The walls

Before designing a maze, think about a question. How to create the pattern below?

Manual maze

It looks easy. We can arrange several square frames, right?

Manual maze

In fact, you don't need square frames. Just use the following model.

Manual maze

Of course, it will have no left side and down side.

Manual maze

It's not a big problem. Just draw two lines at the left side and the lower side. The point here is, we can treat every block of a maze as being made of a upper wall and a right wall. If you can go right to the next block, the current block has no right wall. Being able to go up means no upper wall. If the left block is walkable, the left block has no right wall. The lower block has no upper wall if you can go down.

Therefore, if a maze has blocks such as:

// upper: the block has a upper wall
// right: the block has a right wall
// no   : the block has no wall

upper, upper          , upper, upper
right, upper and right, upper, right
no   , right          , right, right
upper, upper          , right, right

You can draw the following model according to it.

Manual maze

Here, we use the lower-left block as a starting point and the upper-right block as an exiting point. After adding two lines at the left side and the lower side, we have a easy maze.

Manual maze

Block data

Once we know how to construct maze walls, we can define the data structure of a block. We use the xy plane, and the lower-left corner of a maze is located at the origin of the coordinate system of OpenSCAD. We index the lower-left block as (1, 1). Its right blocks are indexed as (2, 1), (3, 1) and (4, 1). The blocks of the upper row are indexed as (1, 2), (2, 2), (3, 2) and (4, 2). The remaining rows follow the same rule.

Besides the block index, we have to record the wall type. For clearness, we define some constant variables first.

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

Thus, we use (x, y, wall_type) as the data structure of a block. In OpenSCAD, we can use a vector to define it. For example, for a 4x4 maze, we can use the code below to represent the block data.

// [x, y, wall_type]
maze_blocks =  [
    [1, 4, 1], [2, 4, 1], [3, 4, 1], [4, 4, 1], 
    [1, 3, 2], [2, 3, 3], [3, 3, 1], [4, 3, 2], 
    [1, 2, 0], [2, 2, 2], [3, 2, 2], [4, 2, 2], 
    [1, 1, 1], [2, 1, 1], [3, 1, 2], [4, 1, 2]
];

You might think that why don't we use the following data?

maze_blocks =  [
    [1, 1, 1, 1], 
    [2, 3, 1, 2], 
    [0, 2, 2, 2], 
    [1, 1, 2, 2]
];

In this case, the wall type of maze_blocks[0][0] is 1, that is UP_WALL. Isn't it shorter than the previous?

In fact, you can use it if you want. I decide to use (x, y, wall_type) because I want to coincide with the directions of the x-axis and the y-axis. If I take the above solution, maze_blocks[0] is the uppermost row and maze_blocks[3] is the lowest row. It will differ from the directions I want.

You might prefer the coordinate system used by output devices such as a screen, window, or a printer. That is, the x coordinate increases to the right, the y coordinate increases downward, and the top-left block is (0, 0). If it's your choice, the above data structure is ok.

In fact, my first Maze generator uses it, too. However, the coordinate system of OpenSCAD is different from output devices such as a screen. Changing between two systems sometimes confuses me. That's why I don't take the above data structure here.

There are other benefits, too. As you will see in the later document, we don't have to change much code when we expand the maze to a random maze. I'll add one field to record whether we've visited a block. That is [x, y, wall_type, visited].

In short, the data structure I use here is flexible and consistent with the coordinate system of OpenSCAD. For convenience, we define some helper functions for constructing the block data.

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];

Drawing a maze

The wall is a line. We can use the polyline module developed in Line to draw a line. The first thing is defining a module to create only a block.

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
        ); 
    }
}

Then, draw the maze according to the block data.

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 lower wall
    polyline(
        [[0, 0], [block_width * columns, 0]], 
        wall_thickness);
    // the left wall
    polyline(
        [[0, block_width], [0, block_width * rows]], 
        wall_thickness);
}

Why do I subtract one from the (x, y) of a block respectively? I want the lower-left corner of the maze is the origin of the xy plane.

The following is all code used to draw a 4x4 maze according to the block data listed above.

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 = 4;
maze_columns = 4;

// [x, y, wall_type]
maze_blocks =  [
    [1, 4, 1], [2, 4, 1], [3, 4, 1], [4, 4, 1], 
    [1, 3, 2], [2, 3, 3], [3, 3, 1], [4, 3, 2], 
    [1, 2, 0], [2, 2, 2], [3, 2, 2], [4, 2, 2], 
    [1, 1, 1], [2, 1, 1], [3, 1, 2], [4, 1, 2]
];


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

Of course, we create the block data manually here. However, do you notice that? We separate the data from the representation. That is, if you can generate the block data randomly, you'll have a random maze. It's what I'll talk lately.

Because we separate the data from the representation, you can change the implementation of the draw_maze module and then you'll have a different maze. That's why I have so many mazes on Thingiverse.