Pathfinding optimization

Maks66606 · May 26, 2022, 6:47pm

Hello all

What do you want to achieve?
Fast and good pathfinding for enemies in my game
What is the issue?
I’ve implemented a pathfinding script for my enemies (following a bit of a tutorial) but It is quite slow and laggy and I don’t know how to go about it

(Keep in mind I’ve also searched on Developer Hub and though some answers could help I feel that this still will be a valid thread)

(pastebin code)

local PathfindingService = game:GetService("PathfindingService")
local enemies = game:GetService("ServerStorage").Enemies:GetChildren()

local Enemy = {}
Enemy.__index = Enemy

function Enemy.new(spawnPoint)
	local self = setmetatable({}, Enemy)
	local enemy = Enemy:Spawn(spawnPoint)
	self.Enemy = enemy
	self.Humanoid = enemy:WaitForChild("Humanoid")
	self.Root = enemy:WaitForChild("HumanoidRootPart")
	self.Root:SetNetworkOwner(enemy)
	self.Health = enemy:GetAttribute("Health")
	self.Humanoid.MaxHealth = self.Health
	self.Damage = enemy:GetAttribute("Damage")
	self.Target = nil
	
	return self
end

function Enemy:Init()
	while wait(0.1) do
		if self.Humanoid.Health < 1 then
			break
		end
		self:FindTarget()
		if self.Target then
			self.Humanoid.WalkSpeed = 16
			self:FindPath()
		else
			self.Humanoid.WalkSpeed = 8
			self:Wander()
		end
	end
end

