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

Path finding Alorithm, what have I missed?

Asked by
hiccup111 231 Moderation Voter
9 years ago

Yes, you can copy and try this code for yourself.

REQUIREMENTS:

Use a Normal (Server) script.

Line12, 'Objects', a Model of all Parts / Walls in Workspace (BasePlate should not be a child of this) Line13, Just an NPC, with a 'Humanoid'

It's based on the A* algorithm.

Efficiency is NOT a requirement at the moment.

SELECTION BOX COLOUR CODES:

BLUE ' Open List '

RED 'Closed List'

Yellow 'Pathway picked'

Anyone with any knowledge on this algorithm, please let me know of anything I've missed.

PS. The Heuristic *is on line *129

if not Workspace:FindFirstChild("BasePlate") then
    BasePlate = Instance.new("Part",Workspace)
    BasePlate.Name = "BasePlate"
    BasePlate.FormFactor = "Custom"
    BasePlate.Size = Vector3.new()
    BasePlate.CanCollide = true
    BasePlate.Anchored = true
    BasePlate.CFrame = CFrame.new(0,-100,0)
else
    BasePlate = Workspace.BasePlate
end
Objects = Workspace.Objects
char = script.Parent
char:MakeJoints()

if not Workspace:FindFirstChild("Nodes") then
    Instance.new("Model",Workspace).Name = "Nodes"
end
Nodes = Workspace.Nodes

defaultNode = Instance.new("Part")
defaultNode.Name = "Node"
defaultNode.Transparency = 0
defaultNode.Anchored = true
defaultNode.CanCollide = false
defaultNode.FormFactor = "Custom"
defaultNode.Size = Vector3.new(.4,.4,.4)
--Instance.new("SelectionBox",defaultNode).Adornee = defaultNode



function isOpen(n,list)
    for _,v in pairs(list) do if v == n then return true end end
    return false
end
function isClosed(n,list)
    for _,v in pairs(list) do
        if v == n then return true end end 
    return false
end


castedFolder = Instance.new("Model",Workspace)
castedFolder.Name = "RayCastFolder"

rayP = Instance.new("Part")
rayP.Anchored = true
rayP.CanCollide = false
rayP.FormFactor = "Custom"


function isVisible(from,too, ignore)
    ray = Ray.new(from.Position,(too.Position-from.Position).unit*999)
    if not ignore then
        hit,pos = Workspace:FindPartOnRayWithIgnoreList(ray, {char,castedFolder})
    else
        hit,pos = Workspace:FindPartOnRayWithIgnoreList(ray, {ignore,char,castedFolder})
    end
    local rp = rayP:Clone()
    rp.Parent = castedFolder
    rp.Size = Vector3.new(0,0,(pos-ray.Origin).magnitude)
    rp.CFrame = CFrame.new(ray.Origin:Lerp(pos,0.5),pos)

    if hit == too then return true else return false end
end


function UpdateNodes()
    Nodes:ClearAllChildren()
    for _,v in pairs(Objects:GetChildren()) do
        if v:IsA("BasePart") and v~= Workspace.Target then
            local div = 1
            newNode = defaultNode:Clone()
            newNode.Name = newNode.Name
            newNode.Parent = Nodes
            newNode.CFrame = v.CFrame * CFrame.new(v.Size.x/div,0,v.Size.z/div)

            newNode = defaultNode:Clone()
            newNode.Name = newNode.Name
            newNode.Parent = Nodes
            newNode.CFrame = v.CFrame * CFrame.new(-v.Size.x/div,0,v.Size.z/div)

            newNode = defaultNode:Clone()
            newNode.Name = newNode.Name
            newNode.Parent = Nodes
            newNode.CFrame = v.CFrame * CFrame.new(-v.Size.x/div,0,-v.Size.z/div)

            newNode = defaultNode:Clone()
            newNode.Name = newNode.Name
            newNode.Parent = Nodes
            newNode.CFrame = v.CFrame * CFrame.new(v.Size.x/div,0,-v.Size.z/div)
        end
    end
    x = 0
    nameTag = "Node"
    for i,v in pairs(Nodes:GetChildren())do
        if x < 10 then
            v.Name = nameTag.."00"..x
        elseif x >= 10 and x < 100 then
            v.Name = nameTag.."0"..x
        elseif x >= 100 and x < 1000 then
            v.Name = nameTag..x
        end
        x = x + 1
    end
