Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
0

A* (A Star) Pathfinding not iterating?

Asked by 6 years ago

I am using A* pathfinding for an AI because the Roblox Pathfinding algorithm doesn't meet my needs, but it seems to keep looping through the starting part. It doesn't move on to any of the other parts in the open list, and parts that are ALREADY in the open list are simply re-added as if they are new parts. Any help is appreciated!

Code:

local module = {}

function module.FindPath(Map, BeginModel, EndModel)

    local Start = BeginModel.PrimaryPart    
    local Finish = EndModel.PrimaryPart 

    local Closed = {}
    local Open = {Start}    

    Start.BrickColor = BrickColor.White()   
    Finish.BrickColor = BrickColor.White()

    if not Start:FindFirstChild("g") and not Start:FindFirstChild("h") and not Start:FindFirstChild("f") then local g, h, f = Instance.new("NumberValue", Start), Instance.new("NumberValue", Start), Instance.new("NumberValue", Start) g.Name, h.Name, f.Name = "g", "h", "f" end
    Start.g.Name, Start.h.Name, Start.f.Name = "g", "h", "f"    

    wait()  

    Start.g.Value = 0 -- Steps from the start
    Start.h.Value = CalculateHeuristic(Start, Finish, 1) -- Avg. Distance from end
    Start.f.Value = Start.g.Value + Start.h.Value -- Total

    wait()  

     while #Open > 0 do 

        --print("open: "..tostring((unpack(Open))))

        local CurrentSearch = OpenWLeastF(Open)

        CurrentSearch.BrickColor = BrickColor.Blue()

        if CurrentSearch == Finish then
            print("done!")
            return print("done") -- PUT CODE FOR GENERATING PATH HERE!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 7u8u9287654gf298654fg296435gt24 <<-------
        end

        table.insert(Closed, CurrentSearch) -- Adds to closed list, but CurrentSearch is still NOT NIL. It is simply in the CLOSED LIST.
        Open[CurrentSearch] = nil

        for _, Neighbor in pairs(GetNeighboringParts(CurrentSearch)) do 

            if not Closed[Neighbor] and not Open[Neighbor] then

                if not Neighbor:FindFirstChild("g") and not Neighbor:FindFirstChild("h") and not Neighbor:FindFirstChild("f") then local g, h, f = Instance.new("NumberValue", Neighbor), Instance.new("NumberValue", Neighbor), Instance.new("NumberValue", Neighbor) g.Name, h.Name, f.Name = "g", "h", "f"   end

                Neighbor.g.Value = CurrentSearch.g.Value + GetMagnitude(CurrentSearch, Neighbor)
                Neighbor.h.Value = CalculateHeuristic(Neighbor, Finish, 1)
                Neighbor.f.Value = Neighbor.g.Value + Neighbor.h.Value 

                table.insert(Open, Neighbor)
                print(unpack(Open))
            end
        end

     wait(1)

     end

end

function GetNeighboringParts(Part)
    local Neighbors = {}

    local pseudoPart = Part:Clone()
    pseudoPart.Parent = Part
    pseudoPart.Position = Part.Position
    pseudoPart.Size = Part.Size + Vector3.new(1,0,1)

    for _, obj in pairs (pseudoPart:GetTouchingParts()) do
        if Neighbors[obj] == nil and obj ~= Part then
            table.insert(Neighbors, obj)
        end
    end

    pseudoPart:Destroy()

    return Neighbors
end

function GetMagnitude(Part2, Part1)
    local Mag = (Part2.Position - Part1.Position).Magnitude
    return Mag
end

function OpenWLeastF(Open, CurrentNode)

    local Best = CurrentNode

    for i, node in pairs (Open) do
        if node ~= nil then
            local f = Open[i].f.Value
            if not Best or f < Best.f.Value then -- Best.f.value is the f value within the part that is currently Best.
                Best = node
            end
        end
    end 

    print(Best.f.Value)
    return Best -- Returns a part (keep in mind that returning the Best.Parent would return the model, if I want to in the future!)

end

function CalculateHeuristic(Node, End, MvmtCost)
    local movement_cost = MvmtCost or 1         
    return movement_cost*math.sqrt((Node.Position.x-End.Position.x)^2 + (Node.Position.y-End.Position.y)^2) 
end


return module

Answer this question