function Enemy:Spawn(spawnPoint)
	local enemy = enemies[math.random(1, #enemies)]:Clone()
	enemy.Parent = workspace
	enemy:SetPrimaryPartCFrame(spawnPoint.CFrame)
	
	return enemy
end

function Enemy:Wander()
	local xRand = math.random(-50, 50)
	local zRand = math.random(-50, 50)
	local goal = self.Root.Position + Vector3.new(xRand, 0, zRand)
	
	local path = PathfindingService:CreatePath()
	path:ComputeAsync(self.Root.Position, goal)
	local waypoints = path:GetWaypoints()
	
	if path.Status == Enum.PathStatus.Success then
		for _, waypoint in ipairs(waypoints) do
			if waypoint.Action == Enum.PathWaypointAction.Jump  then
				self.Humanoid.Jump = true
			end
			self.Humanoid:MoveTo(waypoint.Position)
			local timeOut = self.Humanoid.MoveToFinished:Wait(1)
			if not timeOut then
				print("Enemy Stuck")
				self.Humanoid.Jump = true
				self:Wander()
			end
		end
	else
		print("Path failed")
		self:Wander()
	end
end

function Enemy:CheckSight()
	if self.Target then
		local ray = Ray.new(self.Root.Position, (self.Target.Position - self.Root.Position).Unit * 40)
		local hit, position = workspace:FindPartOnRayWithIgnoreList(ray, {self.Enemy})
		if hit then
			if hit:IsDescendantOf(self.Target) and math.abs(hit.Position.Y - self.Root.Position.Y) < 3 then
				print("Enemy can see the target")
				return true
			end
		end
		return false
	else
		return false
	end
end

function Enemy:FindTarget()
	local distance = 200
	local potentialTargets = {}
	local seeTargets = {}
	for i, v in ipairs(workspace:GetChildren()) do
		local human = v:FindFirstChild("Humanoid")
		local torso = v:FindFirstChild("Torso") or v:FindFirstChild("HumanoidRootPart")

		if human and torso and v.Name ~= self.Enemy.Name then
			if (self.Root.Position - torso.Position).magnitude < distance and human.Health > 0 then
				table.insert(potentialTargets, torso)
			end
		end
	end
	if #potentialTargets > 0 then
		for i, v in ipairs(potentialTargets) do
			if self:CheckSight() then
				table.insert(seeTargets, v)
			elseif #seeTargets == 0 and (self.Root.Position - v.Position).magnitude < distance then
				self.Target = v
				distance = (self.Root.Position - v.Position).magnitude
			end
		end
	end
	if #seeTargets > 0 then
		distance = 200
		for i, v in ipairs(seeTargets) do
			if (self.Root.Position - v.Position).magnitude < distance then
				self.Target = v
				distance = (self.Root.Position - v.Position).magnitude
			end
		end
	end
end

function Enemy:FindPath()
	local path = PathfindingService:CreatePath()
	path:ComputeAsync(self.Root.Position, self.Target.Position)
	local waypoints = path:GetWaypoints()
	
	if path.Status == Enum.PathStatus.Success then
		for _, waypoint in ipairs(waypoints) do
			if waypoint.Action == Enum.PathWaypointAction.Jump then
				self.Humanoid.Jump = true
			end
			self.Humanoid:MoveTo(waypoint.Position)
			local timeOut = self.Humanoid.MoveToFinished:Wait(1)
			if not timeOut then
				self.Humanoid.Jump = true
				self:FindPath()
				break
			end
			if self:CheckSight() then
				repeat
					print("Moving to target")
					self.Humanoid:MoveTo(self.Target.Position)
					wait(0.1)
					if self.Target == nil then
						break
					elseif self.Target.Parent == nil then
						break
					end
				until self:CheckSight() == false or self.Humanoid.Health < 1 or self.Target.Parent.Humanoid.Health < 1
				break
			end
			if (self.Root.Position - waypoints[1].Position).magnitude > 20 then
				print("Target has moved, generating new path")
				self:FindPath()
				break
			end
		end
	end
end

return Enemy

(pastebin code)

local Enemy = require(script.Parent.Enemy)
local PlayerManager = require(script.Parent.PlayerManager)
local spawns = workspace.EnemySpawns:GetChildren()

local function FindSpawnPoint()
	return spawns[math.random(1, #spawns)]
end

PlayerManager.PlayerAdded:Connect(function()
	local enemy = Enemy.new(FindSpawnPoint())
	enemy:Init()
end)

You can see on the video below how does it lag and how easy it is to overtake the enemy and run away

alessdai · May 26, 2022, 6:50pm

You could replace the wait(0.1) with something like game:GetService('RunService').Heartbeat:wait()

Depending on your code and how frequently Enemy:FindPath() is called this can be really expensive performance-wise (or not)

Maks66606 · May 26, 2022, 6:53pm

It changes enemy movement a bit for better but it is still very visible how slow he is (mostly on changing path when you turn).

V_ladzec · May 26, 2022, 6:54pm

Raycast from enemy RootPart to target character and if there is a hit then use pathfinding service to find path else if there is no hit that means enemy can just move straightforward

-- wrap this inside loop for example RunService.Heartbeat
EnemyHumanoid:MoveTo(TargetPosition)

Maks66606 · May 26, 2022, 6:56pm

Okay, makes sense, though where would I put it in my code? Somewhere in Enemy:FindPath()?

V_ladzec · May 26, 2022, 7:03pm

i havent read the whole module but if Enemy.new() returns created enemy you can simply do

while true do
    Enemy:FindTarget()
    if Enemy.Target then

        local origin = Enemy.PrimaryPart.Position
        local direction = origin - Enemy.Target.PrimaryPart.Position

        local result = workspace:Raycast(origin, direction, raycastparams) -- put params to raycast wont hit enemy

        if result then
            Enemy:FindPath()
        else
            Enemy.Humanoid:WalkTo(Enemy.Target.PrimaryPart.Position)
        end

    end
    RunService.Heartbeat:Wait()
end

wrap that in while loop so Enemy:FindPath() will yield

Maks66606 · May 26, 2022, 7:05pm

Well, Enemy:Init() handles calling all the functions, so I would rather just add it in FindPath() so there can be 2 options : either change the path or walk forward, right? But I don’t think It will solve the slow movement and slow turning of the enemy, will it?
Somewhere here where we loop thru waypoints

V_ladzec · May 26, 2022, 7:09pm

i guess raycast from enemy to target inside Enemy:FindPath()

local result = workspace:Raycast(origin, direction, params)
if result then
    -- search for path
else
    Humanoid:MoveTo(Target.PrimaryPart.Position)
end

Maks66606 · May 26, 2022, 7:24pm

I’ve implemented it but it didn’t change anything at all. Looking for more solutions

Maks66606 · May 26, 2022, 7:30pm

A significant fix was just to remove this

local timeOut = self.Humanoid.MoveToFinished:Wait(1)
if not timeOut then
	self.Humanoid.Jump = true
	self:FindPath()
	break
end

V_ladzec · May 26, 2022, 7:59pm

had edited Enemy.new(), Enemy:Init(), Enemy:CheckSight() and Enemy:FindPath() couldnt test so if there is something weird tell me

Module

local PathfindingService = game:GetService("PathfindingService")
local ServerStorage = game:GetService("ServerStorage")
local RunService = game:GetService("RunService")

local enemies = ServerStorage.Enemies:GetChildren()

local Enemy = {}
Enemy.__index = Enemy

function Enemy.new(spawnPoint)
	local self = setmetatable({}, Enemy)
	local enemy = Enemy:Spawn(spawnPoint)
	local Params = RaycastParams.new()
	Params.FilterType = Enum.RaycastFilterType.Blacklist
	Params.FilterDescendantsInstances = {enemy}
	self.Params = Params
	self.Enemy = enemy
	self.Humanoid = enemy:WaitForChild("Humanoid")
	self.Root = enemy:WaitForChild("HumanoidRootPart")
	self.Root:SetNetworkOwner(enemy)
	self.Health = enemy:GetAttribute("Health")
	self.Humanoid.MaxHealth = self.Health
	self.Damage = enemy:GetAttribute("Damage")
	self.Target = nil

	return self
end

function Enemy:Init()
	while true do
		if self.Humanoid.Health <= 0 then
			break
		end
		self:FindTarget()
		if self.Target and not self:CheckSight() then
			self.Humanoid.WalkSpeed = 16
			self:FindPath()
		elseif self.Target then
			self.Humanoid:WalkTo(self.Target.Position)
		else
			self.Humanoid.WalkSpeed = 8
			self:Wander()
		end
		RunService.Heartbeat:Wait()
	end
end

function Enemy:Spawn(spawnPoint)
	local enemy = enemies[math.random(1, #enemies)]:Clone()
	enemy.Parent = workspace
	enemy:SetPrimaryPartCFrame(spawnPoint.CFrame)

	return enemy
end

function Enemy:Wander()
	local xRand = math.random(-50, 50)
	local zRand = math.random(-50, 50)
	local goal = self.Root.Position + Vector3.new(xRand, 0, zRand)

	local path = PathfindingService:CreatePath()
	path:ComputeAsync(self.Root.Position, goal)
	local waypoints = path:GetWaypoints()

	if path.Status == Enum.PathStatus.Success then
		for _, waypoint in ipairs(waypoints) do
			if waypoint.Action == Enum.PathWaypointAction.Jump  then
				self.Humanoid.Jump = true
			end
			self.Humanoid:MoveTo(waypoint.Position)
			self.Humanoid.MoveToFinished:Wait()
		end
	else
		print("Path failed")
		self:Wander()
	end
end

function Enemy:CheckSight(Position)
	if self.Target or Position then
		self.Params.FilterDescendantsInstances = {
			self.Enemy,
			self.Target
		}
		local origin = self.Root.Position
		local direction = origin - (Position or self.Target and self.Target.Position)
		local result = workspace:Raycast(origin, direction, self.Params)
		if result then
			print("Enemy cant see the target")
			return false
		end
		return true
	else
		return false
	end
end

function Enemy:FindTarget()
	local distance = 200
	local potentialTargets = {}
	local seeTargets = {}
	for i, v in ipairs(workspace:GetChildren()) do
		local human = v:FindFirstChild("Humanoid")
		local root = v:FindFirstChild("HumanoidRootPart")

		if human and root and v.Name ~= self.Enemy.Name then
			if (self.Root.Position - root.Position).magnitude < distance and human.Health > 0 then
				table.insert(potentialTargets, root)
			end
		end
	end
	if #potentialTargets > 0 then
		for i, v in ipairs(potentialTargets) do
			if self:CheckSight() then
				table.insert(seeTargets, v)
			elseif #seeTargets == 0 and (self.Root.Position - v.Position).magnitude < distance then
				self.Target = v
				distance = (self.Root.Position - v.Position).magnitude
			end
		end
	end
	if #seeTargets > 0 then
		distance = 200
		for i, v in ipairs(seeTargets) do
			if (self.Root.Position - v.Position).magnitude < distance then
				self.Target = v
				distance = (self.Root.Position - v.Position).magnitude
			end
		end
	end
end

function Enemy:FindPath()
	if self.Target then
		local path = PathfindingService:CreatePath()
		path:ComputeAsync(self.Root.Position, self.Target.Position)
		local waypoints = path:GetWaypoints()
		if path.Status == Enum.PathStatus.Success then
			for _, waypoint in ipairs(waypoints) do
				if waypoint.Action == Enum.PathWaypointAction.Jump then
					self.Humanoid.Jump = true
				end
				self.Humanoid:MoveTo(waypoint.Position)
				self.Humanoid.MoveToFinished:Wait()
				if self:CheckSight() then
					break
				elseif (self.Root.Position - waypoints[1].Position).magnitude > 20 then
					print("Target has moved, generating new path")
					self:FindPath()
					break
				end
			end
		end
	end
end

return Enemy

Maks66606 · May 26, 2022, 9:05pm

V_ladzec:

local PathfindingService = game:GetService("PathfindingService")
local ServerStorage = game:GetService("ServerStorage")
local RunService = game:GetService("RunService")

local enemies = ServerStorage.Enemies:GetChildren()

local Enemy = {}
Enemy.__index = Enemy

function Enemy.new(spawnPoint)
	local self = setmetatable({}, Enemy)
	local enemy = Enemy:Spawn(spawnPoint)
	local Params = RaycastParams.new()
	Params.FilterType = Enum.RaycastFilterType.Blacklist
	Params.FilterDescendantsInstances = {enemy}
	self.Params = Params
	self.Enemy = enemy
	self.Humanoid = enemy:WaitForChild("Humanoid")
	self.Root = enemy:WaitForChild("HumanoidRootPart")
	self.Root:SetNetworkOwner(enemy)
	self.Health = enemy:GetAttribute("Health")
	self.Humanoid.MaxHealth = self.Health
	self.Damage = enemy:GetAttribute("Damage")
	self.Target = nil

	return self
end

function Enemy:Init()
	while true do
		if self.Humanoid.Health <= 0 then
			break
		end
		self:FindTarget()
		if self.Target and not self:CheckSight() then
			self.Humanoid.WalkSpeed = 16
			self:FindPath()
		elseif self.Target then
			self.Humanoid:WalkTo(self.Target.Position)
		else
			self.Humanoid.WalkSpeed = 8
			self:Wander()
		end
		RunService.Heartbeat:Wait()
	end
end

function Enemy:Spawn(spawnPoint)
	local enemy = enemies[math.random(1, #enemies)]:Clone()
	enemy.Parent = workspace
	enemy:SetPrimaryPartCFrame(spawnPoint.CFrame)

	return enemy
end

function Enemy:Wander()
	local xRand = math.random(-50, 50)
	local zRand = math.random(-50, 50)
	local goal = self.Root.Position + Vector3.new(xRand, 0, zRand)

	local path = PathfindingService:CreatePath()
	path:ComputeAsync(self.Root.Position, goal)
	local waypoints = path:GetWaypoints()

	if path.Status == Enum.PathStatus.Success then
		for _, waypoint in ipairs(waypoints) do
			if waypoint.Action == Enum.PathWaypointAction.Jump  then
				self.Humanoid.Jump = true
			end
			self.Humanoid:MoveTo(waypoint.Position)
			self.Humanoid.MoveToFinished:Wait()
		end
	else
		print("Path failed")
		self:Wander()
	end
end

function Enemy:CheckSight(Position)
	if self.Target or Position then
		self.Params.FilterDescendantsInstances = {
			self.Enemy,
			self.Target
		}
		local origin = self.Root.Position
		local direction = origin - (Position or self.Target and self.Target.Position)
		local result = workspace:Raycast(origin, direction, self.Params)
		if result then
			print("Enemy cant see the target")
			return false
		end
		return true
	else
		return false
	end
end

function Enemy:FindTarget()
	local distance = 200
	local potentialTargets = {}
	local seeTargets = {}
	for i, v in ipairs(workspace:GetChildren()) do
		local human = v:FindFirstChild("Humanoid")
		local root = v:FindFirstChild("HumanoidRootPart")

		if human and root and v.Name ~= self.Enemy.Name then
			if (self.Root.Position - root.Position).magnitude < distance and human.Health > 0 then
				table.insert(potentialTargets, root)
			end
		end
	end
	if #potentialTargets > 0 then
		for i, v in ipairs(potentialTargets) do
			if self:CheckSight() then
				table.insert(seeTargets, v)
			elseif #seeTargets == 0 and (self.Root.Position - v.Position).magnitude < distance then
				self.Target = v
				distance = (self.Root.Position - v.Position).magnitude
			end
		end
	end
	if #seeTargets > 0 then
		distance = 200
		for i, v in ipairs(seeTargets) do
			if (self.Root.Position - v.Position).magnitude < distance then
				self.Target = v
				distance = (self.Root.Position - v.Position).magnitude
			end
		end
	end
end

function Enemy:FindPath()
	if self.Target then
		local path = PathfindingService:CreatePath()
		path:ComputeAsync(self.Root.Position, self.Target.Position)
		local waypoints = path:GetWaypoints()
		if path.Status == Enum.PathStatus.Success then
			for _, waypoint in ipairs(waypoints) do
				if waypoint.Action == Enum.PathWaypointAction.Jump then
					self.Humanoid.Jump = true
				end
				self.Humanoid:MoveTo(waypoint.Position)
				self.Humanoid.MoveToFinished:Wait()
				if self:CheckSight() then
					break
				elseif (self.Root.Position - waypoints[1].Position).magnitude > 20 then
					print("Target has moved, generating new path")
					self:FindPath()
					break
				end
			end
		end
	end
end

return Enemy

It seems to be working just fine but there should be MoveTo instead of WalkTo in the Init() function and also enemy seems to be jumping when chasing a player which looks a bit unnatural, do you know why’s that?

V_ladzec · May 26, 2022, 9:21pm

try printing waypoint.Action and see whats wrong