Simply A-maze-ing

One of many things I like about APL is that it’s fun to use for recreational computing. I will frequently happen upon an interesting problem, puzzle, or piece of code and consider how I might implement it in APL.

I was thinking about how to generate mazes for an idea I have about a game to help kids learn APL (that may be a topic for a future blog entry). Anyhow, I found an interesting web page about maze generating algorithms where the author found one, the “Growing Tree Algorithm“, to be of particular interest. His page included roughly 100 lines Ruby code to implement the algorithm. The algorithm can be boiled down to:

• Seed a list of visited cells with a cell selected at random
• While there are unvisited cells
  • If the current cell has any unvisited neighboring cells
    • Select one at random
    • Remove the wall between the cells
    • Add the new cell to the list of visited cells
  • Otherwise backtrack (drop from the visited cell list) until you find a cell with an unvisited neighbor

Here’s a clip of the algorithm implemented in APL building a 10×10 maze.
Notice how whenever it hits a “dead end” it backtracks to the last cell that hasn’t been visited.

What might an APL approach to this algorithm look like? How to represent the maze? My first thought was to separate the maze generation from the drawing. After an hour (or so 😉 ) of tinkering, I’d come up with something that seemed to work pretty well and took about a dozen lines of code.

When I originally thought about writing this blog entry, I was going to launch into a discussion of the code and I realized that it might get lengthy and (egad!) boring. So instead, I’ll highlight a couple of the clever bits, show you the core maze generation code, and point you at the complete namespace for your own amusement and experimentation.

First the clever bits (at least I hope they’re clever)…

• Represent the cells of the maze as an integer matrix where each element is an encoding of the walls surrounding each cell.  Use powers of 2 for the encoding.
• Precalculate the indices of the neighboring cells around each cell so the core loop only has to use indexing and no on-the-fly computation.
• Write a function to remove the common wall between two cells. I originally named the function “Reagan” (after President Reagan’s 1987 exhortation “Mr. Gorbachev, tear down this wall”), but in the spirit of political mindfulness, I renamed it “dewall”.

The core code for the maze generation looks like this:

∇ cells←maze size;valid;neighbors;dewall;visited;current;n;choices;next
 ⍝ Maze - modeled from http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
 ⍝ BPB  - Dec2014
 ⍝ size  - size of the maze in rows/cols
 ⍝ cells   - (2⍴size) integer matrix describing the walls around each cell using powers of 2
 ⍝       1
 ⍝     ┌───┐         ┌───┐
 ⍝   8 │   │ 2       │   │ = 11 = 1 + 2 + 8
 ⍝     └───┘
 ⍝       4
  size←2⍴size  ⍝ set size to square if singleton supplied as argument     

  valid←{{⍵/⍨⍵≢¨⊂⍬}size∘{(0∊⍵)⍱⍵∨.>⍺:⍵ ⋄ ⍬}¨⍵} ⍝ determine if a maze coordinate is valid
  neighbors←valid¨↓(⍳size)∘.+,1 ¯1∘.×1 0⌽¨⊂1 0 ⍝ calculate neighbors for each cell
     
  dewall←{{⍵[2]=0:{(1=⍵)⌽4 1}⍵[1] ⋄ {(1=⍵)⌽2 8}⍵[2]}⍺-⍵}  ⍝ remove wall between cells
     
  cells←size⍴15 ⍝ all cells start with 4 walls
     
  visited←,⊂?size ⍝ random starting cell
     
  :While 15∊cells       ⍝ while we still have cells to examine
      current←1↑visited   ⍝ pop the most recent cell
      :If 0=n←⍴choices←cells{⍵/⍨15=⍺[⍵]}current⊃neighbors ⍝ does it have any unvisited neighbors?
          visited↓⍨←1       ⍝ if none, backtrack
      :Else
          visited,⍨←next←choices[?n] ⍝ otherwise, add the new cell to the front of the list
          cells[next current]-←⊃next⊃.dewall current ⍝ update cell values for which wall was removed
      :EndIf
  :EndWhile
∇

You can get all the code in my maze generating namespace from GitHub. Save a local copy and use the SALT Load command to load it into your workspace, or just cut and paste it into your own namespace script with the editor. The maze namespace contains the following functions of interest:

      intmat←{animate} maze size

• animate is an optional Boolean to indicate whether to animate the maze generation
• size is the size (rows,cols) of the maze to generate; a single number generates a square maze
• intmat is the integer matrix representation of the maze

For example: mat←1 maze 10 animates and generates a 10×10 maze

      z←{line} draw intmat

• line is an optional Boolean that indicates:
  • 1 = use line-drawing characters
  • 0 = use ASCII characters
• intmat is an integer matrix representation of a maze
• z is the drawing of the maze in ASCII or line-drawing characters

For example: pic←1 draw mat produces a line-drawing of the maze generated in the example above

      z←html intmat

• intmat is an integer matrix representation of a maze
• z is the HTML necessary to render the maze in a web browser. Save it to a native file and open the file in your browser.

For example: h←html mat produces an HTML representation of the maze generated in the example above

Follow