Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Simple a-star path finding for dungeon crawler example

in Examples Posts: 708

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


Comments

  • Posts: 875

    @West - interesting approach, have shuffled your code a little and changed the sprites - this could make a smart game if you want to take it further. I like the seek the path but I’d like to see it up against an intricate maze. Impressive.

  • dave1707dave1707 Mod
    Posts: 6,929

    Here’s a link to a path finding program I wrote back in April 2015. Scroll to the bottom for my code. Drag your finger to create barriers

    https://codea.io/talk/discussion/6481/jumper-with-hexagons-success
    
  • Posts: 708
    Yeah - been playing a lot of pixel dungeon lately. The A Star algorithm should always give you the shortest path and should scale. My implementation might be less than optimal but wanted to code from scratch. Happy to hear about any suggested improvements- my next stop is to be able to scroll round the map with the option of locking on to follow the player sprite.
  • Posts: 708
    Thanks @Dave1707 - I’ll take a look
  • edited June 1 Posts: 1

    Thanks! This approach looks pretty interesting with play fafafa slots online

  • Posts: 708

    Here’s an update which adds lighting and also the ability to scroll round a larger map. Trying to post an exported zip project file - not sure if this will work...

Sign In or Register to comment.