Simple a-star path finding for dungeon crawler example

A simple implementation of path finding using the a star algorithm. Coded from pseudo code found on the web so may well be sub optimal but was a useful learning experience for me. Thought I’d share.

--# Main
-- Simple dungeon crawler movement
-- by Graeme West
--Pseudocode for pathfinding from
--http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
displayMode(FULLSCREEN)
-- Use this function to perform your initial setup
function setup()
    dmeasure=1 --distance measure used, 1 manhatten, 2 euclidean
    goal=vec2(15,8)
    hero=vec2(15,8)
    mapcentre=vec2(WIDTH/2,HEIGHT/2)

    movecount=0
    spd=8 --speed of movement (bascially number of frames taken to move between squares)- lower=faster
    stepx=0
    stepy=0
    --display of map rotated by 90 degrees anticlockwise when displayed on screen
    --This means left column of array below corresponds to bottom row of map on screen
    level={
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {1,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1,1},
    {1,0,0,1,0,0,1,1,1,0,0,0,0,1,0,1,1},
    {1,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1},
    {1,0,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1},
    {1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,1},
    {1,0,0,0,1,1,1,1,1,1,1,1,0,1,0,0,1},
    {1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,1},
    {1,1,0,1,1,1,0,0,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,1},
    {1,1,1,1,0,1,1,1,1,1,1,1,0,0,0,0,1},
    {1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1},
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},
    {1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1},
    {1,1,1,0,0,0,0,0,1,1,1,1,0,1,1,1,1},
    {1,1,1,0,0,0,0,0,1,1,1,1,0,1,1,1,1},
    {1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1},
    {1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
    }

    size=36--zoom level which sets the size for each tile

    --initiate map variables
    mapw=#level
    maph=#level[1]
    map={}
    for i=1,mapw do
        map[i]={}
        for j=1,maph do
            map[i][j]=Cell(i,j,goal.x,goal.y,level[i][j])
        end
    end
        path={}--will hold the active path
end


