NPC Waypoint-Based Custom Grid Pathfinding Bug

[Ethaniel2004 (Ethan)]

I have a script that involves several NPCs traversing paths around the map by moving to different pre-set waypoint parts.

The green parts (normally transparent) are the waypoints that the NPCs move to. Each one of these waypoints is the parent of multiple object values of the adjacent waypoints that are available to move to.

Normally the NPCs walk continuously from waypoint to waypoint and have the chance to take a small break from walking when they reach their destination, but the issue is that occasionally they will go to a full stop of all movement at stay at a waypoint forever.

The NPCs all walk from point to point for awhile but eventually stop in their tracks with the exception of “he who never stops.” Here is my script:

NPCFolder = script.Parent
Characters = NPCFolder.Characters
Waypoints = NPCFolder.Paths.Waypoints

-- Function to move NPC without Timeout
function moveTo(humanoid, targetPoint, CurrentWaypoint)
	local targetReached = false
	if humanoid.Parent:FindFirstChild("Waiting") then
		humanoid.Parent.Waiting:Destroy()
	end

	-- listen for the humanoid reaching its target
	local connection
	connection = humanoid.MoveToFinished:Connect(function(reached)
		targetReached = true
		connection:Disconnect()
		connection = nil
		
		if humanoid.Parent.Name ~= "him"  then -- This if-statement is here to make it so occasinally NPCs will stop in their tracks and consider life choices (unless they are him who never stops)
			local WaitTag = Instance.new("BoolValue", humanoid.Parent) -- add a tag to the player to show they are waiting (for debugging purposes)
			WaitTag.Name = "Waiting"
			local rand = math.random(0, 3) -- set a random number to determine if the NPC should wait first
			if rand == 0 then
				wait(math.random(2,7))
			end
		end
		
		-- Choose the next waypoint from the availible adjacent paths
		local AvailibleWaypoints = CurrentWaypoint.Value:GetChildren()
		local NextWaypoint = AvailibleWaypoints[math.random(1, #AvailibleWaypoints)]

		
		-- Recurse the function
		moveTo(humanoid, NextWaypoint.Value.Position, CurrentWaypoint)
		CurrentWaypoint.Value = NextWaypoint.Value	
	end)

	-- start walking
	humanoid:MoveTo(targetPoint)

	-- execute on a new thread so as to not yield function
	spawn(function()
		while not targetReached do
			-- does the humanoid still exist?
			if not (humanoid and humanoid.Parent) then
				break
			end
			-- has the target changed?
			if humanoid.WalkToPoint ~= targetPoint then
				break
			end
			-- refresh the timeout
			humanoid:MoveTo(targetPoint)
			wait(6)
		end

		-- disconnect the connection if it is still connected
		if connection then
			connection:Disconnect()
			connection = nil
		end
	end)
end

-- Main Moving Loop
for _,NPC in pairs(Characters:GetChildren()) do
	local CurrentWaypoint = Instance.new("ObjectValue", NPC)
	CurrentWaypoint.Name = "CurrentWaypoint"
	
	-- Move the NPC to an initial starting position
	local WaypointsTable = Waypoints:GetChildren()
	
	local StartingWaypoint = WaypointsTable[math.random(1, #WaypointsTable)]
	NPC.PrimaryPart.CFrame = CFrame.new(StartingWaypoint.Position) + Vector3.new(0, 10, 0)
	CurrentWaypoint.Value = StartingWaypoint
	
	
	-- Choose the next availible path to an adjacent waypoint and being moving
	local AvailibleWaypoints = CurrentWaypoint.Value:GetChildren()
	local NextWaypoint = AvailibleWaypoints[math.random(1, #AvailibleWaypoints)]

	moveTo(NPC.Humanoid, NextWaypoint.Value.Position, CurrentWaypoint)
	CurrentWaypoint.Value = NextWaypoint.Value		
end

At this point I am going to go into some speculation of what I think the problem is. The only difference between “He who never stops” and the rest of the NPCs is walkspeed. He runs frighteningly fast at light speed in contrast to the other NPCs who slowly walk around the map. This could potentially be why he never stops because his initial “Humanoid:MoveTo()” is never given the full 8 seconds to time out and he always reaches his destination. The other NPCs might be bugging out because their timeout is resetting and that section of the code is buggy?

The other interesting part is none of the NPCs who are broken and stopped in their tracks forever have the “Waiting” tag, so they are continuously trying to move to the next waypoint but never getting anywhere.

This has stumped me for the past few days so if you guys can help that would be excellent.

enjoy this image of my poorly made roblox steph curry

[bashirAlAsaad]

Yeah you are right if the NPC doesn’t reach the waypoint in time then it will stop moving altogether. maybe try adding some points in the middle of their path to avoid that issue.

[ThanksRoBama (Emma)]

You can work around it by making a custom “MoveTo” function:

function actuallyMoveTo(noob: Model, point: Vector3)
	local c
	c = noob.Humanoid.MoveToFinished:Connect(function(reached)
		c:Disconnect()	
		c = nil
		
		if reached then --MoveTo actually did its job
			noob.Humanoid.MoveToActuallyFinished:Fire()
		else --MoveTo stops for no reason, try again
			actuallyMoveTo(noob, point)
		end
	end)
	
	noob.Humanoid:MoveTo(point)	
end

You can then do the loop thing like this:

while wait() do
    local nextWaypoint = pickWaypoint(noob)
    actuallyMoveTo(noob, nextWaypoint.Position)
    noob.Humanoid.MoveToActuallyFinished.Event:Wait()
    noob.CurrentWaypoint.Value = nextWaypoint
end

Just add a BindableEvent called “MoveToActuallyFinished” into the Humanoid. Here’s a place file you can test it at: Actually MoveTo.rbxl (83.2 KB)

One other thing you should know: Luau can’t do infinitely deep recursion and at some point you’ll get a “Stack Overflow” error. For me it happens at 16300 calls, but it might depend on various factors, I don’t know. You can see this for yourself like this:

local n = 0
function yo()
	n += 1
	if n%100 == 0 or n > 16250 then print(n) wait() end
	yo()
end
yo()

This means your characters would break after walking through ~16k waypoints. Probably no something that’ll actually happen in the lifetime of a server, but hey now you know

[Ethaniel2004 (Ethan)]

Thank you for not only fixing my code but also making it substantially shorter and more efficient.

Here is the full and final script if people want it:

NPCFolder = script.Parent
Characters = NPCFolder.Characters
Waypoints = NPCFolder.Paths.Waypoints

-- Function to move NPC without Timeout
function actuallyMoveTo(noob: Model, point: Vector3)
	local c
	c = noob.Humanoid.MoveToFinished:Connect(function(reached)
		c:Disconnect()	
		c = nil

		if reached then --MoveTo actually did its job
			noob.Humanoid.MoveToActuallyFinished:Fire()
		else --MoveTo stops for no reason, try again
			actuallyMoveTo(noob, point)
		end
	end)

	noob.Humanoid:MoveTo(point)	
end

-- Select the next waypoint from the list of availible adjacent paths
function pickWaypoint(CurrentWaypoint,LastWaypoint)
	local AvailibleWaypoints = CurrentWaypoint.Value:GetChildren()
	local NextWaypoint = AvailibleWaypoints[math.random(1, #AvailibleWaypoints)]
	
	return NextWaypoint 
end

-- Main Moving Loop
for _,NPC in pairs(Characters:GetChildren()) do
	local CurrentWaypoint = Instance.new("ObjectValue", NPC)
	CurrentWaypoint.Name = "CurrentWaypoint"
	
	local MoveToActuallyFinished = Instance.new("BindableEvent", NPC.Humanoid) -- Custom event 
	MoveToActuallyFinished.Name = "MoveToActuallyFinished"
	
	-- Move the NPC to an initial starting position
	local WaypointsTable = Waypoints:GetChildren()
	
	local StartingWaypoint = WaypointsTable[math.random(1, #WaypointsTable)]
	NPC.PrimaryPart.CFrame = CFrame.new(StartingWaypoint.Position) + Vector3.new(0, 10, 0)
	CurrentWaypoint.Value = StartingWaypoint
	
	
	-- Continuously keep moving the NPC in a separate thread
	spawn(function()
		while wait() do
			local nextWaypoint = pickWaypoint(CurrentWaypoint)
			actuallyMoveTo(NPC, nextWaypoint.Value.Position)
			NPC.Humanoid.MoveToActuallyFinished.Event:Wait()
			NPC.CurrentWaypoint.Value = nextWaypoint.Value
			
			if NPC.Name ~= "him"  then -- This if-statement is here to make it so occasinally NPCs will stop in their tracks and consider life choices (unless they are him who never stops)
				local rand = math.random(0, 5) -- set a random number to determine if the NPC should wait first
				if rand == 0 then
					wait(math.random(2,7))
				end
			end
		end
	end)	
end

And yes when I originally wrote this code I was trying to cause stack overflows but thank you for the heads up lol