cmat← {⎕rl←2⊃⎕ai} ##.maze shape ⍝ Kidz maze.
Returns a random maze of specified shape, which may be of rank greater than 2.
If the optional left argument is omitted, sucessive calls to [maze] will produce
disinct random mazes.
Entry to, and exit from the maze is through a portal, top left and bottom right,
marked "↓".
In a high-rank maze, we can move within a plane in the normal way, or warp be-
tween planes, up-down/left-right (but not diagonally), providing our way is not
blocked by a closed cell containing a ∘. See examples below.
Technical notes:
Maze construction is in two stages:
[path] Starting at the entrance and exit, a pair of random paths are extended
alternately into the maze, until they meet. This is the solution path.
[fill] Starting from each randomly chosen unvisited cell, a random path is ex-
tended until it collides with an existing path. This is a "tributary" of
the solution path.
As an exercise in functional programming, the coding of the maze function is
"stateless". This means that there are no variables (only definitions, that
don't vary) and no partial assignments, such as ]← and )←. In particular, sub-
function →select← has been used in places where indexed assignment would be con-
siderably faster on the grounds that, for a folly such as this, the speed of
execution may take second place to exploration of programming techniques.
As a coding aid, the closing } of some of the inner functions have been labelled
using an ad hoc notation, with the "type" of the function. For example initial-
isation function [init] is labelled: (c d)(fm to)←:: size. This is to be inter-
preted as "function takes a right argument of size and returns a nested 2-vector
of control and display arrays, and from and to node indices". Similarly, funct-
ion [extend] is of type: (c d)(fm to)←(c d)tag :: path, which means it takes a
path vector on the right and a "structure" on the left, and returns a pair of
pairs.
Examples:
maze 10 20 ⍝ 2-maze.
┌↓────┬───────┬───┬─────────────┬───┬───┐
│ │ │ │ │ │ │
│ ┌─┬─┴─┬─┐ │ └─┐ └── │ ────┬── │ │ └── │
│ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ └───┘ ──┬─┼── ──┼───┬─┼──── │
│ │ │ │ │ │ │ │ │ │
│ └── │ ──┘ ┌───┐ ──┘ │ ──┐ ├─┐ │ └─┬── │
│ │ │ │ │ │ │ │ │ │
│ ──┐ ├─┬───┤ │ │ ──┐ ├─┬─┤ │ ├──── └─┐ │
│ │ │ │ │ │ │ │ │ │ │ │ │
├── │ │ │ │ │ │ │ │ └─┘ │ └── │ ┌─────┤ │
│ │ │ │ │ │ │ │ │ │ │ │
├─┐ ├───┘ ├─┬─┴─┼─┴─────┼───┬─┘ │ ┌── │ │
│ │ │ │ │ │ │ │ │ │ │
│ │ ├── ──┤ │ │ │ ──┬───┘ │ │ ┌───┤ ──┤ │
│ │ │ │ │ │ │ │ │ │ │ │
│ ──┼─┐ │ └─┬─┘ └── │ │ │ │ │ │ │ └─┐ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │
│ ──┘ │ │ │ │ ──┬── └─┴─┴─┘ ├── └─┐ └───┤
│ │ │ │ │ │ │ │
└─────┴─┴─┴─────┴───────────┴─────┴────↓┘
maze 3 3 4 ⍝ 3-maze
┌─┬─┬─┬─┐ ┌─┬─┬───┐ ┌─┬─┬─┬─┐ ┌───┬─┬─┐ ┌─┬─┬─┬─┐ ┌───────┐ ┌─┬─┬─┬─┐
│↓│∘│∘│∘│ │ │ │ │ │ │∘│ │∘│ │ │ │ │ │∘│∘│∘│ │ │ │ │∘│∘│∘│∘│
├─┼─┼─┼─┤ ├─┘ ├── │ ├─┼─┼─┼─┤ │ │ ├─┴─┤ ├─┼─┼─┼─┤ ├──── │ │ ├─┼─┼─┼─┤
│∘│∘│∘│∘│ │ │ │ │∘│ │∘│ │ │ │ │ │ │ │∘│ │∘│ │ │ │ │∘│∘│∘│∘│
├─┼─┼─┼─┤ ├───┼── │ ├─┼─┼─┼─┤ │ ├─┴───┤ ├─┼─┼─┼─┤ ├───┐ └─┤ ├─┼─┼─┼─┤
│∘│∘│∘│∘│ │ │ │ │ │ │∘│∘│ │ │ │ │∘│ │∘│∘│ │ │ │ │∘│∘│∘│↓│
└─┴─┴─┴─┘ └───┴───┘ └─┴─┴─┴─┘ └─┴─────┘ └─┴─┴─┴─┘ └───┴───┘ └─┴─┴─┴─┘
The route through this maze is as follows:
↓ entrance
┌─┬─┬─┬─┐ ┌─┬─┬───┐ ┌─┬─┬─┬─┐ ┌───┬─┬─┐ ┌─┬─┬─┬─┐ ┌───────┐ ┌─┬─┬─┬─┐
│1│∘│∘│∘│ │2│ │ │ │3│∘│ │∘│ │4 │ │ │ │∘│∘│∘│ │ │ │ │∘│∘│∘│∘│
├─┼─┼─┼─┤ ├─┘ ├── │ ├─┼─┼─┼─┤ │ │ ├─┴─┤ ├─┼─┼─┼─┤ ├──── │ │ ├─┼─┼─┼─┤
│∘│∘│∘│∘│ │ │ │ │∘│ │∘│ │ │5│ │ │ │6│∘│ │∘│ │7 │ │ │∘│∘│∘│∘│
├─┼─┼─┼─┤ ├───┼── │ ├─┼─┼─┼─┤ │ ├─┴───┤ ├─┼─┼─┼─┤ ├───┐ └─┤ ├─┼─┼─┼─┤
│∘│∘│∘│∘│ │ │ │ │ │ │∘│∘│ │ │ │ │∘│ │∘│∘│ │ │ 8│ │∘│∘│∘│9│
└─┴─┴─┴─┘ └───┴───┘ └─┴─┴─┴─┘ └─┴─────┘ └─┴─┴─┴─┘ └───┴───┘ └─┴─┴─┴─┘
exit ↓
Similarly:
maze 2 3 2 3 ⍝ 4-maze.
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│∘│∘│∘│ │↓│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐
│∘│∘│∘│ │ │ │ │ │ │ │ │ │ │ │ │∘│∘│ │ │ │ │ │∘│∘│∘│
├─┼─┼─┤ ├─┴─┴─┤ ├─┼─┼─┤ ├─┼─┬─┤ ├─┼─┼─┤ ├─┴───┤ ├─┼─┼─┤
│∘│∘│∘│ │ │ │∘│∘│ │ │ │ │ │ │ │∘│∘│ │ │ │∘│∘│∘│
└─┴─┴─┘ └─────┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─────┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│∘│∘│∘│ │ │ │∘│ │∘│∘│∘│ │∘│ │∘│ │∘│∘│∘│ │ │ │∘│ │∘│∘│∘│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│∘│∘│∘│ │ │∘│∘│ │∘│∘│∘│ │ │ │ │ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐ ┌─────┐ ┌─┬─┬─┐
│∘│∘│∘│ │ │ │ │ │∘│∘│ │ │ │ │∘│∘│∘│ │ │ │∘│∘│∘│
├─┼─┼─┤ │ ├─┬─┤ ├─┼─┼─┤ ├─┘ │ │ ├─┼─┼─┤ │ │ ──┤ ├─┼─┼─┤
│∘│∘│∘│ │ │ │ │ │∘│ │ │ │ │ │ │∘│∘│∘│ │ │ │ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └───┴─┘ └─┴─┴─┘ └─┴───┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│↓│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
With solution:
↓ entrance
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│∘│∘│∘│ │a│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐
│∘│∘│∘│ │b│ │ │ │ │ │ │ │ │o p│ │∘│∘│q│ │ │s r│ │∘│∘│∘│
├─┼─┼─┤ ├─┴─┴─┤ ├─┼─┼─┤ ├─┼─┬─┤ ├─┼─┼─┤ ├─┴───┤ ├─┼─┼─┤
│∘│∘│∘│ │g h│ │∘│∘│i│ │ │ │j│ │ │∘│∘│ │ │ │∘│∘│∘│
└─┴─┴─┘ └─────┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─────┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│∘│∘│∘│ │c│ │∘│ │∘│∘│∘│ │∘│n│∘│ │∘│∘│∘│ │ │t│∘│ │∘│∘│∘│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│∘│∘│∘│ │f│∘│∘│ │∘│∘│∘│ │ │ │k│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐ ┌─┬───┐ ┌─┬─┬─┐ ┌─────┐ ┌─┬─┬─┐
│∘│∘│∘│ │d│ │ │ │∘│∘│ │ │m │ │∘│∘│∘│ │ u │ │∘│∘│∘│
├─┼─┼─┤ │ ├─┬─┤ ├─┼─┼─┤ ├─┘ │ │ ├─┼─┼─┤ │ │ ──┤ ├─┼─┼─┤
│∘│∘│∘│ │e│ │ │ │∘│ │ │ │ │l│ │∘│∘│∘│ │ │ v│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └───┴─┘ └─┴─┴─┘ └─┴───┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│∘│ │∘│∘│w│ │∘│∘│∘│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
exit ↓
See also: select hampton
Back to: contents
Back to: Workspaces