NPC Pathfinding System - Looking for tips to improve performance

Recently I wrote a simple pathfinding npc system along with greatly optimizing it

The npc model properties such as: CanCollide, CanQuery, CanTouch, and CastShadow set to off
Code part has been simplified as I could make it be, instead of setting each NPC CFrame seperately I use Roblox’s BulkMove Api, because as I know this method doesnt apply any updates on physics of the model and only change the position of it.

The system is OOP structured. Client-sided rendering and server-sided spawn replication to all the clients.

My current goal is to improve the performance of my code as much as possible


What I tried and did not work:

  • Using Parallel Luau and creating a seperate actor for each NPC, resulted in almost the whole movement code being REQUIRED to run in serial. The conclusion is using chopped Parallel Luau to move parts is less performant than the serial way.

  • Anchoring all the parts inside of a npc model and not just PrimaryPart with welding them to each other. Did not work for idk reason

My suggestions:

  • PartCache and ObjectCache are looking like a good option to use in my case, although reading their logic of work they didn’t seem anything special.

Changes:

Update 1

Converted the NPC Model into one skinned mesh along with rigging it, and instead of using
BulkMove I switched up to changing CFrame of main bone of the NPC. This ended up on giving 2x more performance.

Update 2

Replaced some of unnecessary math calculations out of a “while” loop. Surprisingly gave another ~30% performance


First Benchmark

export

Latest Benchmark

export

Place: NPC System Stress Test - Roblox

Code

Find in latest update : )

I’m up for any of your ideas

1 Like

Anchored parts cannot be welded together : -)

If you want to squeeze out the most performance, you can convert NPCs into just one skinned mesh, and use bones to move the “limbs”. This ends up being way more performant than having 6 parts.

Update 1

The performance gain is around 200%
Now with 1000 moving npcs fps lock at around 144-156 fps and with 2500 npcs its 42-46 fps

Even with that huge boost I’m still concerned about efficiency of my code, could you look at it and tell me if there’s something I can do to make it more performant?

Update 1 Script
local Replicate = game:GetService('ReplicatedStorage')
local PathfindingService = game:GetService("PathfindingService")
local runService = game:GetService('RunService')

local Ticks = 60
local walkRange = 200

local class = {}
class.__index = class

local entities = {}

function class.start()
	runService.Heartbeat:Connect(BulkMove)
end

-- Parameters
local StepStuds = 50

function class.New(index : number, model : Model)
	local self = setmetatable({},class)
	self.Index = index
	self.Character = model:Clone()
	self.Character.Parent = workspace.NPCs
	self.ControlBone = self.Character.PrimaryPart.Torso
	self.CFrame = self.ControlBone.WorldCFrame
	self.Path = PathfindingService:CreatePath()

	entities[self.Index] = self
	
	Step(self)
	return self
end

function Step(self)
	while true do
		local randomPoint = Vector3.new(math.random(-walkRange,walkRange), 0, math.random(-walkRange,walkRange))
		self.Path:ComputeAsync(self.CFrame.Position, randomPoint)

		local wps = self.Path:GetWaypoints()

		for i=2,#wps do
			local waypointPosition = Vector3.new(wps[i].Position.X,self.CFrame.Position.Y,wps[i].Position.Z)
			self.CFrame = CFrame.lookAt(self.CFrame.Position, waypointPosition)
			while true do
				self.CFrame += self.CFrame.LookVector * (StepStuds/Ticks)
				if (waypointPosition - self.CFrame.Position).Magnitude <= 1 then
					break
				end
				task.wait(1/Ticks)
			end
		end
	end
end

function BulkMove()
	for index, entity in entities do
		entity.ControlBone.WorldCFrame = entity.CFrame
	end
end

--

Replicate.Events.Server.npcAdded.OnClientEvent:Connect(class.New)

return class

Update 2

Replaced unnecessary math calculations out of a “while” loop and rewrote the whole functionality of the script. This gave another ~30% performance gain

Update 2 Script
local Replicate = game:GetService('ReplicatedStorage')
local PathfindingService = game:GetService("PathfindingService")
local runService = game:GetService('RunService')

local class = {}
class.__index = class

local entities = {}

function class.start()
	runService.Heartbeat:Connect(BulkMove)
end

-- Parameters
local Ticks = 60
local StepStud = 25/Ticks
local StepWait = 1/Ticks

--- Creation & Main Functions

function class.New(index : number, model : Model)
	local self = setmetatable({},class)
	self.Index = index
	self.Character = model:Clone()
	self.Character.Parent = workspace.NPCs
	self.ControlBone = self.Character.PrimaryPart.Torso
	self.CFrame = self.ControlBone.WorldCFrame
	self.Path = PathfindingService:CreatePath()
	self.Moving = false

	entities[self.Index] = self

	task.defer(self:Start())
	return self
end

function class:Start()
	if self.Moving == true then return end
	self.Moving = true
	while true do
		self.Path:ComputeAsync(self.CFrame.Position, GetRandomPoint(200))
		local Waypoints = self.Path:GetWaypoints()
		
		for index = 2, #Waypoints do
			if self.Moving == false then break end
			local waypointPosition = Vector3.new(Waypoints[index].Position.X,self.CFrame.Position.Y,Waypoints[index].Position.Z)
			self.CFrame = CFrame.lookAt(self.CFrame.Position, waypointPosition)
			
			local Step = self.CFrame.LookVector * StepStud
			while task.wait(StepWait) do
				self.CFrame += Step
				if (self.CFrame.Position - waypointPosition).Magnitude <= 1 then break end
			end
		end
	end
end

function class:Stop()
	if self.Moving == false then return end
	self.Moving = false
end

--------- Secondary Functions

function GetRandomPoint(Value)
	return Vector3.new(math.random(-Value,Value), 0, math.random(-Value,Value))
end

---------- Move Part

function BulkMove()
	for index, entity in entities do
		entity.ControlBone.WorldCFrame = entity.CFrame
	end
end

----- Events

Replicate.Events.Server.npcAdded.OnClientEvent:Connect(class.New)

return class

  1. Don’t use OOP for npc systems. Use ECS instead. It’s one of the few areas where ECS can provide a much larger performance boost.

  2. Idk how you are handling collision, but if you want a lot of npcs to be performant, you need a custom physics engine. I also recommend spacial hashgrid which allows for very easy multi threading and it’s also O(N)

I’ve already implemented Jecs ECS System and it seems to be working fine I can already see the performance gain.

Although I’m still curious about how exactly should spatial hashgrid help in my case, I surfed a little bit and it seems to be used only for detecting objects in space. The only thing I can imagine using it for is distance check between the npc model and current waypoint position

What does O(N) mean?

The only post saying something alike to my case is:

But I still didn’t understand what is the purpose of using Octree, Spatial Hash Grid, Quadtree and etc. in npc systems

Spacial hashgrid is used to optimize and multi thread collision detection. How are you handling collisions between npcs and the environment?

Hi! Glad you are seeing some performance gains with jecs. However, as noted in my article, uniform data is better off put into specialized index structures such as octrees as a complementary to the ECS itself. This means you can store the octree as a component, with a separate function to walk that tree.

It is very useful to learn as many data structures and algorithms as possible, ECS is not a silver bullet and learning to use these things together will help you absolutely maximize performance.