PICO-8: Maze Algorithm Tutorial

Keys

Z - move to the next step
X - switch on/off auto or reset the maze.

---

Code

Below is a heavily-commented implementation of the actual algorithm used in the tutorial above. It's called the Growing Tree Maze Algorithm if you'd like to learn more about it.

Note: If you'd like to implement this code, you need to draw a wall in sprite #001 and a floor in sprite #002.

function _init()
 w,h=13,13 --must be odd numbers!
 gen() --make a maze!
end
function _update()    
 if (btnp(5)) gen() --reset
end
function _draw()
 cls()
 --center the maze and draw it
 center_x=(128-(w+2)*8)/2
 map(0,0,center_x,0)
 print("press \151 to reset",30,122,5)
end
function gen()
 m={} --empty maze of all walls
 for i=1,w do --go across
  m[i]={}
  for j=1,h do --go down
   m[i][j]=true --true=wall
  end
 end
 c={} --cells we're tracking
    
 --start in a random spot
 add_c(rndbi(0,(w-1)/2)*2+1,rndbi(1,(h-1)/2)*2+1)
 m[c[1].x][c[1].y]=false
 carve()
 set_map_tiles()
end
function carve()
 --easy math to calculate
 --neighboring cells and
 --cells opposite the one
 --we're working with
 dx,dy,op={-2,2,0,0},{0,0,-2,2},{2,-2,2,-2}
 --if the cell list isn't empty
 while (#c>0) do    
  cc=c[#c] --get the last cell
        
  --get a random list of dirs
  rd=get_rnd_dirs()
        
  --check each direction
  for d in all(rd) do
   --get the cell in that dir
   nx,ny=cc.x+dx[d],cc.y+dy[d]
            
   --if that cell is uncarved 
   --and not an edge wall
   if (nx>=1 and nx<=w and ny>=1 and ny<=h and m[nx][ny]) then    
    --carve a path in that dir
    m[cc.x+(dx[d]/2)][cc.y+(dy[d]/2)]=false
    m[nx][ny]=false
    --new cell goes on the list
    add_c(nx,ny)
    --if we found and carved a
    --new path, we're good. no
    --need to check other dirs
    break
   end
            
   --if we checked that dir
   --and couldn't use that dir,
   --take the dir off the list
   --and check the next dir
   del(rd,d)
  end
        
  --if we checked all dirs and
  --couldn't find an open path
  --to carve, we're done with
  --that cell
  if (#rd<1) then
   del(c,cc)        
  end
 end
end
--add a cell to the list of
--cells we're working with
function add_c(x,y)
 local new_c={}
 new_c.x=x
 new_c.y=y
 add(c,new_c)
end
--get a random \139\145\148\131 list
function get_rnd_dirs()
 local dirs={1,2,3,4}
 local rnd_dirs={}
 for i=1,4 do
  local rnd_dir=rndbi(1,#dirs)
  add(rnd_dirs,dirs[rnd_dir])
  del(dirs,dirs[rnd_dir])
 end
 return rnd_dirs
end
function set_map_tiles()    
 --maze border
 for i=0,w+1 do --top/bottom
  mset(i,0,1)
  mset(i,h+1,1) 
 end
 for j=1,h do   --left/right
  mset(0,j,1)
  mset(w+1,j,1)
 end
    
 --maze tiles
 for i=1,w do for j=1,h do
  if (m[i][j]) then
   mset(i,j,1)
  else
   mset(i,j,2)
  end
        
  --simpler version using a
  --ternary operator:
  --mset(i,j,m[i][j] and 1 or 2)
 end end
end
--random integer (h inclusive)
function rndbi(l,h) 
 return flr(rnd(h+1-l))+l
end