Maze generation

From Rosetta Code
Revision as of 14:56, 14 December 2010 by rosettacode>Abu (Smaller example maze)
Maze generation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
This page uses content from Wikipedia. The original article was at Maze generation algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Generate and show a maze.

PicoLisp

This solution uses 'grid' from "lib/simul.l" to generate the two-dimensional structure. <lang PicoLisp>(load "@lib/simul.l")

(de maze (DX DY)

  (let Maze (grid DX DY)
     (let Fld (get Maze (rand 1 DX) (rand 1 DY))
        (recur (Fld)
           (for Dir (shuffle '((west . east) (east . west) (south . north) (north . south)))
              (with ((car Dir) Fld)
                 (unless (or (: west) (: east) (: south) (: north))
                    (put Fld (car Dir) This)
                    (put This (cdr Dir) Fld)
                    (recurse This) ) ) ) ) )
     (for (X . Col) Maze
        (for (Y . This) Col
           (set This
              (cons
                 (cons
                    (: west)
                    (or
                       (: east)
                       (and (= Y 1) (= X DX)) ) )
                 (cons
                    (: south)
                    (or
                       (: north)
                       (and (= X 1) (= Y DY)) ) ) ) )
           (=: west)
           (=: east)
           (=: south)
           (=: north) ) )
     Maze ) )

(de display (Maze)

  (disp Maze 0 '((This) "   ")) )</lang>

Output:

: (display (maze 18 6))
   +   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 6 |   |               |           |                           |   |       |
   +   +---+   +---+   +---+   +   +   +---+---+---+---+---+   +   +   +   +
 5 |       |       |           |   |       |           |       |       |   |
   +---+   +---+   +---+---+---+   +   +   +   +---+   +   +---+---+---+   +
 4 |   |       |       |           |   |   |   |   |       |               |
   +   +---+   +---+   +   +---+---+---+   +   +   +---+---+   +---+---+   +
 3 |       |       |   |       |           |   |               |   |       |
   +   +---+---+   +   +---+   +   +   +---+   +   +   +---+---+   +   +---+
 2 |       |       |   |   |   |   |   |   |   |   |       |       |   |   |
   +   +   +   +---+   +   +   +---+   +   +   +---+---+   +   +---+   +   +
 1 |   |               |               |                   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p   q   r