

 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)




Task

Generate and show a maze, 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.


 Related tasks
 Maze solving.


DEFINE TOP="0"
DEFINE RIGHT="1"
DEFINE BOTTOM="2"
DEFINE LEFT="3"
DEFINE WIDTH="160"
DEFINE HEIGHT="96"
 
DEFINE STACK_SIZE="5000"
BYTE ARRAY stack(STACK_SIZE)
INT stackSize
 
PROC InitStack()
  stackSize=0
RETURN
 
BYTE FUNC IsEmpty()
  IF stackSize=0 THEN
    RETURN (1)
  FI
RETURN (0)
 
BYTE FUNC IsFull()
  IF stackSize>=STACK_SIZE THEN
    RETURN (1)
  FI
RETURN (0)
 
PROC Push(BYTE x,y)
  IF IsFull() THEN Break() RETURN FI
  stack(stackSize)=x stackSize==+1
  stack(stackSize)=y stackSize==+1
RETURN
 
PROC Pop(BYTE POINTER x,y)
  IF IsEmpty() THEN Break() RETURN FI
  stackSize==-1 y^=stack(stackSize)
  stackSize==-1 x^=stack(stackSize)
RETURN
 
PROC FillScreen()
  BYTE POINTER ptr ;pointer to the screen memory
  INT screenSize=[3840]
 
  ptr=PeekC(88)
  SetBlock(ptr,screenSize,$55)
 
  Color=0
  Plot(0,HEIGHT-1) DrawTo(WIDTH-1,HEIGHT-1) DrawTo(WIDTH-1,0)
RETURN
 
PROC GetNeighbors(BYTE x,y BYTE ARRAY n BYTE POINTER count)
  DEFINE WALL="1"
 
  count^=0
  IF y>2 AND Locate(x,y-2)=WALL THEN
    n(count^)=TOP count^==+1
  FI
  IF x<WIDTH-3 AND Locate(x+2,y)=WALL THEN
    n(count^)=RIGHT count^==+1
  FI
  IF y<HEIGHT-3 AND Locate(x,y+2)=WALL THEN
    n(count^)=BOTTOM count^==+1
  FI
  IF x>2 AND Locate(x-2,y)=WALL THEN
    n(count^)=LEFT count^==+1
  FI
RETURN
 
PROC Maze(BYTE x,y)
  BYTE ARRAY stack,neighbors
  BYTE dir,nCount
 
  FillScreen()
 
  Color=2
  InitStack()
  Push(x,y)
  WHILE IsEmpty()=0
  DO
    Pop(@x,@y)
    GetNeighbors(x,y,neighbors,@nCount)
    IF nCount>0 THEN
      Push(x,y)
      Plot(x,y)
      dir=neighbors(Rand(nCount))
      IF dir=TOP THEN
        y==-2
      ELSEIF dir=RIGHT THEN
        x==+2
      ELSEIF dir=BOTTOM THEN
        y==+2
      ELSE
        x==-2
      FI
      DrawTo(x,y)
      Push(x,y)
    FI
  OD
RETURN
 
PROC Main()
  BYTE CH=$02FC,COLOR0=$02C4,COLOR1=$02C5
  BYTE x,y
 
  Graphics(7+16)
  COLOR0=$0A
  COLOR1=$04
 
  x=Rand((WIDTH RSH 1)-1) LSH 1+1
  y=Rand((HEIGHT RSH 1)-1) LSH 1+1
  Maze(x,y)
 
  DO UNTIL CH#$FF OD
  CH=$FF
RETURN