Maze generation

From Rosetta Code
Revision as of 16:35, 15 December 2010 by Rdm (talk | contribs) (J: add whitespace to get syntax highlighting to work properly)
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, using using the simple Depth-first search algorithm.

See also Maze solving.

J

This algorithm allows almost no parallelism. So, while it might be "simple", generating very large mazes this way will not be necessarily efficient to implement on future (highly parallel) systems. That said, perhaps mazes with hundreds of thousands of cells are not very likely to be needed by anyone.

Anyways, based on the picolisp implementation, except without any relevant grid support:

<lang j>maze=:4 :0

 horiz=. 0$~x,y-1
 verti=. 0$~(x-1),y
 unvisited=. 0,0,~|:0,0,~1$~y,x
 path=.,:here=. ?x,y
 while. 1 e.,unvisited do.
   unvisited=.0 (<here+1)} unvisited
   neighbors=. here+"1 (,-)=0 1
   neighbors=. neighbors #~ (<"1 neighbors+1) {unvisited
   if.#neighbors do.
     next=. ({~ ?@#) neighbors
     if.{.next=here
     do. horiz=.1 (<-:here+next-0 1)} horiz
     else. verti=. 1 (<-:here+next-1 0)} verti end.
     path=.path,here=.next
   else.
     here=.{:path
     path=.}:path
   end.
 end.
 horiz;verti

)

display=:3 :0

 size=. >.&$&>/y
 text=. (}:1 3$~2*1+{:size)#"1":size$<' '
 'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y
 ' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text

)</lang>

The result of maze is a pair of arrays: one for open "doors" in the horizontal direction and the other for open "doors" in the vertical direction. The entry and exit doors are not represented by maze -- they are implicitly defined and are implemented in display.

Example use (with ascii box drawing enabled):

<lang j> display 8 maze 11 + +---+---+---+---+---+---+---+---+---+---+ | | | | | + + + + +---+ + +---+---+ + + | | | | | | | | + +---+---+ + +---+---+---+ + + + | | | | | | | +---+ +---+ + + +---+ + +---+---+ | | | | | | | + + +---+---+ +---+ + +---+---+ + | | | | | | | | | + +---+ + + + + +---+---+ + + | | | | | + +---+---+---+---+---+---+---+ +---+ + | | | | | | | | | + + + + + + + + +---+ + + | | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>

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 16 12))
    +   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 12 |   |           |           |               |                   |
    +   +   +   +   +   +---+   +   +---+---+   +   +---+   +---+   +
 11 |       |   |       |   |       |   |       |   |       |       |
    +   +---+   +---+---+   +---+---+   +   +---+---+   +---+   +---+
 10 |   |   |   |           |       |       |           |       |   |
    +   +   +   +---+   +   +   +   +   +---+---+   +---+   +---+   +
  9 |       |       |   |   |   |       |       |   |       |       |
    +   +---+---+   +   +---+   +---+---+   +   +   +   +---+   +   +
  8 |   |       |   |           |           |       |   |       |   |
    +   +   +   +   +   +---+---+   +---+   +---+---+   +---+   +   +
  7 |   |   |       |           |       |       |       |       |   |
    +---+   +---+---+---+---+   +---+   +---+   +   +---+   +---+   +
  6 |   |       |           |   |       |   |   |           |   |   |
    +   +---+   +---+   +---+   +   +---+   +   +---+---+---+   +   +
  5 |       |       |           |           |   |               |   |
    +---+   +---+   +---+   +---+   +---+---+   +   +---+   +---+   +
  4 |   |       |       |       |   |       |   |       |   |       |
    +   +---+   +---+   +---+   +---+   +   +   +---+---+   +   +---+
  3 |       |       |   |   |           |   |           |   |       |
    +   +---+---+   +   +   +---+---+---+   +---+   +   +   +---+   +
  2 |       |       |   |   |           |       |   |   |           |
    +   +   +   +---+   +   +   +---+   +---+   +---+   +   +---+---+
  1 |   |               |           |                   |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p