Pathfinding - NPC Pushing and getting stuck

Help and Feedback Scripting Support
#1

NPC uses PathfindingService

-My NPC frequently gets stuck on corners in the map (it is a basic maze)

-With multiple NPCs, they all follow the same path meaning they get stuck running behind each other instead of running next to them

I do not know how to fix this, it would be great if someone could help.
Code:

function PathfindToPos(Pos,OverWrite)
	if Pathing == false then
		spawn(function()
			Pathing = true
			local RenderedPath=PathfindingService:ComputeRawPathAsync(HRP.Position,Pos,500)
			local RenderedPathCoordinates=RenderedPath:GetPointCoordinates()
			local TimeOutNum = 2
			local Ting = StopPathfinding
			if Ting == true and OverWrite == true then 
				Ting = false 
			end
			for _= 1,#RenderedPathCoordinates do
				if not CanSee and Ting == false then
					local Point=RenderedPathCoordinates[_]
					local CurrentTime = tick()

					repeat wait()
						Humanoid:MoveTo(Point)
						Ting = StopPathfinding 
						if Ting == true and OverWrite == true then 
							Ting = false 
						end
						if (tick() - CurrentTime > TimeOutNum) or Ting then 
							break
						end
					until(HRP.Position-Point).Magnitude<5 or (tick() - CurrentTime > TimeOutNum) or CanSee or Ting
					
					if (tick() - CurrentTime > TimeOutNum) then
						warn("Time out")
					end
					if (tick() - CurrentTime > TimeOutNum) or CanSee then 
						break
					end
				end
			end
			Pathing = false
		end)
	end	
end
6 Likes
#2

The best solution to NPCs getting stuck in one point should be checking if they have travelled(changed their position) a certain distance under a certain time.

If they aren’t moving much, they will be redirected to closest point with rays before proceeding to their destination, to check for clear paths(which ignore all movable objects such as characters).

1 Like
#3

Hmm, you might be right. My old pathfinding function was more advanced, and this didn’t really happen but it caused the game to slow down sufficiently. Also, it does show when it’s stuck:
> warn("Time out")

This is what basically happens: https://gyazo.com/9f40c2b59ca6a51d9f3b8dfade7538b4

5 Likes
#4

I just found your method, PathfindingService:ComputeRawPathAsync, on devforums, and it was deprecated in Patch 309, more than a year ago. It does not show up on the wiki either.

The new method, PathfindingService:CreatePath, has an agentParameters argument, which lets you turn off jumping or keep characters from snagging to walls. It also considers moving parts, which means you could just rerun path:ComputeAsync if multiple NPC’s get stuck on each other.

I hope that helps…

2 Likes
#5

The problem doesn’t change unfortunately.

function PathfindToPos(Pos,OverWrite)
	if Pathing == false then
		spawn(function()
			Pathing = true
			local Path = PathfindingService:CreatePath()
			Path:ComputeAsync(HRP.Position,Pos)
			local Waypoints = Path:GetWaypoints()
			
			local TimeOutNum = 2
			local Ting = StopPathfinding
			if Ting == true and OverWrite == true then 
				Ting = false 
			end
			
			if Path.Status == Enum.PathStatus.Success then
				for _, Point in pairs(Waypoints) do
					if not CanSee and Ting == false then
						local CurrentTime = tick()
						repeat wait()
							Humanoid:MoveTo(Point.Position)
							Ting = StopPathfinding 
							if Ting == true and OverWrite == true then 
								Ting = false 
							end
							if (tick() - CurrentTime > TimeOutNum) or Ting then 
								break
							end
						until(HRP.Position-Point.Position).Magnitude<5 or (tick() - CurrentTime > TimeOutNum) or CanSee or Ting
						
						if (tick() - CurrentTime > TimeOutNum) then
							warn("Time out")
						end
						if (tick() - CurrentTime > TimeOutNum) or CanSee then 
							break
						end
					end
				end
			else
				warn("Couldn't find path")
				NormalFollow(Pos)
			end
			Pathing = false
		end)
	end	
end
1 Like
#6

Try replacing:

local Path = PathfindingService:CreatePath()

with:

local Path = PathfindingService:CreatePath({AgentRadius = 4})

It should give more room for error when pathfinding around walls.

1 Like
#7

I changed it to AgentRadius = 5, and you’re right it is slightly better. Setting AgentRadius more than 5 doesn’t find paths at all though, and to be honest I’m not quite sure what it means, do you know?

#8

It means that the corridor PathfindingService is trying to navigate through is too narrow, specifically less than 6 studs, for a path to be found.
If you want to give PathFindingService an even easier time, you should either:

  • make the walls of your maze thicker, which will cause the next waypoint to be placed at a relatively softer angle,
  • make the maze overall larger, for a larger AgentRadius, or, the least believable one,
  • make the NPC smaller, which makes him butter smooth against those walls.
  • worst-case and easiest scenario, you can just teleport the NPC to the next waypoint. I believe they aren’t too far from each other, so it should still be believable.
