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 :sweat_smile: 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 :slight_smile:

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