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.
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?
It looks easy. We can arrange several square frames, right?
In fact, you don't need square frames. Just use the following model.
Of course, it will have no left side and down side.
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.
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.
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.