Maze generation: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|J}}: Example maze is not solvable, but the solution is already marked "buggy")
Line 5: Line 5:
=={{header|J}}==
=={{header|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.
FIXME: buggy (this particular example is not solvable), not enough walls


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


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


display=:3 :0
display=:3 :0
size=. 2+$>{.y
size=. >.&$&>/y
text=. (}:1 3$~2*1+{:size)#"1":size$<' '
text=. (}:1 3$~2*1+{:size)#"1":size$<' '
'hdoor vdoor'=. 2 4 *L:0 (#&,{@;&i./@$)&.> y
'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y
2 4}._2 _4}.' ' (3 8+L:0 hdoor)} ' ' (vdoor+L:0"0/2 5;2 6;2 7)} text
' ' (0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text
)</lang>
)</lang>


Line 43: Line 43:
<lang j> display 12 maze 16
<lang j> display 12 maze 16
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | |
| | | | |
+ + + +---+ +---+---+ +---+ +---+ +---+---+---+ +
+ +---+---+---+---+ + + +---+---+ +---+ +---+---+ +
| | | | | | | | | |
| | | | | | | | |
+ + +---+ + + +---+ + + + +---+ + +---+ +
+---+---+ + +---+---+ + + +---+---+ +---+---+ + +
| | | | | | | | | | |
| | | | | | | | |
+ +---+---+---+ +---+---+---+---+---+ + + +---+ + +
+ +---+ +---+---+ + + + + +---+---+ + +---+ +
| | | | | | | | | |
| | | | | | | | | |
+---+ + +---+---+ +---+---+---+ + + +---+ +---+---+
+ +---+---+---+ + +---+---+ + + + +---+---+---+---+
| | | | | | | |
| | | | | | | | | |
+ + +---+---+ +---+---+ + +---+ +---+ +---+---+ +
+ + + +---+---+ +---+ +---+ + +---+---+---+ + +
| | | | | | | | |
| | | | | | |
+ +---+---+ +---+ + +---+ + +---+---+---+---+ + +
+ + +---+---+---+---+---+---+ +---+---+ + +---+---+ +
| | | | | | | | |
| | | | | | | | |
+---+---+ + +---+ +---+ +---+---+---+ + +---+---+ +
+ +---+---+---+---+ + + + + + + + + +---+---+
| | | | | | | | |
| | | | | | | | | |
+ +---+ + + +---+ +---+---+---+ + + + + + +
+ + +---+ + + + +---+---+ +---+---+---+---+ +---+
| | | | | | | | | |
| | | | | | | | |
+ + + + + + + + + +---+---+---+---+---+---+ +
+ + + +---+ +---+ + +---+ +---+---+---+---+---+ +
| | | | | | | | | |
| | | | | | | | | |
+ + + +---+ + +---+---+ + + +---+---+ + + +
+ +---+ + + + +---+ +---+---+ +---+ + + +---+
| | | | | | | | | | | |
| | | | | | | | | | | |
+ + +---+ +---+ +---+---+ +---+ +---+---+---+ + +
+---+ + + + + +---+---+ + +---+ +---+---+---+ +
| | | | | |
| | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</lang>
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</lang>



Revision as of 18:08, 14 December 2010

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.

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
 ' ' (0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text

)</lang>

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