# Converting a For() loop

Howdy. I’m trying to figure out why my implementation of @ignatz’s maze generation and rendering code as a single function that’s executed once per frame until all cells are drawn doesn’t do the exact same thing as his function. Here’s his original function for generating and drawing the maze:

``````function Maze:init(n,m,rnd)
local m=m or n --set m=n if not provided
local rnd=rnd or createRandomSeed()
math.randomseed(rnd)
t={} for i=1,n do t[i]={} end --create 2D maze
local stack={} --holds visited cells
local visitedCells=0
local totalCells=n*m
--set up little array to help with finding neighbours
local nb={{x=0,y=-1},{x=-1,y=0},{x=1,y=0},{x=0,y=1}}
--generate random starting cell
local cell={x=math.random(1,n),y=math.random(1,m)}
self.firstX,self.firstY=cell.x,cell.y
t[cell.x][cell.y]={1,1,1,1} -- top, left, right, bottom (1=wall)
visitedCells = visitedCells + 1
--loop through
while visitedCells<totalCells do
local prevVisitedCells=visitedCells
local r={1,2,3,4}
while #r~=0 do
--pick a random neighbour from the four directions
local rr=math.random(1,#r)
local s=r[rr]
table.remove(r,rr)
--work out x and y positions of neighbour
local x,y=cell.x+nb[s].x,cell.y+nb[s].y
--must be a valid cell that hasnt been visited
if x>0 and x<=n and y>0 and y<=m and t[x][y]==nil then
t[x][y]={1,1,1,1} -- top, right,bottom,left (1=wall)
t[cell.x][cell.y][s]=0 --break down wall in current cell
t[x][y][5-s]=0 --and neighbour
visitedCells = visitedCells + 1
table.insert(stack,{x=cell.x,y=cell.y}) --add previous cell to stack in case we need it
cell.x,cell.y=x,y --make neighbour the current cell
break
end
end
if prevVisitedCells==visitedCells then
--no unvisited neighbours found, go back to previous cell from stack
cell.x,cell.y=stack[#stack].x,stack[#stack].y
table.remove(stack,#stack)
end
end
self.maze=t
end

function createMaze()
w,h=Size,Size
m=Maze(w,h) --create maze
z=m.maze --get resulting maze
--calculate size of squares that fit on screen, not greater than 40
local sx=(WIDTH-offset.x*2)/w
local sy=(HEIGHT-offset.y*2)/h
s=math.min(sx,sy,40)
path=nil --solution
end

function draw()
background(40, 40, 50)
strokeWidth(1)
stroke(255)
if s==nil then return end

pushStyle()
pushMatrix()
--move drawing start position to bottom left of maze
--then all future code can assume maze starts at 0,0
--the only tricky thing is our maze cells have 1,1 at top left
--but our screen has 0,0 at bottom left, ie y is upside down
translate(offset.x,offset.y)
topy=s*h --top of maze
for i=1,w do
for j=1,h do
local x,y=(i-1)*s,topy-(j-1)*s
--each cell has info about all its walls but if we draw them all
--we would draw most of them twice because they belong to two cells
--the most efficient is just to draw the top and left walls of each cell
--which only leaves out the very bottom row and extreme right hand column
--which we can deal with afterwards
if z[i][j][1]==1 then line(x,y,x+s,y) end
if z[i][j][2]==1 then line(x,y,x,y-s) end
end
end
--now do bottom row
for i=1,w do
if z[i][h][4]==1 then
local x,y=(i-1)*s,topy-h*s
line(x,y,x+s,y)
end
end
--and right hand column
for j=1,h do
if z[w][j][3]==1 then
local x,y=w*s,topy-(j-1)*s
line(x,y,x,y-s)
end
end
--draw solution if available
strokeWidth(2)
stroke(255,0,0)
if path~=nil then
for i=2,#path do
x1,y1=(path[i-1].x-.5)*s,topy-(path[i-1].y-.5)*s
x2,y2=(path[i].x-.5)*s,topy-(path[i].y-.5)*s
line(x1,y1,x2,y2)
end
end
popMatrix()
popStyle()
end

``````

here’s my implementation as a function that’s called once per frame until visitedCells==totalCells:

``````function Maze2:init(n, m, rnd, size )
--sets up everything so you can call maze:draw(), which generates 1 cell at a time
--set up dimensions
self.rows = n
self.columns = m or self.rows
local rnd=rnd or createRandomSeed()
math.randomseed(rnd)
--set up maze table
self.maze={} for i=1,n do self.maze[i]={} end --create 2D maze
self.stack={} --holds visited cells
self.visitedCells=0
self.totalCells = self.rows * self.columns
--our random starting cell
self.lastCell = {x=math.random(1,self.columns),y=math.random(1,self.rows)}
self.startX = self.lastCell.x --do we need this?
self.startY = self.lastCell.y --do we need this?
--set up first cell's walls
self.maze[self.lastCell.x][self.lastCell.y] = {1,1,1,1}
self.stack[1] = {x=self.lastCell.x, y=self.lastCell.y }
self.visitedCells = self.visitedCells + 1
--set up cell size
local sx=(WIDTH-offset.x*2)/size
local sy=(HEIGHT-offset.y*2)/size
self.cellSize=math.min(sx,sy,40)
self.topY = self.cellSize*size --top of maze
self.numCells = size
self.context = image(WIDTH, HEIGHT) --where we do our drawing
self.removedFromStack = 0
--self:createUnprocessedMaze()
end

function Maze2:createAndDrawCell(cell, maze, context)
--given cell, generate neighboring cells
--cell should always be self.lastCell.
print( "Maze2:createAndDrawCell(", cell, maze, ")\
", cell.x, cell.y )
local result = false
local r = {1,2,3,4}
local nb={{x=0,y=-1},{x=-1,y=0},{x=1,y=0},{x=0,y=1}}
while( #r ~= 0 ) do
local side = self:getAndRemoveRandomElm( r )
local x, y = cell.x+nb[ side ].x, cell.y+nb[ side ].y
if( x>0 and x<=self.rows and
y>0 and y<=self.columns and
maze[x][y] == nil ) then
maze[x][y] = {1,1,1,1}
maze[cell.x][cell.y][ side ] = 0
maze[x][y][5 - side ] = 0
self.visitedCells = self.visitedCells + 1
table.insert(self.stack,{x=self.lastCell.x,y=self.lastCell.y}) --add previous cell to stack in case we need it
print( "    **stack length:", #self.stack )
self.removedFromStack = 0
self.lastCell = {x=x, y=y} --update lastCell to the neighbor we generated
result = true
if( x == 1 or cell.x == 1 ) then
--print( "new cell created @:" , x, y )
--print( "    walls: ", maze[x][y][1], maze[x][y][2], maze[x][y][3], maze[x][y][4] )
if( maze[x][y][2] == 0 or maze[cell.x][cell.y][2] == 0 ) then
print( "cell @ "..x..","..y.." or "..cell.x..","..cell.y.." has no left wall" )
end
end
if( cell.x == 1 ) then
--print( "old cell @:", cell.x, cell.y )
--print( "    walls:", maze[cell.x][cell.y][1], maze[cell.x][cell.y][2], maze[cell.x][cell.y][3], maze[cell.x][cell.y][4] )
end
--draw code:
pushStyle()
pushMatrix()
--move drawing start position to bottom left of maze
--then all future code can assume maze starts at 0,0
--the only tricky thing is our maze cells have 1,1 at top left
--but our screen has 0,0 at bottom left, ie y is upside down
setContext( context )
translate(offset.x,offset.y)

rectMode( CORNER )
noFill()
strokeWidth( 2 )
stroke( 255, 0, 0 ,255 )

local _x,_y=(x-1)*self.cellSize,self.topY-(y-1)*self.cellSize
--rect( _x, _y-self.cellSize, self.cellSize, self.cellSize )

strokeWidth(3)
stroke(0, 0, 0)
--print( "Maze:createAndDrawCell() new cell row/col, x/y\
", x, y, _x, _y )

--print( "i, j", i, j, "x, y", x, y )
--each cell has info about all its walls but if we draw them all
--we would draw most of them twice because they belong to two cells
--the most efficient is just to draw the top and left walls of each cell
--which only leaves out the very bottom row and extreme right hand column
--which we can deal with afterwards
if maze[cell.x][cell.y][1]==1 then line(_x,_y,_x+self.cellSize,_y) end
if maze[cell.x][cell.y][2]==1 then line(_x,_y,_x,_y-self.cellSize) end
--line(x,y,x,y-s)
if( cell.x == self.columns ) then
if( maze[self.columns][cell.y][3] == 1 ) then
_x,_y=self.numCells*self.cellSize,self.topY-(x-1)*self.cellSize
line(_x,_y,_x,_y-self.cellSize)
end
end
--bottom row
--line(x,y,x+s,y)
if( cell.y == self.rows ) then
if( maze[cell.x][self.rows][4]==1 and cell.y == self.rows ) then
_x,_y=(x-1)*self.cellSize,self.topY-self.numCells*self.cellSize
line(_x,_y,_x+self.cellSize,_y)
end --line(x,y,x+s,y)
end

popMatrix()
popStyle()
setContext()
break  --only make 1 neighbor at a time
end
end

return result
end

function Maze2:draw()
--local cell = {x=math.random(1,n),y=math.random(1,m)}
local cellDrawn = self:createAndDrawCell(self.lastCell, self.maze, self.context)
if( cellDrawn == true ) then
--self.lastCell = self.stack[#self.stack] -- last element is most recently created cell
print( "Maze2:draw() result:", self.lastCell.x, self.lastCell.y )
else
--no unvisited neighbours found, go back to previous cell from stack
--use previous cell when we try to draw again
print( "Maze2:draw() no open neighbors! ", self.lastCell, self.removedFromStack, #self.stack )
--self.lastCell = self.stack[#self.stack]
self.lastCell = table.remove(self.stack )
print( "last Cell:", self.lastCell )
self.removedFromStack = self.removedFromStack + 1
end
end

function Maze2:getAndRemoveRandomElm(tbl)
local idx = math.random(1, #tbl)
local elem = tbl[idx]
table.remove(tbl, idx)
--print( "Maze:getAndRemoveRandomElm() result:", elem )
return elem
end

function draw()
background(40, 40, 50)

if( doCreateMaze == true ) then
maze:draw()

--doCreateMaze = false
--maze:printMazeInfo()
if( maze.visitedCells == maze.totalCells ) then
doCreateMaze = false
print( "finished making maze" )
end
end

--translate( offset.x, offset.y )
if( maze ~= nil ) then
if( maze.context ~= nil ) then
spriteMode(CORNER)
sprite(maze.context)
fill( 255, 0, 0 )
translate( offset.x, offset.y )
ellipse(maze.startX * maze.cellSize, maze.startY*maze.cellSize, 20 )
else
print( "no maze.context" )
end
end
end

``````

I should preface that my code works about 90% of the way. My mazes just don’t look like the ones his code generates. I also have this project posted on CC if you wanna look at it that way.

I would have tried using a coroutine to pause the original for loop, which might require only minimal changes to the code. You have made so many changes, it is a debugging nightmare.

@matkatmusic If you need another maze creation example, try here.

``````http://codea.io/talk/discussion/3369/maze-creation-with-animation#Item_8
``````

ok, so let’s reduce it down to:

``````while( #r ~= 0 ) do
--bunch of stuff
if( withinBounds(x,y,m,n) and t[x][y] ~= nil ) then
--bunch of more stuff
break
end
end
``````

How do you turn this while() loop into a function that’s called once per frame() until the while() condition is met?

@dave1707 that’s great! runs a little slow the larger it gets tho. that’s something I solved in my version. instead of doing a huge for() loop drawing a bunch of lines each frame, it writes the lines to an image() and the image gets rendered as a sprite. I’ll play around with your code and see what I come up with. Thanks for sharing the link!

@matkatmusic That example was meant to run slow so you could watch the maze being created. If you want a faster one, try this.

EDIT: Removed unused code.

``````
function setup()
parameter.integer("dim",10,100,12,change)
setup1()
end

function change()
change=true
end

function setup1()
tab={vec2(0,1),vec2(1,0),vec2(0,-1),vec2(-1,0)}
tab1={3,4,1,2}
locations={}
square={}
size=WIDTH/(dim+5)
for z=1,dim*dim do
square[z]=nil
end
curr=vec2(math.random(dim),math.random(dim))
c=curr.x*dim+curr.y-dim
square[c]=vec4(1,1,1,1)
table.insert(locations,curr)
prevCurr=vec2(0,0)
while #locations>0 do
nextSquare()
if prev then
curr=locations[#locations]
table.remove(locations,#locations)
prevCurr=curr
else
if prevCurr.x>0 then
table.insert(locations,prevCurr)
prevCurr=vec2(0,0)
end
table.insert(locations,curr)
end
end
change=false
end

function draw()
background(40, 40, 50)
text("Tap screen for another "..dim.." x "..dim.." maze",WIDTH/2,HEIGHT-30)
if change then
return
end
stroke(255)
strokeWidth(1)
if #locations==0 then
square[1][4]=0
square[dim*dim][2]=0
stroke(255)
strokeWidth(2)
local v=0
for a=1,dim do
for b=1,dim do
v=v+1
if square[v].x==1 then -- top line
line(a*size,(b+1)*size,(a+1)*size,(b+1)*size)
end
if square[v].y==1 then -- right line
line((a+1)*size,b*size,(a+1)*size,(b+1)*size)
end
if square[v].z==1 then -- bottom line
line(a*size,b*size,(a+1)*size,b*size)
end
if square[v].w==1 then -- left line
line(a*size,b*size,a*size,(b+1)*size)
end
end
end
end
end

function nextSquare()
done=false
prev=false
side={1,2,3,4}
while not done do
rs=math.random(#side)
r=side[rs]
table.remove(side,rs)
nxt=curr+tab[r]
if nxt.x>=1 and nxt.x<=dim and nxt.y>=1 and nxt.y<=dim then
c=curr.x*dim+curr.y-dim
n=nxt.x*dim+nxt.y-dim
if square[n]==nil then
square[n]=vec4(1,1,1,1)
square[c][r]=0
square[n][tab1[r]]=0
curr=nxt
done=true
return
end
end
if #side==0 then
prev=true
done=true
end
end
end

function touched(t)
if t.state==BEGAN then
setup1()
end
end

``````

@meerkatmusic - see the link below for the way to “pause” code in a for a loop. Whether you end up using it or not in this example, I suggest it’s very useful to know about.

http://coolcodea.wordpress.com/2013/03/25/coroutines-or-how-to-report-progress-of-a-big-job/

@dave1707 Thanks for the update.

I took your code and created a hybrid. it precalcs the level, but still shows it figuring out the path. it’s way faster now. in fact, aside from the slowness of the precalc’ing, it ‘generates’ the maze really fast, regardless of the dimension:

``````supportedOrientations(LANDSCAPE_ANY)

function setup()
parameter.integer("dim",10,100,32)
parameter.action("create maze",setup1)
end

function setup1()
tab={vec2(0,1),vec2(1,0),vec2(0,-1),vec2(-1,0)}
tab1={3,4,1,2}
dots={}
locations={}
square={}
size=HEIGHT/(dim+5)
s2=size/2
s4=size/4
for z=1,dim*dim do
square[z]=vec4(1,1,1,1)
end
--generate a random current position
curr=vec2(math.random(dim),math.random(dim))
--store current position in locations table
table.insert(locations,curr)
--store current location into dots table, marked as red
table.insert(dots,vec3(curr.x,curr.y,2))
--set up initial previous location
prevCurr=vec2(0,0)
--preprocess the whole level
output.clear()
print( "total size:", dim*dim )
moves = {}
table.insert(moves, vec3(curr.x, curr.y, 2) )
while #locations>0 do
nextSquare()
if prev then
curr=locations[#locations]
table.insert(moves, vec3(curr.x, curr.y,1) )
table.remove(locations,#locations)
prevCurr=curr
else
if prevCurr.x>0 then
table.insert(locations,prevCurr)
table.insert(moves, vec3(curr.x, curr.y, 2) )
prevCurr=vec2(0,0)
end
table.insert(locations,curr)
table.insert(moves, vec3(curr.x, curr.y, 2) )
end
end

--draw the maze
mazeImg = image(WIDTH,HEIGHT)
setContext(mazeImg)
stroke(255)
strokeWidth(2)
for a=1, dim do
for b=1, dim do
-- top line
line(a*size,(b+1)*size,(a+1)*size,(b+1)*size)
-- right line
line((a+1)*size,b*size,(a+1)*size,(b+1)*size)
-- bottom line
line(a*size,b*size,(a+1)*size,b*size)
-- left line
line(a*size,b*size,a*size,(b+1)*size)
--end
end
end
setContext()
end

function draw()
background(40, 40, 50)
stroke(255)
strokeWidth(2)
--still got stuff to process
--print( "numLocations:", #locations )
--translate(20,20)
spriteMode( CORNER )
if( mazeImg ~= nil ) then sprite(mazeImg) end
if( moves == nil ) then
print( "no moves" )
elseif( #moves > 0 ) then
loc = table.remove( moves, 1 )
--print( loc.x, loc.y, loc.z, #moves )
setContext( mazeImg )
noStroke()
if( loc.z == 1 ) then
fill(0, 45, 255, 255)
elseif ( loc.z == 2 ) then
fill(255, 0, 45, 255)
end
ellipse(loc.x*size+s2,loc.y*size+s2,s4)
--now remove lines from grid.  draw them with the same color as the background
--find loc in square[]
stroke(40,40,50)
strokeWidth(2)
local c = loc.x*dim + loc.y-dim
if(square[c][1] == 0 ) then
line(loc.x*size,(loc.y+1)*size,(loc.x+1)*size,(loc.y+1)*size)
end
if(square[c][2] == 0 ) then
line((loc.x+1)*size,loc.y*size,(loc.x+1)*size,(loc.y+1)*size)
end
if(square[c][3] == 0 ) then
line(loc.x*size,loc.y*size,(loc.x+1)*size,loc.y*size)
end
if(square[c][4] == 0 ) then
line(loc.x*size,loc.y*size,loc.x*size,(loc.y+1)*size)
end

setContext()
else
--square[1][4]=0
--square[dim*dim][2]=0
--set lower left cell's left wall to 0
setContext(mazeImg)
loc=vec3(1,1,0)
stroke(40,40,50)
strokeWidth(2)
line(loc.x*size,loc.y*size,loc.x*size,(loc.y+1)*size)
--set upper right cell's right wall to 0
loc=vec3(dim,dim,0)
line((loc.x+1)*size,loc.y*size,(loc.x+1)*size,(loc.y+1)*size)
setContext()
fill(255)
text("Tap screen for another "..dim.." x "..dim.." maze",WIDTH/2,HEIGHT-size)
end

end

function nextSquare()
local done=false
prev=false
local side={0,0,0,0} --each side's wall flag = false
while not done do
--pick a random side
local r=math.random(4)
--set it's wall-processed flag to true
side[r]=1
--figure out which cell is next via vec2() + vec2()
--cur = current cell
--tab = table of vectors which define the math to select the cell next door
nxt=curr+tab[r]
--if nxt is within grid boundaries
if nxt.x>=1 and nxt.x<=dim and nxt.y>=1 and nxt.y<=dim then
--square is stored as a 1 dimensional table, not a 2D table
--figure out the location in square[] of our curr cell
local c=curr.x*dim+curr.y-dim
--figure out the location in square[] of our nxt cell
local n=nxt.x*dim+nxt.y-dim
--each cell can only have 3 walls max
local tn=square[n][1]+square[n][2]+square[n][3]+square[n][4]
--if cell has more than 3 walls
if tn>3 then
--set last wall flag for current cell to false
--this means we can pass from curr to nxt
square[c][r]=0
--set neighbor cell's corresponding wall flag to false
square[n][tab1[r]]=0
--set current to next
curr=nxt
--finished processing this cell, stop processing while()
done=true
return
end
end
--check the number of walls we've processed
local ts=side[1]+side[2]+side[3]+side[4]
if ts==4 then
--we have to backtrack
prev=true
--finished processing, stop while()
done=true
end
end
end

function touched(t)
if t.state==BEGAN then
setup1()
end
end
``````

next step, figure out why there are tiny gaps between each line, and do the same thing (show the processing in realtime) with the A* implementation by @ignatz

Hi @matkatmusic,

You may also want to look at http://codea.io/talk/discussion/2942/jumper-lightweight-fast-and-easy-to-use-pathfinding-library/p1

This is a library I ported to Codea which gives you a variety of pathfinding algorithms nicely wrapped up… It uses a binary heap for A* which makes it pretty quick…

Brookesi