Maze generation: Difference between revisions
(→Tcl: Added implementation) |
m (→{{header|Tcl}}: tinkering) |
||
Line 235: | Line 235: | ||
{{trans|Javascript}} |
{{trans|Javascript}} |
||
<lang tcl>package require Tcl 8.5 |
<lang tcl>package require Tcl 8.5 |
||
# Helper to pick a random number |
|||
proc rand n {expr {int(rand() * $n)}} |
|||
# Helper to pick a random element of a list |
# Helper to pick a random element of a list |
||
proc pick list { |
proc pick list { |
||
lindex $list [ |
lindex $list [rand [llength $list]] |
||
} |
|||
⚫ | |||
⚫ | |||
lindex $v [expr {$x+1}] [expr {$y+1}] |
|||
} |
} |
||
⚫ | |||
⚫ | |||
# Helper to write into a list of lists (with offsets) |
# Helper to write into a list of lists (with offsets) |
||
proc unvisited= {x y value} { |
proc unvisited= {x y value} { |
||
Line 250: | Line 250: | ||
# Maze builder; returns a dictionary |
# Maze builder; returns a dictionary |
||
proc maze { |
proc maze {y x} { |
||
set n [expr {$x * $y - 1}] |
set n [expr {$x * $y - 1}] |
||
if {$n < 0} {error "illegal maze dimensions"} |
if {$n < 0} {error "illegal maze dimensions"} |
||
set horiz [lrepeat [expr {$x+1}] [lrepeat [expr {$y+1}] 0]] |
set horiz [set verti [lrepeat [expr {$x+1}] [lrepeat [expr {$y+1}] 0]]] |
||
set verti [lrepeat [expr {$x+1}] [lrepeat [expr {$y+1}] 0]] |
|||
⚫ | |||
set path [list $here] |
|||
set unvisited [lrepeat [expr {$x+2}] [lrepeat [expr {$y+2}] 0]] |
set unvisited [lrepeat [expr {$x+2}] [lrepeat [expr {$y+2}] 0]] |
||
⚫ | |||
for {set j 0} {$j < $x} {incr j} { |
for {set j 0} {$j < $x} {incr j} { |
||
for {set k 0} {$k < $y} {incr k} { |
for {set k 0} {$k < $y} {incr k} { |
||
Line 263: | Line 261: | ||
} |
} |
||
} |
} |
||
while {0 < $n} { |
while {0 < $n} { |
||
lassign $here hx hy |
lassign $here hx hy |
||
set neighbours {} |
set neighbours {} |
||
foreach {dx dy} {1 0 0 1 -1 0 |
foreach {dx dy} {1 0 0 1 -1 0 0 -1} { |
||
if {idx($unvisited, $hx+$dx, $hy+$dy)} { |
if {idx($unvisited, $hx+$dx+1, $hy+$dy+1)} { |
||
lappend neighbours [list [expr {$hx+$dx}] [expr {$hy+$dy}]] |
lappend neighbours [list [expr {$hx+$dx}] [expr {$hy+$dy}]] |
||
} |
} |
||
} |
} |
||
if {[llength $neighbours]} { |
if {[llength $neighbours]} { |
||
⚫ | |||
lassign [set here [pick $neighbours]] nx ny |
lassign [set here [pick $neighbours]] nx ny |
||
unvisited= $nx $ny 0 |
unvisited= $nx $ny 0 |
||
if {$nx == $hx} { |
if {$nx == $hx} { |
||
lset horiz $nx [expr {min($ny, $hy)}] 1 |
|||
lset horiz $nx $py 1 |
|||
} else { |
} else { |
||
lset verti [expr {min($nx, $hx)}] $ny 1 |
|||
lset verti $px $ny 1 |
|||
} |
} |
||
lappend |
lappend stack $here |
||
⚫ | |||
} else { |
} else { |
||
set here [lindex $ |
set here [lindex $stack end] |
||
set |
set stack [lrange $stack 0 end-1] |
||
} |
} |
||
} |
} |
||
Line 311: | Line 307: | ||
} |
} |
||
} |
} |
||
if {!$j} { |
if {!$j} { |
||
lappend text [string replace $line 1 3 " "] |
|||
} elseif {$x*2-1 == $j} { |
|||
lappend text [string replace $line end end " "] |
|||
} else { |
|||
lappend text $line |
|||
} |
|||
} |
} |
||
} |
} |
||
return [join $text \n] |
return [join $text \n] |
||
} |
} |
||
# Demonstration |
# Demonstration |
||
puts [display [maze |
puts [display [maze 11 8]]</lang> |
||
Output: |
Output: |
||
<pre> |
<pre> |
Revision as of 17:14, 18 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.
- Start at a random cell.
- Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
- If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.
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 millions of cells are not very likely to be needed to be generated quickly.
Anyways, based on the picolisp implementation, except without any relevant grid support:
<lang j>maze=:4 :0
assert.0<:n=.<:x*y horiz=. 0$~x,y-1 verti=. 0$~(x-1),y path=.,:here=. ?x,y unvisited=.0 (<here+1)} 0,0,~|:0,0,~1$~y,x while.n do. neighbors=. here+"1 (,-)=0 1 neighbors=. neighbors #~ (<"1 neighbors+1) {unvisited if.#neighbors do. n=.n-1 next=. ({~ ?@#) neighbors unvisited=.0 (<next+1)} unvisited 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>
JavaScript
Based on the J implementation.
<lang javascript>function maze(x,y) { var n=x*y-1; if (n<0) {alert("illegal maze dimensions");return;} var horiz=[]; for (var j= 0; j<x+1; j++) horiz[j]= []; var verti=[]; for (var j= 0; j<x+1; j++) verti[j]= []; var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)]; var path= [here]; var unvisited= []; for (var j= 0; j<x+2; j++) { unvisited[j]= []; for (var k= 0; k<y+1; k++) unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1)); } while (0<n) { var potential= [[here[0]+1, here[1]], [here[0],here[1]+1], [here[0]-1, here[1]], [here[0],here[1]-1]]; var neighbors= []; for (var j= 0; j < 4; j++) if (unvisited[potential[j][0]+1][potential[j][1]+1]) neighbors.push(potential[j]); if (neighbors.length) { n= n-1; next= neighbors[Math.floor(Math.random()*neighbors.length)]; unvisited[next[0]+1][next[1]+1]= false; if (next[0] == here[0]) horiz[next[0]][(next[1]+here[1]-1)/2]= true; else verti[(next[0]+here[0]-1)/2][next[1]]= true; path.push(here= next); } else here= path.pop(); } return ({x: x, y: y, horiz: horiz, verti: verti}); }
function display(m) {
var text= [];
for (var j= 0; j<m.x*2+1; j++) {
var line= [];
if (0 == j%2)
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
line[k]= '+';
else {
if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
line[k]= ' ';
else
line[k]= '-';
}
else
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4) {
if (k>0 && m.horiz[(j-1)/2][k/4-1])
line[k]= ' ';
else
line[k]= '|';
} else
line[k]= ' ';
if (0 == j) line[1]= line[2]= line[3]= ' ';
if (m.x*2-1 == j) line[4*m.y]= ' ';
text.push(line.join()+'\r\n');
}
return text.join();
}</lang>
Example use:
<lang html><html><head><title></title></head><body>
</body></html>
<script type="text/javascript"> /* ABOVE CODE GOES HERE */ document.getElementById('out').innerHTML= display(maze(8,11)); </script></lang>
produced:
<lang>+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ + +---+ + +---+---+ + + | | | | | | | | + + + +---+ +---+ +---+---+ + + | | | | | | | + +---+ +---+---+---+---+---+ + + + | | | | | | +---+ +---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+---+---+---+---+ + + + | | | | | | + +---+---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+ +---+---+ + + +---+ | | | | +---+---+---+---+---+---+---+---+---+---+---+</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)) ) ) ) ) ) ) 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
Tcl
<lang tcl>package require Tcl 8.5
- Helper to pick a random number
proc rand n {expr {int(rand() * $n)}}
- Helper to pick a random element of a list
proc pick list {
lindex $list [rand [llength $list]]
}
- Helper _function_ to index into a list of lists
proc tcl::mathfunc::idx {v x y} {lindex $v $x $y}
- Helper to write into a list of lists (with offsets)
proc unvisited= {x y value} {
upvar 1 unvisited u lset u [expr {$x+1}] [expr {$y+1}] $value
}
- Maze builder; returns a dictionary
proc maze {y x} {
set n [expr {$x * $y - 1}] if {$n < 0} {error "illegal maze dimensions"} set horiz [set verti [lrepeat [expr {$x+1}] [lrepeat [expr {$y+1}] 0]]] set unvisited [lrepeat [expr {$x+2}] [lrepeat [expr {$y+2}] 0]] lappend stack [set here [list [rand $x] [rand $y]]] for {set j 0} {$j < $x} {incr j} {
for {set k 0} {$k < $y} {incr k} { unvisited= $j $k [expr {$here ne [list $j $k]}] }
} while {0 < $n} {
lassign $here hx hy set neighbours {} foreach {dx dy} {1 0 0 1 -1 0 0 -1} { if {idx($unvisited, $hx+$dx+1, $hy+$dy+1)} { lappend neighbours [list [expr {$hx+$dx}] [expr {$hy+$dy}]] } } if {[llength $neighbours]} { lassign [set here [pick $neighbours]] nx ny unvisited= $nx $ny 0 if {$nx == $hx} { lset horiz $nx [expr {min($ny, $hy)}] 1 } else { lset verti [expr {min($nx, $hx)}] $ny 1 } lappend stack $here incr n -1 } else { set here [lindex $stack end] set stack [lrange $stack 0 end-1] }
} return [dict create x $x y $y horiz $horiz verti $verti]
}
- Maze displayer; takes a maze dictionary
proc display {m} {
set text {} dict with m {
for {set j 0} {$j < $x*2+1} {incr j} { set line {} for {set k 0} {$k < $y*4+1} {incr k} { if {$j%2 && ($k%4 || $k && idx($horiz, ($j-1)/2, $k/4-1))} { append line " " } elseif {$j%2} { append line "|" } elseif {0 == $k%4} { append line "+" } elseif {$j && idx($verti, $j/2-1, $k/4)} { append line " " } else { append line "-" } } if {!$j} { lappend text [string replace $line 1 3 " "] } elseif {$x*2-1 == $j} { lappend text [string replace $line end end " "] } else { lappend text $line } }
} return [join $text \n]
}
- Demonstration
puts [display [maze 11 8]]</lang> Output:
+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ +---+---+ + +---+ +---+ + | | | | | | + + +---+ +---+---+ +---+ + + + | | | | | | | | + +---+ +---+---+---+ + + + + + | | | | | | | | + + + + +---+---+ + +---+---+ + | | | | | | | | +---+---+---+---+ + +---+ + + +---+ | | | | | | | | + +---+---+ + + + + + +---+ + | | | | | | | | +---+ + +---+---+---+---+ + +---+ + | | +---+---+---+---+---+---+---+---+---+---+---+