Ad
Log in to vote
0

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

Asked by 9 days ago
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

Answer this question