function astar(start,gin)
    --get the shortest path between start and end points using the a* algorithm
    goal.x=gin.x
    goal.y=gin.y
    for i=1,mapw do
        for j=1,maph do
            map[i][j]:reset()
        end
    end
    neighbours={vec2(-1,1),vec2(0,1),vec2(1,1),vec2(1,0),vec2(1,-1),vec2(0,-1),vec2(-1,-1),vec2(-1,0)}

    local loop=0
    openlist={start}
    closedlist={}
    openlist[#openlist].g=0
    openlist[#openlist].f=openlist[#openlist].g+getDistance(vec2(start.x,start.y),goal,dmeasure)

    local current=openlist[1]
    local currentpos=1

    while #openlist>0 do
        loop = loop + 1
        current=openlist[1]
        currentpos=1
        for i,ol in pairs(openlist) do
            if ol.f<current.f then
                current=ol
                currentpos=i
            end
        end
        if current.parent~=nil then
        end

        if current.x==goal.x and current.y==goal.y then
--reached goal so finish
            table.insert(closedlist,current)
            map[current.x][current.y]=current
            map[current.x][current.y].inclosed=1
            --return path
            path=getPath()
            for i,p in pairs(path) do
                map[p.x][p.y].onpath=1
            end
            break
        end

        --  remove current from open_list
        map[openlist[currentpos].x][openlist[currentpos].y].inopen=0
        table.remove(openlist,currentpos)

        --    add current to closed_list
        table.insert(closedlist,current)
        map[current.x][current.y]=current
        map[current.x][current.y].inclosed=1

        for j,n in pairs(neighborsof(current)) do
            local inc=0
            for k,closen in pairs(closedlist) do
                if closen.x==n.x and closen.y==n.y then
                    inc=k
                end
            end

            if inc==0 then
                n.f=n.g+getDistance(vec2(n.x,n.y),goal,dmeasure)
                local openneighbor=nil
                for k,openn in pairs(openlist) do
                    if openn.x==n.x and openn.y==n.y then
                        openneighbor=openn
                    end
                end

                if openneighbor==nil then
                    table.insert(openlist,n)
                else

                    if n.g<openneighbor.g then
                        openneighbor.g=n.g
                        openneighbor.parent=n.parent
                    end
                end
            end
        end
        --want to break out if a path cant be found after a certain number of iterations
        --setting this break point to be the number of cells in the map
        if loop>maph*mapw then
            return nil
        end
    end
end

function neighborsof(node)
    local nb={}
    for j,n in pairs(neighbours) do
        --check for valid neighbours
        if node.y+n.y<=#map[1] and node.y+n.y>0 and node.x+n.x<=#map and node.x+n.x>0 then
            if map[node.x+n.x][node.y+n.y].value==0 then
                --brute force check to prevent squeezing through a diagonal wall
                if (j==1 and (map[node.x+neighbours[8].x][node.y+neighbours[8].y].value==1 and map[node.x+neighbours[2].x][node.y+neighbours[2].y].value==1)) 
                or (j==3 and (map[node.x+neighbours[2].x][node.y+neighbours[2].y].value==1 and map[node.x+neighbours[4].x][node.y+neighbours[4].y].value==1)) 
                or (j==5 and (map[node.x+neighbours[4].x][node.y+neighbours[4].y].value==1 and map[node.x+neighbours[6].x][node.y+neighbours[6].y].value==1)) 
                or (j==7 and (map[node.x+neighbours[6].x][node.y+neighbours[6].y].value==1 and map[node.x+neighbours[8].x][node.y+neighbours[8].y].value==1)) 
                then

                else
                    table.insert(nb,Cell(node.x+n.x,node.y+n.y,goal.x,goal.y,level[node.x+n.x][node.y+n.y]))
                    if j==1 or j==3 or j==5 or j==7 then
                        nb[#nb].g=node.g+1.414
                    else
                        nb[#nb].g=node.g+1
                    end
                    nb[#nb].parent=node
                end
            end
        end
    end
    return nb
end

function getDistance(start,fin,measure)
    --calculate the distance between two points
    local dist=0
    if measure==1 then
        --manhatten
        dist=math.abs(start.x-fin.x)+math.abs(start.y-fin.y)
    elseif measure==2 then
        --euclidean
        dist=math.sqrt((start.x-fin.x)^2+(start.y-fin.y)^2)        
    end
    return dist
end

function getPath()

   local p={}
    local curx=goal.x
    local cury=goal.y
    local count=0

    while (curx~=hero.x or cury~=hero.y) do
        count = count + 1
        table.insert(p,map[curx][cury])
        local parx=map[curx][cury].parent.x
        local pary=map[curx][cury].parent.y
        curx=parx
        cury=pary
    end
    return p
end


function draw()
    offx=hero.x
    offy=hero.y    
    -- This sets a dark background color
    background(40, 40, 50)

    --draw the map
    for i=1,mapw do
        for j=1,maph do
            if map[i][j].value==1 then
                sprite("Blocks:Brick Grey",(i-offx)*size+WIDTH/2,(j-offy)*size+HEIGHT/2,size,size)
            else
                tint(255,50)
                --highlight path
                if map[i][j].onpath==1 then
                    tint(255,0,0,50)
                end                

                sprite("Blocks:Blank White",(i-offx)*size+WIDTH/2,(j-offy)*size+HEIGHT/2,size*0.9,size*0.9)
                noTint()
            end
        end
    end
    --draw goal and hero sprites
    sprite("Planet Cute:Heart",(goal.x-offx)*size+mapcentre.x,(goal.y-offy)*size+mapcentre.y,size*0.58,size)
    sprite("Platformer Art:Guy Standing",WIDTH/2,HEIGHT/2,size*0.7,size)    

    fill(255)

    movecount = movecount - 1
    if #path>0 and movecount<=0 then        
        dest=path[#path]        
        movecount=spd
        stepx=(dest.x-hero.x)/spd
        stepy=(dest.y-hero.y)/spd
        map[dest.x][dest.y].onpath=0
        table.remove(path,#path)
    end
    if movecount>0 then
        hero.x = hero.x + stepx
        hero.y = hero.y + stepy
    else
        hero.x = math.floor(hero.x+0.5)
        hero.y = math.floor(hero.y+0.5)
    end
end

function touched(t)
    if t.state==ENDED then
        if #path==0 then
            local tempx=math.floor(0.5+((t.x-(mapcentre.x))/size))+hero.x
            local tempy=math.floor(0.5+((t.y-(mapcentre.y))/size))+hero.y
            if tempx>0 and tempx<=mapw and tempy>0 and tempy<maph then
                if map[tempx][tempy].value==0 then
                    astar(map[hero.x][hero.y],map[tempx][tempy])
                end
            end
        end
    end
end

--# Cell
Cell = class()

function Cell:init(x,y,goalx,goaly,val)
    -- you can accept and set parameters here
    self.x = x
    self.y=y
    self.g=0 -- g is the incremental cost to get to this square
    self.h=getDistance(vec2(x,y),vec2(goalx,goaly),dmeasure)
    self.value=val
    self.inopen=0
    self.inclosed=0
    self.onpath=0
self.parent=nil
end
function Cell:reset()
        self.inopen=0
    self.inclosed=0
    self.onpath=0
self.parent=nil
    self.h=0
    self.f=0
    self.g=0
end

function Cell:draw()
    sprite("Blocks:Cactus Inside",self.x*size,self.y*size,size,size)
end