Implementing A* pathfinding in my hexagon grid based game

[Ducktor Cid]

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:

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

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.

[Azhukar]

Code: Select all

local neighbors = grid:neighbors(cur.q,cur.r)
for neighborInd, neighbor in pairs(neighbors) do
	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
			neighborsD.h=AStar.heuristic(neighbor,goal)
			neighborsD.f=neighborsD.g+neighborsD.h
			neighbor.previous=cur
		end
	end
end

[Ducktor Cid]

Yes! That worked. Thank you!