Support Forum / Форум поддержки

Posted: **Fri Jun 21, 2013 9:22 am**

Maze algorithm

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

Support Forum / Форум поддержки

Maze generator (algorithm and program)

Maze generator (algorithm and program)