#### 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: 911

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)

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

``````

• Posts: 2,689

@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.

• Mod
Posts: 9,977

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: 911
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: 911
Thanks @Dave1707 - I’ll take a look
• edited June 2018 Posts: 1

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

• Posts: 911

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...