Maze generation: Difference between revisions
m (Using an interwiki link) |
(J: document major data structure) |
||
Line 38:
' ' (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 <code>maze</code> 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 <code>maze</code> -- they are implicitly defined and are implemented in <code>display</code>.
Example use (with ascii box drawing enabled):
|
Revision as of 18:45, 14 December 2010
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.
J
This algorithm allows almost no parallelism. So, while it might be "simple", it will not be necessarily efficient to implement on future (highly parallel) systems.
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 12 maze 16 + +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | + +---+---+---+---+ + + +---+---+ +---+ +---+---+ + | | | | | | | | | +---+---+ + +---+---+ + + +---+---+ +---+---+ + + | | | | | | | | | + +---+ +---+---+ + + + + +---+---+ + +---+ + | | | | | | | | | | + +---+---+---+ + +---+---+ + + + +---+---+---+---+ | | | | | | | | | | + + + +---+---+ +---+ +---+ + +---+---+---+ + + | | | | | | | + + +---+---+---+---+---+---+ +---+---+ + +---+---+ + | | | | | | | | | + +---+---+---+---+ + + + + + + + + +---+---+ | | | | | | | | | | + + +---+ + + + +---+---+ +---+---+---+---+ +---+ | | | | | | | | | + + + +---+ +---+ + +---+ +---+---+---+---+---+ + | | | | | | | | | | + +---+ + + + +---+ +---+---+ +---+ + + +---+ | | | | | | | | | | | | +---+ + + + + +---+---+ + +---+ +---+---+---+ + | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</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