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