2 Likes
#9

Made map bigger and walls thicker, overall the pathfinding is smoother now, although there are little places where for some reason it cannot find a path. Thank you for this!

Moving onto second point, how would I go about making NPC’s not following the exact same path? (or so they do not run into each other from behind when pathfinding)

1 Like
#10

I definitely know that pathfinding can’t be used to find multiple paths at once. However, you can create a function that places sets of checkpoints in your maze, and you can just call Path:ComputeAsync to a credible neighbor.

If you have some sort of maze building algorithm in place, you could probably mark nodes where three paths branch off from one node, create a function to connect any number of nodes from the starting point to the destination (the last code block down there), and use path:ComputeAsync between those nodes instead.

If you have a static maze that is already built, you can just mark these three-way nodes yourself and use that same algorithm.

You would have to start with a node collection, which is just the position of the node combined with any neighbors the node has:

NodeCollection = {
  --node name = {position, neighbor nodes} 
	Start = {Vector3.new(...), {"node1"} }
	node1 = {Vector3.new(...), {"node2","node3"} }
	node2 = {...},
	node3 = {...},
	...
	nodeN = {...}, -- N can really be any number fyi
	Dest = {...}
}

Generating NodeCollection could be done with either a folder or model of pre-generated parts and ObjectValues/StringValues, or you can generate them yourself if you build by algorithm.

--[[ Explorer Structure
- Source
  - Part
    - Value
    - Value
    - ...
--]]
local Source = -- folder/model here
local NodeCollection = {}
for _,part in pairs(Source:GetChildren()) do
	local neighbors = {}
	for _,value in pairs(part:GetChildren()) do
		table.insert(neighbors,value.Value) -- .Name if it's an object
	end
	NodeCollection[part.Name] = {part.Position, neighbors}
end

This would be the algorithm I would use to move between nodes:

function Traverse()
	local function pickNext(node) -- choose a random node from its neighbors
		local neighbors = node[2]
		local newNeighbor = neighbors[ math.random(#neighbors) ]
		return NodeCollection[newNeighbor]
	end
	local currNode = pickNext( NodeCollection["Start"] )
	while wait() do -- can be true if you trust yourself
		path:ComputeAsync(NPC.Position, currNode[1])
		--print(path.Status)
		if path.Status == Enum.PathStatus.Success then
			for _,pt in pairs(path:GetWaypoints()) do
				humanoid:MoveTo(pt.Position)
				humanoid.MoveToFinished:Wait()
				--[[
				if pt.Action == Enum.PathWaypoint.Jump then
					humanoid.Jump = true
				end
				--]]
			end
		else
			-- handler here
			break
		end
		if currNode == NodeCollection["Dest"] then
			break
		end
		currNode = pickNext(currNode)
	end
end

I tested it in Studio, it seems to work fine. I hope this helps.

1 Like
#11

Thank you for this, I think it is the best way and pathfinding isn’t that reliable so I guess if I want my pathfinding to be complex enough I’ll have to create my own paths.

1 Like
#12

This is true but what if ur npc ai have a script that fights players and so they stop moving to fight them? I feel like this wouldn’t work under that circumstance

#13

They’ll start moving to the right or left(or a point around the wall) if they can’t close the gap or the player is moving further away. This is a behavior found in Fantastic Frontier for a few AIs only.

They will enter a combat loop until the player is out-of-reach, died or impossible to reach, due to lack of a proper path. The AI will calculate their path around trying to find nearest point to with raycast towards the player to see if any parts are blocking the way.

#15

Although this thread has been marked with a solution a couple months ago, I’m wondering:

Could the NPCs be grouped in a PhysicsService CollisionGroup so they don’t collide with each other, but still collide with other objects in the game? As described in https://developer.roblox.com/articles/Collision-Filtering-Team-Doors

Or else could the function that performs Pathfinding and Humanoid:MoveTo include a ray cast or region3 check around the NPC to detect other NPCs (or even just detect any game objects at all) then stop moving with Humanoid:MoveTo(HumanoidRootPart.Position) and then Wait() or Heartbeat before check for presence of the same object, and finally start moving again if the object has moved. Intent being create a staggered delay in the movement or any trailing NPCs.

Would either of those approaches be feasible to stop NPCs from bumping into each other, specifically?

1 Like
#16

Bumping into each other is a problem, but that only happens because they follow the same path and I use PathfindingService. So there isn’t a great fix for it really but the second one could work, or get it stuck and have choppy movements.

1 Like