Maze generation: Difference between revisions
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 |
|||
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. |
while.1 e.,unvisited do. |
||
unvisited=.0 (< |
unvisited=.0 (<here+1)} unvisited |
||
neighbors=. here+"1 (,-)0 1 |
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 |
do. horiz=.1 (<-:here+next-0 1)} horiz |
||
else.verti=. 1 (<-:here+next- |
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;verti |
|||
) |
) |
||
display=:3 :0 |
display=:3 :0 |
||
size=. |
size=. >.&$&>/y |
||
text=. (}:1 3$~2*1+{:size)#"1":size$<' ' |
text=. (}:1 3$~2*1+{:size)#"1":size$<' ' |
||
'hdoor vdoor'=. 2 4 |
'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> |
)</lang> |
||
| Line 43: | Line 43: | ||
<lang j> display 12 maze 16 |
<lang j> display 12 maze 16 |
||
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |
||
| | |
| | | | | |
||
+ + |
+ +---+---+---+---+ + + +---+---+ +---+ +---+---+ + |
||
| |
| | | | | | | | | |
||
+ |
+---+---+ + +---+---+ + + +---+---+ +---+---+ + + |
||
| |
| | | | | | | | | |
||
+ +---+---+---+ + |
+ +---+ +---+---+ + + + + +---+---+ + +---+ + |
||
| |
| | | | | | | | | | |
||
+ +---+---+---+ + +---+---+ + + + +---+---+---+---+ |
|||
| | |
| | | | | | | | | | |
||
+ + +---+---+ +---+---+ + +--- |
+ + + +---+---+ +---+ +---+ + +---+---+---+ + + |
||
| | |
| | | | | | | |
||
+ +---+---+ |
+ + +---+---+---+---+---+---+ +---+---+ + +---+---+ + |
||
| | | | | | | | | |
|||
+---+---+ + + |
+ +---+---+---+---+ + + + + + + + + +---+---+ |
||
| |
| | | | | | | | | | |
||
+ +---+ + + +---+ +---+---+---+ |
+ + +---+ + + + +---+---+ +---+---+---+---+ +---+ |
||
| | |
| | | | | | | | | |
||
+ + + + |
+ + + +---+ +---+ + +---+ +---+---+---+---+---+ + |
||
| | | | |
| | | | | | | | | | |
||
+ + + + |
+ +---+ + + + +---+ +---+---+ +---+ + + +---+ |
||
| |
| | | | | | | | | | | | |
||
+ + + |
+---+ + + + + +---+---+ + +---+ +---+---+---+ + |
||
| |
| | | | |
||
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</lang> |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</lang> |
||