In Binary tree algorithm, I introduced the basic ideas about generating maze automatically. If you are not familiar with Functional programming, binary tree algorithm has another benefit. Because it doesn't care about the visiting sequence, you can just use list comprehensions to step the maze blocks.
But, once you want to improve the bias, you'll face problems such as tracking and changing the visited blocks.
If you want to walk randomly, you have to carve walls such as the way mentioned in Manual maze. That is, 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.
Then, you have to trace and change the wall block for every block.
Thus, you have to change you block data under the paradigm of Functional programming even you cannot re-assign a value to a variable or modify the element of a vector in OpenSCAD. It sounds impossible; however, it's just because you think from the aspect of imperative programming languages.
Defining fundamental functions
Let's do it in action. We challenge random mazes directly. It might be hard for you. Even if I am familiar with OpenSCAD, I still have to think and implement step by step. It took me about 3 hours to come up all the code below. I'll explain each part of them for you. But you still have to think by yourself and get your hand dirty. Knowing and doing are two different things, right?
As mentioned before, we have to track whether we've visited a block. That is because repeated visiting might carve a necessary wall and cause loops in a maze, not a perfect maze anymore. It's not what we want.
Therefore, we add a visited field to our block data.
function block_data(x, y, wall_type, visited) = [x, y, wall_type, visited];
The initial status of a block data has UP_RIGHT_WALL and the false value for the visited field. We define a starting_maze function to do initialization of a maze. For simplification, the exit of the maze is always the upper-right block.
// initialize the status of a maze
function starting_maze(rows, columns) = [
for(y = [1:rows])
for(x = [1:columns])
block_data(
x, y,
// all blocks have UP_RIGHT_WALL except the exit
y == rows && x == columns ? UP_WALL : UP_RIGHT_WALL,
// false is unvisited
false
)
];
We'll store all our block data in a vector. To check whether we've visited a block (x, y), we need to know the index of the block data in the vector.
// find the index of block (x, y)
function indexOf(x, y, maze, i = 0) =
i > len(maze) ? -1 : (
[get_x(maze[i]), get_y(maze[i])] == [x, y] ? i :
indexOf(x, y, maze, i + 1)
);
Yes, it uses recursion; however, not difficult. If the index is out of bound, we return -1 for not found. While indexing, we check whether the values of the parameter x and y are the same as (x, y) of the block data. If they are the same, we return the i value, otherwise, invoke indexOf again.
Recursion is not the main point. The point is that you have to divide and conquer. The paradigm of Functional programming is just a way to force you to divide and conquer. It's harder to write a lump of code, which is common in imperative languages. (Of course, it's still possible to do that if you want. No one can stop you! )
Once we have the indexOf function, it's easy to check whether we've visited a block.
// check whether we've visited the block (x, y)
function visited(x, y, maze) = maze[indexOf(x, y, maze)][3];
We have to check whether a block is visitable.
// is (x, y) visitable?
function visitable(x, y, maze, rows, columns) =
y > 0 && y <= rows && // y is not out of bound
x > 0 && x <= columns && // x is not out of bound
!visited(x, y, maze); // visited or not
Using the set_visited function to set the block (x, y) as being visited. It returns a new block data.
// we've visited (x, y)
function set_visited(x, y, maze) = [
for(b = maze)
[x, y] == [get_x(b), get_y(b)] ?
[x, y, get_wall_type(b), true] : b
];
Now, we have to decide which direction we should walk through. Even though you can use rands to generate numbers 0 to 3 randomly, the rands function might produce a number sequence such as 0, 1, 1, 1, 2, 3, etc. That is, you migh try one direction more than two times. For efficiency, I hard code all permutations for 0 to 3.
If we hard code these numbers, is it still random? Yes, I randomly chose one vector from them.
// 0（right）、1（up）、2（left）、3（down）
function rand_dirs() =
[
[0, 1, 2, 3],
[0, 1, 3, 2],
[0, 2, 1, 3],
[0, 2, 3, 1],
[0, 3, 1, 2],
[0, 3, 2, 1],
[1, 0, 2, 3],
[1, 0, 3, 2],
[1, 2, 0, 3],
[1, 2, 3, 0],
[1, 3, 0, 2],
[1, 3, 2, 0],
[2, 0, 1, 3],
[2, 0, 3, 1],
[2, 1, 0, 3],
[2, 1, 3, 0],
[2, 3, 0, 1],
[2, 3, 1, 0],
[3, 0, 1, 2],
[3, 0, 2, 1],
[3, 1, 0, 2],
[3, 1, 2, 0],
[3, 2, 0, 1],
[3, 2, 1, 0]
][round(rands(0, 24, 1)[0])];
We can read the element of the returned vector sequentially. Thus, we'll visit each direction only once.
The next_x and next_y are helper functions used to get the next x and y respectively.
// given the `x` value and a direction, return the `x` value of the next block
function next_x(x, dir) = x + [1, 0, -1, 0][dir];
// given the `x` value and a direction, return the `x` value of the next block
function next_y(y, dir) = y + [0, 1, 0, -1][dir];
After defining these essential functions, we can move on to the next stage: creating the block data of the maze.
Carving walls
Suppose we are at the (x, y) block, its right block is visitable and we go right, then we have to carve the right wall of (x, y) if it the current block has a right wall. Because the current block has one of the four wall types, there were four conditions we have to check, right?
For example, the current block has UP_WALL so we don't have to do anything. If it has RIGHT_WALL, we change the wall type to NO_WALL. The next status is UP_WALL if the original wall type is UP_RIGHT_WALL.
Though it's right, we don't have to. It's also inefficiency. Think about it. The initial status of all blocks is UP_RIGHT_WALL. If a block doesn't have a right wall, we must remove it before. That is, we ever went from the left to right block, so the right block must not be visitable. In this situation, we don't have to check UP_WALL and NO_WALL; only have to check whether it's UP_RIGHT_WALL. If it is, the next status is UP_WALL. If not, the current type is RIGHT, so the next status is NO_WALL.
// go right, remove the right wall
function go_right_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x, y] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x, y, UP_WALL, visited(x, y, maze)] :
[x, y, NO_WALL, visited(x, y, maze)]
) : b
];
Similarly, suppose the upper block is visitable, and we go up, we only have to check whether the current type is UP_RIGHT_WALL.
// go up, remove the upper wall
function go_up_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x, y] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x, y, RIGHT_WALL, visited(x, y, maze)] :
[x, y, NO_WALL, visited(x, y, maze)]
) : b
];
When going left or down, remember, we don't remove the wall of the current block; we remove the wall of the next block.
// go left, remove the right wall of the left block
function go_left_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x - 1, y] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x - 1, y, UP_WALL, visited(x - 1, y, maze)] :
[x - 1, y, NO_WALL, visited(x - 1, y, maze)]
) : b
];
// go down, remove the upper wall of the lower block
function go_down_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x, y - 1] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x, y - 1, RIGHT_WALL, visited(x, y - 1, maze)] :
[x, y - 1, NO_WALL, visited(x, y - 1, maze)]
) : b
];
Because OpenSCAD doesn't allow if...else in functions, we use the ternary operator ?: instead. Some programming languages view if...else as an expression. It'll be helpful to readability if OpenSCAD can suppose it.
From another viewpoint, it might be intentional for OpenSCAD to suppose only the ?: operator. It's diffcult to write a nested structure so force you to divide the task into smaller functions. Of course, it's still possible to write a nested and ugly structure, it's up to you.
Now, we can try our neighbors.
// 0（right）、1（up）、2（left）、3（down）
function try_block(dir, x, y, maze, rows, columns) =
dir == 0 ? go_right_from(x, y, maze) : (
dir == 1 ? go_up_from(x, y, maze) : (
dir == 2 ? go_left_from(x, y, maze) :
go_down_from(x, y, maze) // dir must be 3
)
);
Random walking
Here comes the climax of our maze; however, it's the most complex. First, we have to know how many visitable directions we can try.
// return visitable directions we can try
function visitable_dirs_from(x, y, maze, rows, columns) = [
for(dir = [0, 1, 2, 3])
if(visitable(next_x(x, dir), next_y(y, dir), maze, maze_rows, columns))
dir
];
After visiting the (x, y) block, we use rand_dirs to get a list of random directions if the number of the visitable directions is not 0.
// walk from (x, y)
function go_maze(x, y, maze, rows, columns) =
// have visitable directions?
len(visitable_dirs_from(x, y, maze, rows, columns)) == 0 ?
set_visited(x, y, maze) // we visited here and cannot go further.
: walk_around_from( // walk randomly from (x, y)
x, y,
rand_dirs(), // random directions
set_visited(x, y, maze), // we visited here
rows, columns
);
We use an incremental i to try four directions.
// walk randomly from (x, y)
function walk_around_from(x, y, dirs, maze, rows, columns, i = 4) =
i > 0 ?
walk_around_from(x, y, dirs,
try_routes_from(x, y, dirs[4 - i], maze, rows, columns),
rows, columns,
i - 1) // try next direction
: maze;
The try_routes_from function checks whether the next block is visitable according to the given direction. If it's walkable, invoke the try_block function listed before. It will return a new status of the maze. After that, invoke go_maze again.
function try_routes_from(x, y, dir, maze, rows, columns) =
// is the next block visitable?
visitable(next_x(x, dir), next_y(y, dir), maze, rows, columns) ?
go_maze(
next_x(x, dir), next_y(y, dir),
try_block(dir, x, y, maze, rows, columns),
rows, columns
)
: maze;
That is, it's a sub-task from here. We start from (x, y) to try the next block (x', y') and get a new status of the maze. Then, We start from (x', y') to try the next block and get a new status of the maze again. This process will continue until we visited all blocks.
What's the initial status of the maze? Remember it? We've defined a starting_maze function to do initialization of a maze before, and the first (x, y) is (1, 1), the starting point.
Once all the above are ready, we can generate a 10x10 maze now.
block_width = 3;
wall_thickness = 1;
maze_rows = 10;
maze_columns = 10;
maze_blocks = go_maze(
1, 1, // the starting point
starting_maze(maze_rows, maze_columns),
maze_rows, maze_columns
);
draw_maze(
maze_rows,
maze_columns,
maze_blocks,
block_width,
wall_thickness
);
Look at all the code above. Do we re-assign a value to a variable? No! Do we modify any element of a vector? No! We just pass a new value to a parameter of a function. We return a new vector including a new status of the maze.
In fact, it's why you have to divide and conquer again and again. As I said, maze algorithms are not diffcult. The hard part is turning your thinking into Functional programming.
There are many benefits of Functional programming. I don't want to repeat them here. If you are interested, just search them on the internet. Love Functional programming or not, it's up to you.
Let's create a 30x30 maze!
For completeness, I list all the code of the maze below.
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, visited) = [x, y, wall_type, visited];
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);
}
// initialize the status of a maze
function starting_maze(rows, columns) = [
for(y = [1:rows])
for(x = [1:columns])
block_data(
x, y,
// all blocks have UP_RIGHT_WALL except the exit
y == rows && x == columns ? UP_WALL : UP_RIGHT_WALL,
// false is unvisited
false
)
];
// find the index of block (x, y)
function indexOf(x, y, maze, i = 0) =
i > len(maze) ? -1 : (
[get_x(maze[i]), get_y(maze[i])] == [x, y] ? i :
indexOf(x, y, maze, i + 1)
);
// check whether we've visited the block (x, y)
function visited(x, y, maze) = maze[indexOf(x, y, maze)][3];
// is (x, y) visitable?
function visitable(x, y, maze, rows, columns) =
y > 0 && y <= rows && // y is not out of bound
x > 0 && x <= columns && // x is not out of bound
!visited(x, y, maze); // visited or not
// we've visited (x, y)
function set_visited(x, y, maze) = [
for(b = maze)
[x, y] == [get_x(b), get_y(b)] ?
[x, y, get_wall_type(b), true] : b
];
// 0（right）、1（up）、2（left）、3（down）
function rand_dirs() =
[
[0, 1, 2, 3],
[0, 1, 3, 2],
[0, 2, 1, 3],
[0, 2, 3, 1],
[0, 3, 1, 2],
[0, 3, 2, 1],
[1, 0, 2, 3],
[1, 0, 3, 2],
[1, 2, 0, 3],
[1, 2, 3, 0],
[1, 3, 0, 2],
[1, 3, 2, 0],
[2, 0, 1, 3],
[2, 0, 3, 1],
[2, 1, 0, 3],
[2, 1, 3, 0],
[2, 3, 0, 1],
[2, 3, 1, 0],
[3, 0, 1, 2],
[3, 0, 2, 1],
[3, 1, 0, 2],
[3, 1, 2, 0],
[3, 2, 0, 1],
[3, 2, 1, 0]
][round(rands(0, 24, 1)[0])];
// given the `x` value and a direction, return the `x` value of the next block
function next_x(x, dir) = x + [1, 0, -1, 0][dir];
// given the `x` value and a direction, return the `x` value of the next block
function next_y(y, dir) = y + [0, 1, 0, -1][dir];
// go right, remove the right wall
function go_right_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x, y] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x, y, UP_WALL, visited(x, y, maze)] :
[x, y, NO_WALL, visited(x, y, maze)]
) : b
];
// go up, remove the upper wall
function go_up_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x, y] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x, y, RIGHT_WALL, visited(x, y, maze)] :
[x, y, NO_WALL, visited(x, y, maze)]
) : b
];
// go left, remove the right wall of the left block
function go_left_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x - 1, y] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x - 1, y, UP_WALL, visited(x - 1, y, maze)] :
[x - 1, y, NO_WALL, visited(x - 1, y, maze)]
) : b
];
// go down, remove the upper wall of the lower block
function go_down_from(x, y, maze) = [
for(b = maze) [get_x(b), get_y(b)] == [x, y - 1] ? (
get_wall_type(b) == UP_RIGHT_WALL ?
[x, y - 1, RIGHT_WALL, visited(x, y - 1, maze)] :
[x, y - 1, NO_WALL, visited(x, y - 1, maze)]
) : b
];
// 0（right）、1（up）、2（left）、3（down）
function try_block(dir, x, y, maze, rows, columns) =
dir == 0 ? go_right_from(x, y, maze) : (
dir == 1 ? go_up_from(x, y, maze) : (
dir == 2 ? go_left_from(x, y, maze) :
go_down_from(x, y, maze) // dir must be 3
)
);
// return visitable directions we can try
function visitable_dirs_from(x, y, maze, rows, columns) = [
for(dir = [0, 1, 2, 3])
if(visitable(next_x(x, dir), next_y(y, dir), maze, maze_rows, columns))
dir
];
// walk from (x, y)
function go_maze(x, y, maze, rows, columns) =
// have visitable directions?
len(visitable_dirs_from(x, y, maze, rows, columns)) == 0 ?
set_visited(x, y, maze) // we visited here and cannot go further.
: walk_around_from( // walk randomly from (x, y)
x, y,
rand_dirs(), // random directions
set_visited(x, y, maze), // we visited here
rows, columns
);
// walk randomly from (x, y)
function walk_around_from(x, y, dirs, maze, rows, columns, i = 4) =
i > 0 ?
walk_around_from(x, y, dirs,
try_routes_from(x, y, dirs[4 - i], maze, rows, columns),
rows, columns,
i - 1) // try next direction
: maze;
function try_routes_from(x, y, dir, maze, rows, columns) =
// is the next block visitable?
visitable(next_x(x, dir), next_y(y, dir), maze, rows, columns) ?
go_maze(
next_x(x, dir), next_y(y, dir),
try_block(dir, x, y, maze, rows, columns),
rows, columns
)
: maze;
block_width = 3;
wall_thickness = 1;
maze_rows = 30;
maze_columns = 30;
maze_blocks = go_maze(
1, 1, // the starting point
starting_maze(maze_rows, maze_columns),
maze_rows, maze_columns
);
draw_maze(
maze_rows,
maze_columns,
maze_blocks,
block_width,
wall_thickness
);