Implementing A* pathfinding in my hexagon grid based game
Posted: Thu Oct 19, 2017 7:42 am
Before I start, I want to say yes, I know the redblob article on hexagon grids exists. It doesn't help me nor does the pathfinding article also on that website. (everytime I've asked this question the only answer I've gotten is a link to that article so I'm sort of getting annoyed)
I'm creating a game where the main gameplay involves a hexagon grid (won't go into this in more detail because it's mostly irrelevant). Currently, my AI can use one game mechanic which is taking over enemy hexagons. However, I want it to also take advantage of the swapping mechanic I have where you swap two owned hexagons. One way I thought of doing this was with pathfinding (pathfinding to the hexagon the AI wants to swap with, and making them swap the hexagons along the path until they reach it)
My main problem is trying to draw the path to the goal. It seems that the goal node never has previous assigned, while everything else does have previous assigned to it.
Here's my code:
I've attached the zip for my game (I'm on a college PC atm and I can't change extensions) so you can see what's happening. AStar.lua in lib is the relevant file.
I'm creating a game where the main gameplay involves a hexagon grid (won't go into this in more detail because it's mostly irrelevant). Currently, my AI can use one game mechanic which is taking over enemy hexagons. However, I want it to also take advantage of the swapping mechanic I have where you swap two owned hexagons. One way I thought of doing this was with pathfinding (pathfinding to the hexagon the AI wants to swap with, and making them swap the hexagons along the path until they reach it)
My main problem is trying to draw the path to the goal. It seems that the goal node never has previous assigned, while everything else does have previous assigned to it.
Here's my code:
Code: Select all
function AStar.pathfind(start,goal,grid)
local closedset={}
local openset={start}
local current -- where are we at the moment?
local startTimer=love.timer.getTime()
local path={} -- path
while (#openset>0) do
print("!!!")
local lowestIndex=1
for i=1,#openset do
local opensetD=hexes.getHexagon(openset[i])
if opensetD.f<hexes.getHexagon(openset[lowestIndex]).f then
lowestIndex=i
end
if opensetD.f==hexes.getHexagon(openset[lowestIndex]).f then
if (opensetD.g>hexes.getHexagon(openset[lowestIndex]).g) then
lowestIndex=i
end
end
end
local cur=openset[lowestIndex]
local curData=hexes.getHexagon(cur)
for _, v in pairs(closedset) do
local data=hexes.getHexagon(v)
data["type"]["color"]={255,0,0}
end
for _, v2 in pairs(openset) do
local data=hexes.getHexagon(v2)
data["type"]["color"]={0,255,0}
end
if cur==goal then
local temp=cur
print("prev:",temp.previous) -- is always nil
local endT=love.timer.getTime()
print("Done in: "..tostring(round2(endT-startTimer,3)))
while (temp.previous) do -- since the first previous (previous of the end node) is always nil, this never runs.
local newTemp=temp.previous
temp=newTemp
local tempData=hexes.getHexagon(temp)
tempData["type"]["color"]={255,255,255} -- draw path as white
end
break
end
remove(openset,cur)
table.insert(closedset,cur)
local neighbors=grid:neighbors(cur.q,cur.r);
for neighborInd, neighbor in pairs(neighbors) do
local neighbors=neighbor
local neighborsD=hexes.getHexagon(neighbor)
if neighborsD["text"]~="1" then
if not find(closedset,neighbor) then
local tempG=curData.g+1
if find(openset,neighbor) then
if tempG<neighborsD.g then
neighborsD.g=tempG
end
else
neighborsD.g=tempG
table.insert(openset,neighbor)
end
end
neighborsD.h=AStar.heuristic(neighbor,goal)
neighborsD.f=neighborsD.g+neighborsD.h
neighborsD.previous=cur
end
end
end
return {finished and path or nil,finished}
end