0

# [SOLVED] A* algorithm returns suboptimal path for some reason?

Edited 9 days ago

This question has been solved by the original poster.

Recently I was trying to implement pathfinding to my game, this seemed rather trivial as I already had a script from before (which used the A Star algorithm). But after a while I found out that the script offered subpar performance, and a lot of the variables/functions were undocumented, so there was no way I was going to fix it. So I decided to instead write a new script (and make sure to document everything). After a lot of googling and watching video tutorials (namely Sebastian Lague's videos on the A Star algorithm, found here. I made sure to follow the pseudocode in the video very closely) I finally had a script. However, there were some problems;

Image

By the way, those brown cells are supposed to be mud, increasing the G cost by thrice the amount of a regular cell. I don't think this causes the problem, however. As even without this feature the algorithm would still sometimes underperform.

For some reason the algorithm chose a rather suboptimal path, taking a lot of needless turns. I've tried lots of things but nothing has worked; changing the heuristic, changing how the G cost worked and more. So, as I can't find any solution myself I went on here and posted this question. If you have any suggestions/solutions, then feel free to help me out.

Full script (I believe the problem resides between line 98-106):

function manhattanDistance(goalX,goalY,x,y) -- Calculate heuristic cost
return Vector2.new(x - goalX,y - goalY).Magnitude
--return math.abs(x - goalX) + math.abs(y - goalY)
end

-- Find the lowest F cost. Current function is very unoptimized
function lowestFCost(list)
local min,node,index = math.huge,nil,nil
for i,v in pairs(list) do
if v.F < min then
min = v.F
node = v
index = i
end
end
return node,index
end

-- Check whether or not a cell exists at x,y
function isValidCell(x,y,list)
if list[x] then
if list[x][y] then
return true
end
end
return false
end

-- Initialize 'cell' object
cell = {}
function cell.new(x,y,h,g)
local cell = {}
cell.X = x -- Cell X position
cell.Y = y -- Cell Y position
cell.H = h -- Cell Heuristic cost. IE: Distance to target
cell.G = g -- Cell G Cost. The distance of the most optimal path to this cell.
cell.F = 0 -- Cell F cost. Sum of H and G cost.
cell.Parent = nil -- Parent Cell
cell.Traversable = true -- Whether or not the Cell can be crossed or not
cell.MovementCost = 1 -- How much crossing this cell will increment the G cost
return cell
end

-- Initialize some variables
local startX,startY = 0,0
local targetX,targetY = 15,15
local map = {}
local directions = {
{-1,0},
{1,0},
{0,-1},
{0,1}
} -- Table representing the four available directions of movement (up,down,left,right), allows for more organized code

-- Initialize the actual 'map'
local grid = {}
for x = 0,15 do
grid[x] = {} -- Internal representation of cells
map[x] = {} -- In-game representation of cells as parts
for y = 0,15 do
grid[x][y] = cell.new(x,y,nil,0)
local p = Instance.new("Part") -- Create a part to represent the cell
p.Size = Vector3.new(1,1,1)
p.Anchored = true
p.CFrame = CFrame.new(x,0,y)
p.Parent = workspace
if not grid[x][y].Traversable then
p.BrickColor = BrickColor.new("Black")
end
if math.random(0,2) == 0 then
grid[x][y].MovementCost = 3
p.BrickColor = BrickColor.new("Brown")
p.Material = Enum.Material.Slate
end
map[x][y] = p
end
end

-- Do the algorithm

local open = {}
local closed = {}
local debugMode = true
table.insert(open,#open + 1,grid[startX][startY])
while #open >= 0 do
wait(.1)
local current,index = lowestFCost(open)
if index == nil then
break
end
open[index] = nil
table.insert(closed,#closed + 1,current)
if debugMode then map[current.X][current.Y].BrickColor = BrickColor.new("Really red") end
if current.X == targetX and current.Y == targetY then -- Exit loop if target is reached
if debugMode then map[current.X][current.Y].BrickColor = BrickColor.new("Baby blue") end
break
end
for i,v in pairs(directions) do
if isValidCell(current.X - v[1],current.Y - v[2],grid) then
local neighbour = grid[current.X - v[1]][current.Y - v[2]]
if not table.find(closed,neighbour) and neighbour.Traversable then
if not table.find(open,neighbour) or current.G + neighbour.MovementCost < neighbour.G then
neighbour.F = manhattanDistance(targetX,targetY,neighbour.X,neighbour.Y) + current.G + neighbour.MovementCost
neighbour.Parent = current
if not table.find(open,neighbour) then
table.insert(open,#open + 1,neighbour)
if debugMode then map[neighbour.X][neighbour.Y].BrickColor = BrickColor.new("Bright green") end
end
end
end
end
end
end

-- Retrace path from end point
function recurse(tbl)
local recurse = true
local currentTile = tbl[targetX][targetY].Parent
local path = {}
while recurse == true do
recurse = false
if currentTile then
recurse = true
table.insert(path,#path + 1,currentTile)
currentTile = currentTile.Parent
end
end
return path
end

-- Build path
local path = recurse(grid)
print(#path) -- Path length
for i,v in pairs(path) do
wait(.1)
map[v.X][v.Y].BrickColor = BrickColor.new("Bright blue")
end


pls help

Edit: I managed to solve the problem myself. I had actually made a typical programming error and forgot to assign a variable, namely the G and the H costs. This caused the G Cost to stay constant, and thus caused paths to be suboptimal.

0
I haven't looked at the code but from a glance at the image, it looks like your implementation isn't backtracking properly. Is your heuristic admissible? https://thefinalbit.wordpress.com/2014/01/24/admissible-vs-consistent-heuristics eLunate 5136 — 9d
0
As of now I'm using euclidean distance, I found that euclidean distance would outperform Manhattan distance on a set seed. I'm quite new to the subject of pathfinding and pathfinding algorithms, but as far as I know I do believe that euclidean distance is in my case (4-way movement) admissible. Feel free to correct me. And yes, I too believe that the backtracking is to blame. Vinceberget 1269 — 9d