[SOLVED] Help with Astar pathfinding

[oleosjo]

Hi,

I have an Astar pathfinding algorithm I'm having trouble with. It seems to find the shortest path in some instances but not in others. I don't know what I'm doing wrong. It is based heavily on http://www.policyalmanac.org/games/aStarTutorial.htm.

If you run the game and click in the top right corner of the map, the problem presents itself. It's not finding the shortest path. In all other directions, though, it does.

Bad

bad pathfinding.png (38.16 KiB) Viewed 3264 times

Here is the function that does the pathfinding:

Code: Select all

function Pathfinder:find(cx,cy,ex,ey)

	if ex < 1 or ey < 1 or ex > #self.nodes or ey > #self.nodes then return nil end

	-- init and add starting node to the open list
	self.nodes[cx][cy].cost = 0
	self.nodes[cx][cy].F = manhattan(cx, cy, ex, ey)
	local open = {self.nodes[cx][cy]}
	-- init closed list
	local closed = {}

	local current = {}

	while not _.is_empty(open) do
		--sort by lowest F cost
		_.sort(open, function(a,b) return a.F < b.F end)
		-- take first off open list
		current = _.shift(open)
		-- switch current to closed list
		table.insert(closed, current)
		--if end square is in the closed table we're done
		if(table.contains(closed,self.nodes[ex][ey])) then
			break
		end

		neighbors = {}
		for x=-1, 1 do 
			for y=-1, 1 do
				local nx = current.x + x
				local ny = current.y + y
				if self.nodes[nx][ny] ~= nil then
					if (math.abs(x) == math.abs(y)) then --diagonal
						self.nodes[nx][ny].cost = 14
					else
						self.nodes[nx][ny].cost = 10
					end
					table.insert(neighbors, self.nodes[nx][ny])
				end
			end
		end

		-- For each adjacent square do
		for k,neighbor in pairs(neighbors) do
			-- if it's walkable and not in the closed list
			if neighbor.walkable and not table.contains(closed, neighbor) then
				
				local G = current.cost + neighbor.cost
				if not table.contains(open, neighbor) or G < current.cost then
					-- make the current square the parent of this square
					neighbor.parent = current

					H = manhattan(neighbor.x, neighbor.y, ex, ey)

					neighbor.cost = G 
					neighbor.F = neighbor.cost + H
					 	
					-- add it to the open list
					if not table.contains(open, neighbor) then
						table.insert(open, neighbor)	
					end
				 end
			end
		end

	end

	local path = {}

	if self.nodes[ex][ey].parent == nil then
		pathready = false
		self.path = nil
	else
		target = self.nodes[ex][ey]
		while target ~= self.nodes[cx][cy] do
			table.insert(path, {x=target.x,y=target.y})
			target = target.parent
		end
		table.insert(path, {x=cx,y=cy})
		pathready = true
		self.path = path
	end
end

[oleosjo]

I fixed it.

I don't really understand how I fixed it, but I changed the pathfinding function to this:

Code: Select all

function Pathfinder:find(cx,cy,ex,ey)

	if ex < 1 or ey < 1 or ex > #self.nodes or ey > #self.nodes then return nil end

	-- init and add starting node to the open list
	self.nodes[cx][cy].cost = 0
	self.nodes[cx][cy].F = manhattan(cx, cy, ex, ey)
	local open = {self.nodes[cx][cy]}
	-- init closed list
	local closed = {}

	local current = {}

	while not _.is_empty(open) do
		--sort by lowest F cost
		_.sort(open, function(a,b) return a.F < b.F end)
		-- take first off open list
		current = _.shift(open)
		-- switch current to closed list
		table.insert(closed, current)
		--if end square is in the closed table we're done
		if(table.contains(closed,self.nodes[ex][ey])) then
			break
		end

		neighbors = {}

		-- For each adjacent square do		
		for x=-1, 1 do 
			for y=-1, 1 do
				local nx = current.x + x
				local ny = current.y + y
				neighbor = self.nodes[nx][ny]
			-- if it's walkable, not in the closed list, and within bounds
			if neighbor.walkable and not table.contains(closed, neighbor) and self.nodes[nx][ny] ~= nil then
				-- find G cost
				if (math.abs(nx) == 1 and math.abs(ny) == 1) then --diagonal
						addedGCost = 14
					else
						addedGCost = 10
					end
				local G = current.cost + addedGCost
				if not table.contains(open, neighbor) or G < current.cost then
					-- make the current square the parent of this square
					neighbor.parent = current

					H = manhattan(neighbor.x, neighbor.y, ex, ey)

					neighbor.cost = G 
					neighbor.F = neighbor.cost + H
					 	
					-- add it to the open list
					if not table.contains(open, neighbor) then
						table.insert(open, neighbor)	
					end
				 end
			end
		end
	end
	end

	local path = {}

	if self.nodes[ex][ey].parent == nil then
		pathready = false
		self.path = nil
	else
		target = self.nodes[ex][ey]
		while target ~= self.nodes[cx][cy] do
			table.insert(path, {x=target.x,y=target.y})
			target = target.parent
		end
		table.insert(path, {x=cx,y=cy})
		pathready = true
		self.path = path
	end
end

[raidho36]

You should've posted the difference rather than new whole version, since it's pretty big and we'd have line-by-line compare them or use diff tool.

Implementation is highly sub-optimal, if you gonna use that extensively make sure to omptimize that.

[oleosjo]

You should've posted the difference rather than new whole version, since it's pretty big and we'd have line-by-line compare them or use diff tool.

Implementation is highly sub-optimal, if you gonna use that extensively make sure to omptimize that.

Yeah, I plan on optimizing later. This is just the early stages and I needed to lay it out in a way that's easier to get my head around.

I'll try to post differences from now on.

[raidho36]

Lua gems has chapters about code performance, I suggest reading that.