The maze is generated in a rectangular field of cells, each cell being an element in a 2-dimensional array. Each cell has 2 to 4 neighbour cells separated by horizontal and vertical walls. Cells may be "visited" by the algorithm or not. At the end of the procedure all cells have been visited. The algorithm in pseudo-code is as follows:
Select a (random) initial cell-> make this the "current" cell and mark it " visited"
WHILE there are non-visited cells, DO {
IF the current cell has non-visited neighbour cells, THEN {
choose (at random) one of the neighbour cells
eliminate the wall between both cells
push the current cell on the stack
make the chosen cell the current cell and mark it as visited
}
ELSE {
IF the stack is not empty, THEN {
pop a cell from the stack
make this the current cell
}
ELSE {
select a random non-visited cell
make this the current cell and mark it visited
}
}
Code: Select all
' generate a nr rows by nk columns maze
'
option base 1 ! randomize
input "number of rows : ":nr ! input "number of columns : ":nk
dim cel(nr,nk), hw(nr-1,nk), vw(nr,nk-1), buren(4,2), empty(40,2)
dim stack(nr*nk,2)
graphics ! graphics clear .8,.8,.8
draw color 0,0,0 ! fill color .8,.8,.8
cr=1 ! ck=1+rnd(nk) ! cel(cr,ck)=1 ! br=cr ! bk=ck ! flag=1
if nk>29 or nr>35 then ds=15 else ds=25
loop1:
if unvis(nr,nk,cel) then
nbuur=nburen(nr,nk,cr,ck,cel,buren)
if nbuur then
s=1+rnd(nbuur) ! sr=buren(s,1) ! sk=buren(s,2)
sp=sp+1 ! stack(sp,1)=cr ! stack(sp,2)=ck
wall(cr,ck,sr,sk,hw,vw)
cr=sr ! ck=sk ! cel(cr,ck)=1
if flag and cr=nr then ! er=cr ! ek=ck ! end if
else
if sp then
cr=stack(sp,1) ! ck=stack(sp,2) ! sp=sp-1
else
ne=empt(nr,nk,cel,empty) ! flag=0
s=1+rnd(ne) ! cr=empty(s,1) ! ck=empty(s,2)
cel(cr,ck)=1
end if
end if
else
goto loop2
end if
goto loop1
loop2:
' plotting the generated maze
ww=ds*nk ! hh=ds*nr ! draw size 3 ! graphics clear .8,.8,.8
draw line 20,50 to 20+ww,50 ! draw line 20,50+hh to 20+ww,50+hh
draw line 20,50 to 20,50+hh ! draw line 20+ww,50 to 20+ww,50+hh
draw size 2
for i=1 to nr-1 ! for j=1 to nk
if hw(i,j)=0 then draw line 20+ds*(j-1),50+ds*i to 20+ds*j,50+ds*i
next j ! next i
for i=1 to nr ! for j=1 to nk-1
if vw(i,j)=0 then draw line 20+ds*j,50+ds*(i-1) to 20+ds*j,50+ds*i
next j ! next i
draw text "v" at 22+ds*(bk-1),46
draw text "v" at 22+ds*(ek-1),44+ds*(nr-1)
end
def unvis(nr,nk,cel(,))
unvis=0
for i=1 to nr ! for j=1 to nk
if cel(i,j)=0 then
unvis=1 ! return
end if
next j ! next i
end def
def nburen(nr,nk,cr,ck,cel(,),buren(,))
nb=0
if cr>1 and cel(cr-1,ck)=0 then
nb=nb+1 ! buren(nb,1)=cr-1 ! buren(nb,2)=ck
end if
if cr<nr and cel(cr+1,ck)=0 then
nb=nb+1 ! buren(nb,1)=cr+1 ! buren(nb,2)=ck
end if
if ck>1 and cel(cr,ck-1)=0 then
nb=nb+1 ! buren(nb,1)=cr ! buren(nb,2)=ck-1
end if
if ck<nk and cel(cr,ck+1)=0 then
nb=nb+1 ! buren(nb,1)=cr ! buren(nb,2)=ck+1
end if
nburen=nb
end def
def wall(cr,ck,sr,sk,hw(,),vw(,))
if cr=sr then
if ck<sk then vw(cr,ck)=1 else vw(cr,sk)=1
end if
if ck=sk then
if cr<sr then hw(cr,ck)=1 else hw(sr,ck)=1
end if
end def
def empt(nr,nk,cel(,),empty(,))
ne=0
for i=1 to nr ! for j=1 to nk
if cel(i,j)=0 then
ne=ne+1 ! empty(ne,1)=i ! empty(ne,2)=j
end if
next j! next i
empt=ne
end def