Another day, another change. I had a problem where my algorithm would be stuck on one same node all the time, and I tried to fix it. What I had in mind, is to optimize my cost detection thingy. Basically there is a regCost and a ManhattanCost. regCost is basically the cost, that determines how much tiles you would need to walk through to reach another tile, and ManhattanCost is basically approximately equal cost of how much you would need more tiles to get to finish. ManhattenCost does not take in count obstacles and different costs, so it is not 100% reliable. The main Cost is equal to regCost plus ManhattanCost, and the next tile to choose would be the one with the main Cost being the least. Additionally, I utilized OpenList differently from before, now the Currently inspected tile is inside of its own Current table, while the OpenList contains the neighbors of already visited parts. ClosedList is also used: After finishing calculations of where to go, the part that was previously in Current table is moved into ClosedList.
So in my idea, the Closed List prevents part from going back in the already visited nodes, and if the algorithm chooses undesired track, it eventually gets stuck, and after that, it goes through OpenList, looking for new part with lowest main Cost, to then continue its way. However I ran into some problem… There is this error that I never stumbled upon before:
Script timeout: exhausted allowed execution time
And this does not let me properly see if my script works as intended. Any ideas why this could have happened?
Here is my current code:
local start = workspace.Nodes.Start
local finish = workspace.Nodes.Finish
local Nodes = workspace.Nodes:GetChildren()
local OpenList = {}
local ClosedList = {}
local Path = {}
local Neighbors = {}
local Costs = {}
local Current = {}
local ExtraCheckList = {}
script.Parent.MouseClick:Connect(function()
table.insert(Current, start)
while #Current > 0 do
for i, part in pairs(Nodes) do
if part:GetAttribute("Occupied") == true then
table.remove(Nodes, table.find(Nodes, part))
part.Color = Color3.fromRGB(100, 0, 0)
elseif table.find(ClosedList, part) then
table.remove(Nodes, table.find(Nodes, part))
part.Color = Color3.fromRGB(60, 60, 60)
end
end
for i, center in pairs(Current) do
center.Color = Color3.fromRGB(150, 150, 0)
local UpNeighbor
local DownNeighbor
local RightNeighbor
local LeftNeighbor
local UpCost
local DownCost
local RightCost
local LeftCost
local regUpCost
local regDownCost
local regRightCost
local regLeftCost
for i, n in pairs(Nodes) do
if math.abs(n.Position.X / 8) == math.abs(center.Position.X / 8) and math.abs(n.Position.Z / 8) == math.abs(center.Position.Z / 8) + 1 then
UpNeighbor = n
if UpNeighbor then
if table.find(OpenList, UpNeighbor) then
regUpCost = center:GetAttribute("regCost") + 1
if regUpCost < UpNeighbor:GetAttribute("regCost") then
UpNeighbor:SetAttribute("regCost", regUpCost)
UpNeighbor:SetAttribute("CameFrom", center.CFrame)
else
UpNeighbor:SetAttribute("regCost", UpNeighbor:GetAttribute("regCost"))
end
else
regUpCost = math.abs((n.Position.X / 8) - (start.Position.X / 8)) + math.abs((n.Position.Z / 8) - (start.Position.Z / 8))
UpCost = math.abs((finish.Position.X / 8) - (UpNeighbor.Position.X / 8)) + math.abs((finish.Position.Z / 8) - (UpNeighbor.Position.Z) / 8) + regUpCost
table.insert(OpenList, UpNeighbor)
table.insert(Costs, UpCost)
end
end
elseif math.abs(n.Position.X / 8) == math.abs(center.Position.X / 8) and math.abs(n.Position.Z / 8) == math.abs(center.Position.Z / 8) - 1 then
DownNeighbor = n
if DownNeighbor then
if table.find(OpenList, DownNeighbor) then
regDownCost = center:GetAttribute("regCost") + 1
if regDownCost < DownNeighbor:GetAttribute("regCost") then
DownNeighbor:SetAttribute("regCost", regDownCost)
DownNeighbor:SetAttribute("CameFrom", center.CFrame)
else
DownNeighbor:SetAttribute("regCost", DownNeighbor:GetAttribute("regCost"))
end
else
regDownCost = math.abs((n.Position.X / 8) - (start.Position.X / 8)) + math.abs((n.Position.Z / 8) - (start.Position.Z / 8))
DownCost = math.abs((finish.Position.X / 8) - (DownNeighbor.Position.X / 8)) + math.abs((finish.Position.Z / 8) - (DownNeighbor.Position.Z) / 8) + regDownCost
table.insert(OpenList, DownNeighbor)
table.insert(Costs, DownCost)
end
end
elseif math.abs(n.Position.X / 8) == math.abs(center.Position.X / 8) + 1 and math.abs(n.Position.Z / 8) == math.abs(center.Position.Z / 8) then
RightNeighbor = n
if RightNeighbor then
if table.find(OpenList, RightNeighbor) then
regRightCost = center:GetAttribute("regCost") + 1
if regRightCost < RightNeighbor:GetAttribute("regCost") then
RightNeighbor:SetAttribute("regCost", regRightCost)
RightNeighbor:SetAttribute("CameFrom", center.CFrame)
else
RightNeighbor:SetAttribute("regCost", RightNeighbor:GetAttribute("regCost"))
end
else
regRightCost = math.abs((n.Position.X / 8) - (start.Position.X / 8)) + math.abs((n.Position.Z / 8) - (start.Position.Z / 8))
RightCost = math.abs((finish.Position.X / 8) - (RightNeighbor.Position.X / 8)) + math.abs((finish.Position.Z / 8) - (RightNeighbor.Position.Z) / 8) + regRightCost
table.insert(OpenList, RightNeighbor)
table.insert(Costs, RightCost)
end
end
elseif math.abs(n.Position.X / 8) == math.abs(center.Position.X / 8) - 1 and math.abs(n.Position.Z / 8) == math.abs(center.Position.Z / 8) then
LeftNeighbor = n
if LeftNeighbor then
if table.find(OpenList, LeftNeighbor) then
regLeftCost = center:GetAttribute("regCost") + 1
if regLeftCost < LeftNeighbor:GetAttribute("regCost") then
LeftNeighbor:SetAttribute("regCost", regLeftCost)
LeftNeighbor:SetAttribute("CameFrom", center.CFrame)
else
LeftNeighbor:SetAttribute("regCost", LeftNeighbor:GetAttribute("regCost"))
end
else
regLeftCost = math.abs((n.Position.X / 8) - (start.Position.X / 8)) + math.abs((n.Position.Z / 8) - (start.Position.Z / 8))
LeftCost = math.abs((finish.Position.X / 8) - (LeftNeighbor.Position.X / 8)) + math.abs((finish.Position.Z / 8) - (LeftNeighbor.Position.Z) / 8) + regLeftCost
table.insert(OpenList, LeftNeighbor)
table.insert(Costs, LeftCost)
end
end
end
end
if #Costs > 0 then
local best = math.min(unpack(Costs))
if best == UpCost then
table.remove(Current, table.find(Current, center))
table.insert(ClosedList, center)
table.insert(Current, UpNeighbor)
elseif best == DownCost then
table.remove(Current, table.find(Current, center))
table.insert(ClosedList, center)
table.insert(Current, DownNeighbor)
elseif best == LeftCost then
table.remove(Current, table.find(Current, center))
table.insert(ClosedList, center)
table.insert(Current, LeftNeighbor)
elseif best == RightCost then
table.remove(Current, table.find(Current, center))
table.insert(ClosedList, center)
table.insert(Current, RightNeighbor)
end
else
table.remove(Current, table.find(Current, center))
table.insert(ClosedList, center)
for i, o in pairs(OpenList) do
local check = o:GetAttribute("Cost")
table.insert(ExtraCheckList, check)
end
local newBest = math.min(unpack(ExtraCheckList))
for i, o in pairs(OpenList) do
if o:GetAttribute("Cost") == newBest then
table.insert(Current, o)
end
end
end
end
end
end)
It used to have some task.wait(0.1)s but I got rid of these for some time. When clicking a button, the game freezes for around 30 seconds and then gives out an error.