end












function GetShortestPath(paths) print("GetShortest Path", #paths)
    bestPath = nil
    bestScore = math.huge
    for i,path in pairs(paths) do wait(2)
        castedFolder:ClearAllChildren()
        score = 0
            for x,p in pairs(path) do
                if x == 1 then isVisible(char.Torso,p) end if x == #path and isVisible(p,Target) then end
                if not lastP then lastP = p end
                if isVisible(lastP,p) then
                    score = score + (p.Position-lastP.Position).magnitude + (p.Position-Target.Position).magnitude
                --  print(score,bestScore)
                end
                lastP = p
            end
            if score > 0 and score < bestScore then
                bestScore = score
                bestPath = path
            end
    end
    print("Check now")
    wait(5)
    if bestPath and #bestPath > 0 then
        for _,n in pairs(bestPath) do wait(0.5)
            local sb = Instance.new("SelectionBox",n)
            sb.Adornee = n
            sb.Transparency = 0
            sb.Color = BrickColor.Yellow()
            game.Debris:AddItem(sb,5)
        end
    else
        bestPath = nil
    end


    if bestPath then --print("Returning best path", #bestPath.." steps")
        return bestPath
    else    print("Returning nil path")
        return {}
    end
end










UpdateTime = 1


function Search(from,too) wait()-- processes = processes + 1 if processes > 50 then return end
    local openList = {}
--  local closedList = {}
    if from.Parent == Nodes then
        table.insert(closedList,from)
        if not from:FindFirstChild("SelectionBox") then
            sb = Instance.new("SelectionBox",from)
            sb.Adornee = from
            sb.Color = BrickColor.Red()
            game.Debris:AddItem(sb,UpdateTime)
        end
    end
    if isVisible(from,Target,Nodes) then table.insert(newPath,from) return true end
    if isVisible(too,Target,Nodes) then table.insert(newPath,too) return true end

    if isVisible(from,too) then
        table.insert(newPath,from)
        table.insert(newPath,too)
    end

    for i,n in pairs(Nodes:GetChildren()) do
        if not isClosed(n,closedList) and isVisible(from,n) then
            table.insert(openList,n)
            if not n:FindFirstChild("SelectionBox") then
                sb = Instance.new("SelectionBox",n)
                sb.Adornee = n
                sb.Color = BrickColor.Blue()
                game.Debris:AddItem(sb,UpdateTime)
            end
        end
    end

    for i,v in pairs(openList) do
        for z,n in pairs(Nodes:GetChildren()) do
            if n ~= v and isVisible(v,n) and not isClosed(n,closedList) then
                if Search(v,n) then processes = processes + 1
                    print("Got "..processes.." path(s)")
                    table.insert(paths,newPath)
                    newPath = {char.Torso}
                    castedFolder:ClearAllChildren()
                end
            end
        end
    end

end





while true do print("Go")
    castedFolder:ClearAllChildren()
    Target = Workspace.Target
    if isVisible(char.Torso,Target) then
        FOUNDTARGET = true
        char.Humanoid:MoveTo(Target.Position,BasePlate)
    else
        FOUNDTARGET = false
        UpdateNodes()
        newPath = {char.Torso}
        closedList = {}
        openList = {}
        paths = {}
        processes = 0
        Search(char.Torso,Target)
        print("Paths found["..#paths.."]")
    --  coroutine.resume(coroutine.create(function()
            if #paths> 0 then
                for _,v in pairs(GetShortestPath(paths)) do wait(UpdateTime/5) print("Travelin' to ", v)
                    sb = Instance.new("SelectionBox",v)
                    sb.Adornee = v
                    sb.Color = BrickColor.White()
                    game.Debris:AddItem(sb,UpdateTime/5)
                    repeat wait()
                        castedFolder:ClearAllChildren()
                        overshoot = -(char.Torso.Position-v.Position).unit*4
                        char.Humanoid:MoveTo(v.Position + overshoot,BasePlate)
                    until (v.Position-char.Torso.Position).magnitude <= 4 or FOUNDTARGET or isVisible(char.Torso,Workspace.Target)
                    if isVisible(char.Torso,Workspace.Target) then break end
                end
            end
    --  end))
    end
    wait(UpdateTime)
end
0
dude 258 lines of code... HexC3D 830 — 9y
0
As I said, you can copy and test it. hiccup111 231 — 9y
0
I understand the algorithm but just post the algorithm. HexC3D 830 — 9y

1 answer

Log in to vote
1
Answered by
BlueTaslem 18071 Moderation Voter Administrator Community Moderator Super Administrator
9 years ago

A* is not a complicated function. A lot of what you have can be significantly reduced. I'm not going to make this quite the same as what you have, but hopefully this is a useful model for your to write your stuff.

I assume adjacent is defined in a way like isVisible is (except where the parameters are Vector3's)

nodes I take as a list of Vector3's, and from and to being two Vector3's inside of that list.

I didn't test this, but it should work. This function seems to replace your Search and GetShortestPath functions.

When A* is implemented correctly, it efficiently finds the shortest path, not just a path which may be short, but the shortest path.

function astar(nodes,from,to)
    local visited = {};
    local goto = {}; -- Should be a heap for efficiency
    local parent = {};
    local pathDistance = {};
    local last = from;
    while last and last ~= to do
        visited[last] = true;
        for _,node in pairs(nodes) do
            if adjacent(node,last) and not visited[node] then
                pathDistance[node] = pathDistance[last] 
                    + (node-last).magnitude;
                parent[node] = last;
                visited[node] = true;
                table.insert(goto,node);
            end
        end
        table.sort(goto, function(a,b)
            local DA = (a - to).magnitude;
            local DB = (b - to).magnitude;
            return DA + pathDistance[a] < DB + pathDistance[b];
        end);
        -- Again, for efficiency purposes, should be a heap
        last = goto[1];
    end
    local path = {};
    while last do
        table.insert(path,last,1);
        last = parent[last];
    end
    return path;
end

EDIT: Here's an explanation of the algorithm.

This form of path finding is done on a list of "nodes", points in space. Some of them are "connected" or "adjacent", meaning you can go directly from one to another. In the context of a game, that means you can walk in a straight line without any obstacles in the way.

The idea of A* is to improve upon Dijstrika's algorithm. Dijstrika's algorithm starts from a single node, and finds the very closest node, V, to the starting node, S.

You know that since this was the shortest edge available, any other path to that particular closest node would be longer than this one; you know the shortest path from S to V is just {S,V}.

Now we consider all of the nodes adjacent to either S or V to find the next closest (by path length) node to S. If this node, B is adjacent to V (but not S) then the distance of its path is ||B - V|| + ||V - S||. If it is adjacent to S, it's path length is just ||B - S||. (||x|| here means the magnitude of vector x)

We see for the same arguments as before that we have the shortest path to B (either {S,B} or {S,V,B}) and furthermore that no node has a shorter path than B.

We can repeat this until we find a shortest path to every node.

If you think about this, though, for most applications, this is grossly inefficient. Why do we care about the shortest path to B if we only need to know the shortest path to C?

We could begin by modifying the way we grow out. If we instead consider the node closest to our target, we'll see that it only bothers checking things going in the correct direction. This will mean it will (usually) find the path much more quickly. However, we can easily imagine mazes where it goes completely out of its way, turns around, and then finds the solution. The paths produced from this "best first" search is not optimal.

It is provable that if we modify Dijstrika's by just adding the distance to the target, we keep the paths optimal, but also make it much more direct to the target. If we multiply that distance by a larger amount, we get a faster algorithm that gives slightly less optimal paths.

So that's A* for you.

0
Thanks for taking the time to explain this, I knew my version wasn't efficient, but I was unsure how to do it. To be honest I'm still having trouble with it. But cheers. hiccup111 231 — 9y
Ad

Answer this question