# Keeping track of parts allready used for pathfinding

Hello!
I made this script to make my NPC travel on nodes (invisible parts) as shown in image bellow this script

``````local npcPos = npc.HumanoidRootPart.Position
local pos = 500
local part = 0
local newPos = 0
local a = workspace.Defaltio
local b = workspace.Defaltio
while true do
pos = 500
b = a -- Set last destination as last position
npcPos = npc.HumanoidRootPart.Position
for _, v in pairs(nodes) do
if v ~= b then
newPos = (v.Position - npcPos).Magnitude
if newPos < pos then
pos = newPos
part = v
end
end
end
a = part -- Set destination
npc.Humanoid:MoveTo(part.Position)
npc.Humanoid.MoveToFinished:Wait()
end
``````

It works fine expect i need NPCs to avoid going back to node they starter from (unless there is no other node like (like on end of the pathway etc))

I tried to do everything including tables and setting last destination as last position (as shown in code above)
Any idea how to do it?

2 Likes

Tryed solving it using magnitude and if nodes are < 40 then it will add them to table and then randomly select them, however NPCs now skip node and walk on grass wich destroy entire purpose of nodes.

1 Like

How do you represent connectivity between nodes? Because it seems like youâre just using a list of points and assuming that any point is connected to the next and previous nodes in the list, which can work but will only allow you to make paths with no branches. E.g. the node at the intersection has 4 neighbors, not just 2.

Iâm trying to find the closest one using this part of script:

``````newPos = (v.Position - npcPos).Magnitude
if newPos < pos then
pos = newPos
part = v
end
``````

Edit: The script works perfectly fine, i just need to know how to store last node soo NPC doesnât do 180 and return to itâs last node (like in video)

1 Like

Okay i fixed it by keeping table of visited nodes and once table reaches 3 nodes inside it remove first one.

1 Like

Sorry I got carried away long post incoming (lots of pictures and links tho). Code stuff at the bottom.

If you want them to only walk on paths and the closest node isnât always actually connected to the current node, then a distance based approach wonât work. E.g.

Going from A to C wonât work even though C is the closest node to A. The only cases where the distance based approach works is if you carefully construct the âgraphâ so that two nearby nodes are always connected. In your case you might be able to fix it by adding another node between.

The distance based approach isnât ideal even if you get it to work. Consider this graph:

The actor will never go from B to C, because no matter what there will always be a closer node that isnât the previous node. The actor will go back and forth between A, B and D but never visit C. Your actor is very likely to get stuck in very small parts of your whole graph because of this.

Actually, it will always get stuck going back and forth between 3 nodes or go in a circle no matter what. E.g.:

(circles are the max distance)

Consider starting at the blue point. The actor will go along the green path, then turn around to the blue point. From there it can only go along the orange path, eventually getting to the red path where it will be stuck forever. Iâm pretty sure this will always happen. You can try making all nodes the same distance from each other e.g. by placing them in a square grid, but then you need to change your code to find the nearest node and then find all other nodes that are the same distance away, which might not even work because of floating point errors causing âequalâ distances to actually be a tiny amount off.

I would go with a completely different approach where you either manually define connections between nodes and completely ignore distance, or automatically detect which nodes are connected using some other measure of ânearnessâ than Euclidean distance. Your approach essentially divides the nodes into something like a nearest neighbors graph, which usually doesnât connect the whole graph. You might want to try one of these:

âŚ although implementing them can be a hassle especially if youâre new to programming and itâs not even guaranteed to give you exactly the results you want. Iâd recommend connecting nodes manually for example using WeldConstraints:

You can get a list of connected nodes by calling `part:GetConnectedParts(false)`, and using welds is handy because you can see them in the editor to get a nice visualization.

Iâm very confused about your variable names. Youâve called `newPos` and `pos` something with âposâ, i.e. âpositionâ, so a point in space. But youâre setting them to numbers representing distance. Iâm having trouble reading your script in general, so hereâs my attempt at doing what I think itâs trying to do:

``````local MAX_NODE_DIST = 500

--Set starting node
local targetNode = game.Workspace.Defaultio
local prevNode = targetNode

while true do
local npcPos = npc.HumanoidRootPart.Position

--Find the nearest valid node
local nearestValidNode, nearestValidNodeDist = nil, MAX_NODE_DIST --Ignore nodes that are farther than MAX_NODE_DIST (set to math.huge instead if you don't care)
for _, node in pairs(nodes) do
if node ~= prevNode then
local nodeDist = (node.Position - npcPos).Magnitude
if nodeDist < nearestValidNodeDist then
nearestValidNode = node
nearestValidNodeDist = nodeDist
end
end
end

--Set prevNode to targetNode, potentially set targetNode to prevNode (multiple assignment uses "old" value of prevNode)
prevNode, targetNode = targetNode, (nearestValidNode or prevNode) --If no valid nodes were found (i.e. nearestValidNode is nil), allow actor to go back to previous node

npc.Humanoid:MoveTo(targetNode.Position)
npc.Humanoid.MoveToFinished:Wait()
end
``````

This is all a pretty big rabbit hole, sorry if I just caused more confusion, and let me know if anything is unclear

2 Likes

WOW! Thanks but i think i found easier solution:

``````for _, v in pairs(workspace.PF_Nodes:GetChildren()) do -- Try to find node
Deny = false
for _, g in pairs(Visited) do -- Check if v isn't in table with last visited nodes
if v == g then
Deny = true
end
end
if Deny == false then -- If it isn't try to find closest node
NewReach = (v.Position - CurrentPosition).Magnitude
if NewReach < Reach and NewReach > 10 then
Reach = NewReach
PathTo = v
end
end
end
if PathTo == workspace.Defaltio then -- If we couldn't find node (end of pathway) allow script to return to previously visited node
Reach = 30
for _, v in pairs(workspace.PF_Nodes:GetChildren()) do
NewReach = (v.Position - CurrentPosition).Magnitude
if NewReach < Reach and NewReach > 5 then
Reach = NewReach
PathTo = v
end
end
end
table.insert(Visited, #Visited+1, PathTo) -- Add last destination as visited node
local count = 0
for _, v in pairs(Visited) do
count += 1
end
if count == 3 then -- If there is more than 3 entries in table remove first one
table.remove(Visited, 1)
end
``````
1 Like