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