Amazingly Raku - Part 1: The Maze
[94.1] Published 28. September 2020. Updated 9. December 2020See also: The Introduction.
Those of you old enough may remember MSDOS programs with pretty advanced user interfaces, using nothing but ASCII characters. E.g. Norton Commander.
The Box Drawing symbols have found their way into the Unicode standard. See e.g. en.wikipedia.org/wiki/Box-drawing_character for more information.
The original use case is pretty much obsolete, but ╗, ═,
╝, ╔, ║, ╚, ╦,
╠, ╣, ╩ and ╬ are excellent for
drawing mazes. I am using █ for the entry and exit.
Here is a traversable 5x5 character maze (the file «5x5-ok.txt»). The original maze is shown on the left, and a path (one of many) is shown highlighted on the right:
█╩╩║╬ █╩╩║╬
╠╬╬╔╦ ╠╬╬╔╦
╬╬╬═╣ ╬╬╬═╣
╠╩╩╩╣ ╠╩╩╩╣
╩╬╬║█ ╩╬╬║█
The open ends look rather unfortunate when they are dead ends, so let us try the filled in
symbols ┓, ━, ┛, ┏, ┃,
┗, ┳, ┣, ┫, ┻ and
╋ instead:
█┻┻┃╋
┣╋╋┏┳
╋╋╋━┫
┣┻┻┻┫
┻╋╋┃█
| That does not look very nice. It is easy to interpret the black lines as walls, and the non-black areas as corridors. So I'll stick with the hollow versions. You just have to imagine walls filling in the open ends, like this: |  |
Here is a non-traversable maze (the file «5x5-fail.txt»):
█╠╠╠╦
╬╦╬╬╩
╠╩╣╦╬
╬╠╝╬╦
╣╣╦╣█
An impressive 25x25 maze (the file «25x25-ok.txt»):
█╩╣╦╬╔╣╠╬╦╣╣╬╠╦╦╦╬╩╣╩╬╦╩╩
╣╬╝╔╣╦╩╬╩╠╠╬╦╬╬╬╣╠╩╦╩╠╩╠╠
╣╠╠╦╦╦╦╩╠╬╝╠╠╣╣╣╦╩╣═╬╩╠╣╠
╬╠╠║╣╬╩╦╬╬╩╠╬╬╦╠╣╩╬╠╬╠╠╦╣
╩╩╬╚╠╩╠╣╣╠╬╦╩╦╬╬╩═╦╠╩╚╔╚╬
╦╔╦╬╩╩╠╔╣╩╦╝╣╩╬╬╠╠╝╦═╣╚╠╦
╝╩╣╩╦╩╣╣╦╦╣╠╦╔║╦╦╬╬╬╬╣╩╣╠
╬╩╩╦╬╬╣╣╦═╩╠╣╬╠╣╠║╚╠╩╬╬╩╩
╩║║╚╬╩╦╬╝╣╣╩║╦╩╬╔╚╬╦╦╦╦╚║
╠╦╣╬╬╩╣╩╩╬║╠╣╠╩╠╬╬╣╬╠╦═╦╬
═╠╣╠╣╝╬╩╩╣╦╩╬╬╬╬╣╚╦╦╦╩╦╦╦
╬╠║╚╬╩╚╣╬╩╠╬╦╬╬╠╬╩╩╩╩╩╠╣═
╠╦╝╣╬╦╣╦╩╩╦╣╦╬╬╬═╦╠╦╣╩╬╩╠
╦╣╬╬╠╠╦╠╠╠╠╠╠╚╠╦╠╬╬╬╣╩╚╣╬
╦╣╔╚╣╩╬╦═╔╬╩╦╔╣╩╬╩╬╠╠╣╦╠╦
╣╠╦╠╩╬╦╠╠╬╠╬╩╦╣║╦╣═╦╩╬╠╬╬
╬╩╦╠╝╣╦╠╬╠╩═╬╩╦╣╩╣╠╩╠╬╬╣╠
╦╠╣╦╦╠╣╣═╠╩╣╬╬╬╦╩╠╣╬╣╝╩╠╦
╠╩╬╬═╔╩╦╠╠║╩╬╬╣╠╩╠╠╣╣╬╣╬╩
╩╦╬╣╬╣╠╬╣╠╣╩╦╣╦╬╣╚╦╣╠╠╩║╚
╦╩╩╦╔╬═╣╦╝╣╣╠╠╬╦═╩╔╣╔╦╬║╣
╩╬╩╬╣╩╠╩╠╣╬╠╦╠╬╠╬╬╬╠╦╠╠╬╩
╬╬╣╣╦╠╣╦╦╠╣╩╣╩╦╩╦╬╬╦╬╚╣╬╦
╚╬╣╦╠╠╠╩╝╩╬╚╠╠╬╣╬╦╣╩╠╣╩╬╬
╠║╬╦╣╬╦╠╠╦╣╠╣╩╚╠╦╩╩╠╬╚╬╣█
And yes, it is traversable:
█╩╣╦╬╔╣╠╬╦╣╣╬╠╦╦╦╬╩╣╩╬╦╩╩
╣╬╝╔╣╦╩╬╩╠╠╬╦╬╬╬╣╠╩╦╩╠╩╠╠
╣╠╠╦╦╦╦╩╠╬╝╠╠╣╣╣╦╩╣═╬╩╠╣╠
╬╠╠║╣╬╩╦╬╬╩╠╬╬╦╠╣╩╬╠╬╠╠╦╣
╩╩╬╚╠╩╠╣╣╠╬╦╩╦╬╬╩═╦╠╩╚╔╚╬
╦╔╦╬╩╩╠╔╣╩╦╝╣╩╬╬╠╠╝╦═╣╚╠╦
╝╩╣╩╦╩╣╣╦╦╣╠╦╔║╦╦╬╬╬╬╣╩╣╠
╬╩╩╦╬╬╣╣╦═╩╠╣╬╠╣╠║╚╠╩╬╬╩╩
╩║║╚╬╩╦╬╝╣╣╩║╦╩╬╔╚╬╦╦╦╦╚║
╠╦╣╬╬╩╣╩╩╬║╠╣╠╩╠╬╬╣╬╠╦═╦╬
═╠╣╠╣╝╬╩╩╣╦╩╬╬╬╬╣╚╦╦╦╩╦╦╦
╬╠║╚╬╩╚╣╬╩╠╬╦╬╬╠╬╩╩╩╩╩╠╣═
╠╦╝╣╬╦╣╦╩╩╦╣╦╬╬╬═╦╠╦╣╩╬╩╠
╦╣╬╬╠╠╦╠╠╠╠╠╠╚╠╦╠╬╬╬╣╩╚╣╬
╦╣╔╚╣╩╬╦═╔╬╩╦╔╣╩╬╩╬╠╠╣╦╠╦
╣╠╦╠╩╬╦╠╠╬╠╬╩╦╣║╦╣═╦╩╬╠╬╬
╬╩╦╠╝╣╦╠╬╠╩═╬╩╦╣╩╣╠╩╠╬╬╣╠
╦╠╣╦╦╠╣╣═╠╩╣╬╬╬╦╩╠╣╬╣╝╩╠╦
╠╩╬╬═╔╩╦╠╠║╩╬╬╣╠╩╠╠╣╣╬╣╬╩
╩╦╬╣╬╣╠╬╣╠╣╩╦╣╦╬╣╚╦╣╠╠╩║╚
╦╩╩╦╔╬═╣╦╝╣╣╠╠╬╦═╩╔╣╔╦╬║╣
╩╬╩╬╣╩╠╩╠╣╬╠╦╠╬╠╬╬╬╠╦╠╠╬╩
╬╬╣╣╦╠╣╦╦╠╣╩╣╩╦╩╦╬╬╦╬╚╣╬╦
╚╬╣╦╠╠╠╩╝╩╬╚╠╠╬╣╬╦╣╩╠╣╩╬╬
╠║╬╦╣╬╦╠╠╦╣╠╣╩╚╠╦╩╩╠╬╚╬╣█
What about a 50x25 maze (the file «50x25.txt»)?
█╣╠╬═╣═╩╣╠╠╝╩╬╩╠╣╦╬╩╚╠╦╣╠╣╠╦╬╩╠╩║╬╣╠╚╩╬╠╩╩═╬╣═╬╣╣║
╩╠╩║╦╩╦╦╦╣╝═╠╦═╦╚╬╩╬╠╩╬╣╩║╠╚╠╩═╦╣╦╩╠╠╬╬╬╣╠╩╩╣╦╣╣╦╣
╬╠╣═╚╣╬╩╩╠╦╩╩╦╣╩╝╬╣╩╩║╬║╠╣╬╩╣╝╬╦╣╬╩╦╠╠╬╦╣╦╣╣╩╠╬║╦╬
║╩╩╩═╣╬╠╠╦╩╬╠╝╩╬╦╩╣╣╩╦═╣╦╬╬╦╬╩╦╠╬╣╣╬╬╠╠╩╦╠╚╩╣╩╦╩╣╦
╩╬╣╣╣╣╦╩╦╬╩╝╩╦╣╦║╦╦╣╠╔╬╬╩╠╣╣╦═╬╠╠╣╦═╬╦╦╩║╠╩╩╠╩╬╦╩╬
╣╠╩╣╦╦╦╣╦╩╬═╩╠╠╦╠║╬╠╠╬╣╩╠╝╣╬╠╦╣║╬╚╩╬╬╬╦╠╦╦╠╬╠╣╦╣╩╠
╦╦║╩╩╠╣╣╩═╣╦╠╣╦╦╦╩╔╠╠╠╦╣╬═╬╬╠╦╩╩╬╬╦║╦╠║╦╬╣╦╦╬╠╩╩╠╬
╩╠╚╣╦╠╣╦╬╩╣╣╣╔╦╩╬╦╩╬╬╩╬╦╠╠╣╬═╦╦╦╦╬╦╣╠╣╠╔╩╬╣╠╦╝╬╦╣╬
╔╝╦╠╩╣╦╦╩╣╠╬╩╩╦╦╠╩╣╩╣╩╠╠╣╩╣╦╦╠╬╬╦╬╬╩╦╣╦╩╠╔╦╦╣╔╩╠╬╠
═╦╦╣╦╠║╬╦╣╦╬╣╬╩╣╦╦╣╠╬╬╩═╠╣╠╠╣╠╬╬╬╠╩╩╦╦╚╣╔╠╠╣╣╣╠╬╩╦
╬╬╣╣╩═╔╣╬╔╬╬╣╠╠╬╣╬╣╩╠╬╩╣╔╩╩╦╩╣╩║╩╔╩╦╣═╬║╦╠╣╝╦╦╠╬╩╚
╬╦╬╣╣╣╩╠╠╦╚╣╠╬╦║╣╩╦╬╣╦╠╦╠╠╣╠╣╣╣╠╣╣╬╣╩╣╠╠╠╩╣╣╩╦═╠╦╦
╣╩╩╬╩╬╦╚╠╩╣╬╬══╬╣╦╣╣╠╬╔╣╦╦╣╬╬╬╠╣╬║╦╠╣║╬╦╩╬╩╦╩╦╝╩╬╝
╦╩╣╣╦╦╬╩╩╝╬╠╩╣╠╬═╩╦╩╬╬╬╩═╩╠╣╣╩╠╣╦╠╣╣║╣═╦╩╣╝╬╣╦╬╦║╬
╬╠╦╩╠╬╠╦╚╩╠╬╠╩╣╦╝╬╦╠╦╩╠╦╬╬╣╠╠╩╬╦╣╣╣╔╬╩╠╠╣╦╠╠╬╣╦╩╦╣
╠╬╩╠╩╦╬╠╦╦╚╬╣╩╣╠╠╠╠╔═╩╬╩╬╩╠╠╣╣╬╬╔╠╬╠╬╣╩╦╩╣╣╩╩╦╦╦╬╬
╣╩╣╦╬╦╬╩╦╦╦╩╔═╩╦╦╬╣╣╩╩╣╣╦╦╦╦╩╠╩╩╦╦╩╣╦╩╩═╬╩╠╝╩╔╬╬╠╠
╦╠╝╠╔╬╝╬╦╣╝╦╬╦╝╬╦╣╩╬╣╬╠╦╣╣╣╦╬╣╬╬╩╠╦╦╣╬╩╬╦╣╣╣╬╠╦╦╝║
╠═╬╚╦╣╩╦╣╠╚╚╠║╦╩║╦╠╠═╣╣╠╬╩╦╔╠╠╬╩║╬╠╦╬═╦╦╦╦╩╠╩╩╦╦╬╣
╬╣╝╩═╠╣╩╦╣╬╠╦╝╠╦╣╬╬╣╣╬╦╠╦╦╝╬╦║╣╠╩╣╣╠╠╠╦╩╦╦╠╬╔╣╩╠╠╠
╣╦╣╩╬╩╬╣╬╠╬╬╣╣╠╦║╠╦═╦╣╠╩╬╦╝╠╠╝╚╠╠╩╣╩╩╬╠╦╬═╣╦╣╚╩╩╠╬
╠╩╠╩╣╣╬╠╝╠╣╠═╣║╦╬╩╣╩╣╩╣╣╬╣╩╠╦╣╩║╬╣╩╠╩╦╬╦╚╩╦╬╠╠╦╬╩╣
╠╠╠╦╣╠╠╬╦╩═╣╩╩╩╩╬║╬╣╔═╣╠╠╣╣╠╩═╠╩╦╩╩╬╩╩╠╣╦╬╬╦╦╣╩╣║╣
╠║╣╣╬╣╬╩╣╝╣╦╦╦╩╠╦╔╠╩═╚╬═╣╩╩╬╠╣╦╦╣║╦╦╠╣╩╦╣╣╣╝╝║╣╦╣╣
╩╬╠╩╬╬═╣╩╦╦╩╬╩╩╩╩╬╩╣╩╦╣╦╦╝╩╣║╠╦╦╬╦╦╠╬║╩╬╬╠╩╬╬╠║╠═█
Feel free to try traversing it...
An Amazing Program
I certainly did not make up these mazes manually. I wrote a program. Here it is:
File: mazemaker
#! /usr/bin/env raku
unit sub MAIN ($cols = 25, # [1]
$rows = 25, # [1a]
:s(:$scale) = 7, # [2]
:v(:$verbose)); # [5]
my %weight = ( # [3]
'╗' => 1,
'═' => 1,
'╝' => 1,
'╔' => 1,
'║' => 1,
'╚' => 1,
'╦' => $scale,
'╠' => $scale,
'╣' => $scale,
'╩' => $scale,
'╬' => $scale
);
constant $end = '█'; # [4]
my @symbols = %weight.keys.map({ $_ xx %weight{$_} }).flat; # [5]
say ": Symbols: @symbols[]" if $verbose; # [6]
my @maze;
@maze.push: @symbols.roll($cols).join for ^$rows; # [7]
@maze[0].substr-rw(0,1) = @maze[$rows-1].substr-rw($cols-1,1) = $end; # [8]
say @maze.join("\n"); # [9]
[1] The default size of the maze is 25 columns [1] and 25 rows [1a].
[2] An earlier version of this program treated all the characters as equal when choosing from them at random. That led to mazes that had a lot of dead ends, and most of them were not traversable. This command line option makes it possible to favour symbols with three or four exits. The default value of 7 is a result of trial and error. Feel free to try other values.
[3] The symbols, and the weight, is set up here.
[4] A variable with a constant (read only) value, is a constant.
[5]
Set up a list of characters to choose from when we construct the maze.
Note the use of the List Repetition Operator xx to inseart as
many copies of the characters as prescribed by the weight. The final flat
is there to prevent a list of lists. We want a one dimentional list.
[6] Use Verbose Mode to see the list of characters to choose from, with repetitions according to the weight.
[7] Generate one row at a time, and add it to the array.
roll gives us the specified number of characters (in this case the length
of the row, the number of columns) chosen at random from the array. Each character
has the same weight, so the duplicates we insterted gives some of them a higher
possibility to be chosen.
[8]
Replace the upper left and lower right corners with a filled
square symbol, indicating the entry point and exit of the maze. The usual
substr does not change the value itelf, but returns the modified
version. We want it changed, so use substr-rw instead.
[9] Print the maze.
See
docs.raku.org/routine/constant for
more information about constant.
See
docs.raku.org/routine/xx for more
information about the list repetition operator xx.
See
docs.raku.org/routine/flat for more
information about the flattening operator flat.
See
docs.raku.org/routine/roll for more
information about roll.
See
docs.raku.org/routine/substr for more
information about substr.
See
docs.raku.org/routine/substr-rw for more
information about substr-rw.
The mazes shown above were created by this program.
Note that the mazes do not have any empty cells (the space symbol). That is on purpose, to make it harder to find a path just by looking at the maze. They have a lot of unreachable parts, for the same reason.
An Even More Amazing Program
The mazes shown so far are full of what looks like exits at the edges. We should perhaps do something about them, as it does not look very professional.
The left hand maze is an original maze, as generated by the «mazemaker» program. The second one shows the spurious exits, the third one shows the result of removing those exits, and the fourth and final one highlights the resulting empty cells (the spaces):
Original Problems Modified Spaces
█╦╩╚╦╦╠╩╦╣ █╦╩╚╦╦╠╩╦╣ █╦═ ╦╦╔═╦╗ █╦═█╦╦╔═╦╗
╠╬╣║╠╦╠╣╗╩ ╠╬╣║╠╦╠╣╗╩ ╠╬╣║╠╦╠╣╗╝ ╠╬╣║╠╦╠╣╗╝
╠╣╦═╠╠╣╔╦╩ ╠╣╦═╠╠╣╔╦╩ ╠╣╦═╠╠╣╔╦╝ ╠╣╦═╠╠╣╔╦╝
╦╠╩╣║╦╦╬╬╝ ╦╠╩╣║╦╦╬╬╝ ╔╠╩╣║╦╦╬╬╝ ╔╠╩╣║╦╦╬╬╝
╗╦╣╬╩╣╩╠╣╣ ╗╦╣╬╩╣╩╠╣╣ ╦╣╬╩╣╩╠╣╣ █╦╣╬╩╣╩╠╣╣
╦╩╩╦╗╩╣╩╣╬ ╦╩╩╦╗╩╣╩╣╬ ╔╩╩╦╗╩╣╩╣╣ ╔╩╩╦╗╩╣╩╣╣
╣╩╩╦╩╩╣╬╬╚ ╣╩╩╦╩╩╣╬╬╚ ║╩╩╦╩╩╣╬╬ ║╩╩╦╩╩╣╬╬█
╩╦╦╦╣═╩╣╬╣ ╩╦╦╦╣═╩╣╬╣ ╚╦╦╦╣═╩╣╬╣ ╚╦╦╦╣═╩╣╬╣
╣╣╣╬╩╬═╚╠╩ ╣╣╣╬╩╬═╚╠╩ ║╣╣╬╩╬═╚╠╝ ║╣╣╬╩╬═╚╠╝
╦═╩╬╦╬╩╣╣█ ╦═╩╬╦╬╩╣╣█ ═╩╩═╩╩╝╝█ █═╩╩═╩╩╝╝█
The empty cells are caused by the program removing all but one exit from the original symbols, and we do not have a symbol with only one exit. So there is nothing left, thus a space symbol.
Note that the maze is not traversable, as the exit is unreachable.
Removing one (or more) exits is easy(ish), if we translate the symbols into strings. I have
chosen the letters N=North (up), E=East (right), S=South (down) and W=West (left). The
╬ symbol translates to «NESW». Then we just remove e.g. the «N» letter (if we
are on the top row in the maze), and translate the string «ESW» back to the symbol ╦.
The printed mazes look like maps, so it is customary to use the compass directions. They have the added benefit of beeing unambiguous. Imagine beeing somewhere inside the maze, looking south. Taking a left hand turn leads you in the western direction. You are obviously going left, even it is in the right direction on the map.
File: mazemaker2
#! /usr/bin/env raku
unit sub MAIN ($cols = 25,
$rows = 25,
:s(:$scale) = 7,
:f(:$fill), # [1]
:v(:$verbose));
my %weight;
my %desc2symbol;
if $fill
{
%weight = (
'┓' => 1,
'━' => 1,
'┛' => 1,
'┏' => 1,
'┃' => 1,
'┗' => 1,
'┳' => $scale,
'┣' => $scale,
'┫' => $scale,
'┻' => $scale,
'╋' => $scale
);
%desc2symbol = ( # [2]
SW => '┓',
EW => '━',
NW => '┛',
ES => '┏',
NS => '┃',
NE => '┗',
ESW => '┳',
NES => '┣',
NSW => '┫',
NEW => '┻',
NESW => '╋'
);
}
else
{
%weight = (
'╗' => 1,
'═' => 1,
'╝' => 1,
'╔' => 1,
'║' => 1,
'╚' => 1,
'╦' => $scale,
'╠' => $scale,
'╣' => $scale,
'╩' => $scale,
'╬' => $scale
);
%desc2symbol = (
SW => '╗',
EW => '═',
NW => '╝',
ES => '╔',
NS => '║',
NE => '╚',
ESW => '╦',
NES => '╠',
NSW => '╣',
NEW => '╩',
NESW => '╬'
);
}
my %symbol2desc = %desc2symbol.antipairs; # [3]
say ": Mapping: { %mapping.raku }" if $verbose;
constant $end = '█';
my @symbols = %weight.keys.map({ $_ xx %weight{$_} }).flat;
say ": Symbols: @symbols[]" if $verbose;
my @maze;
@maze.push: @symbols.roll($cols).join for ^$rows;
@maze[0].substr-rw(0,1) = @maze[$rows-1].substr-rw($cols-1,1) = $end;
if $verbose
{
say @maze.join("\n");
say '';
}
remove-direction(@maze[0].substr-rw($_,1), "N") for ^$cols; # [4]
remove-direction(@maze[$_].substr-rw(0,1), "W") for ^$rows; # [4a]
remove-direction(@maze[$_].substr-rw($cols-1,1), "E") for ^$rows; # [4b]
remove-direction(@maze[$rows-1].substr-rw($_,1), "S") for ^$cols; # [4c]
say @maze.join("\n");
sub remove-direction($symbol is rw, $direction) # [5]
{
my $desc = %symbol2desc{$symbol} // return $symbol; # [6]
$desc ~~ s/$direction//; # [7]
$symbol = %desc2symbol{$desc} // ' '; # [8]
}
[1] Use the «--fill» (or «-f») command line option if you want the filled in symbols instead.
[2] The mapping from symbols to strings. The order of the symbols is NESW (starting North, continuing clockwise), so that we can translate to and from the strings without problems.
[3] The mapping in the other direction, from the strings to
the symbols. Using antipairs on a hash gives us a new hash, where the
keys and values have been swapped.
[4] Remove any North exits from the top row [4], any West exits from the leftmost column [4a], any East exits from the rightmost column [4b], and any South exits from the bottom row [4c].
[5] The procedure removing a given direction from the symbol, if set. Note
is rw on the symbol variable, so that we can change it.
[6] Return the symbol if we cannot translate it into a string. This applies to the black (entry and exit) boxes.
[7] Remove the directional character (substitue it with nothing).
See
docs.raku.org/routine/antipairs for
more information about antipairs.
Part 2: The Path
Mazes are meant for traversal. We'll look for a path through them in the next part; Part 2: The Path.