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