Log in to vote

0
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;

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