Best way to make updating pathfinding AI?

eyrtuiop232 · February 11, 2021, 2:53pm

So, i’ve been trying to make pathfinding AI for my game, i tried various method currently the best one i have got 5% activity when theres 50 humanoids in one place and 1 - 2% activity when theres 15 humanoids in one place, i want to optimize this even further but i have no idea on how to do it.

my current method is using PathfindingService, so i use MoveToFinished event and only updates the path when needed.
it works great, but i still want to optimize this even further.

i’ve tried raycasting method and it got 14% activity when theres 7 humanoids in one place.

i also try to search on forum but didnt found the answer.

EDIT :
I tried A*, so with A* it depends on the range and the map complexity between the start and end. if the range is short and the map is simple it will costs very little performance.
and A* is customizable.
with this script i got 5 ~ 6% activity if i visualize the part.

A* Script

local function CreatePath(start,endd,height,gap,visual)
	local function createPart(y)
		if y == nil then
			y = 0.1
		end
		local cube = Instance.new("Part",workspace)
		cube.Anchored = true
		cube.CanCollide = false
		cube.Size = Vector3.new(gap,y,gap)
		cube.Material = Enum.Material.Plastic
		cube.BrickColor = BrickColor.White()
		--game.Debris:AddItem(cube,0.1)
		--table.insert(parts,cube)
		return cube
	end

	local function createCube(pos)
		local positions = {
			pos + Vector3.new(-gap,0,gap),
			pos - Vector3.new(-gap,0,gap),
			pos + Vector3.new(0,0,-gap),
			pos + Vector3.new(-gap,0,0),
			pos + Vector3.new(0,0,gap),
			pos + Vector3.new(gap,0,0),
			pos + Vector3.new(-gap,0,-gap),
			pos + Vector3.new(gap,0,gap),
			pos
		}
		for _,v in pairs(positions) do
			if visual == true then
				local p = createPart()
				p.Position = v
			end
		end
		return positions
	end
	local open_points = {}
	local nearest_points = {}
	local closed_points = {}
	local results = {}
	local finalPos = nil
	local origin = script.Parent.Position
	function Pathfind(pos1,pos2)
		table.insert(closed_points,pos1)
		local nearest = nil
		local positions = createCube(pos1)
		local m1,m2 = math.huge,math.huge
		for i,v in pairs(open_points) do
			if not table.find(closed_points,v) then
				local H = (pos2 - v).Magnitude
				local G = (pos1 - v).Magnitude
				local F = H + G
				if F < m1 then
				--[[if not nearest_points[tostring(v)] then
					nearest_points[tostring(v)] = {["Pos"] = v,["H"] = H,["G"] = G,["Dir"] = pos1}
				else
					nearest_points[tostring(v)] = {["Pos"] = v,["H"] = H,["G"] = G,["Dir"] = pos1}
				end]]

					--print("Current Nearest is "..tostring(v).." F = "..F.." H = "..H.." G = "..G)
					m1 = F
					m2 = H
					nearest = v
				elseif F == m1 and H < m2 then
				--[[if not nearest_points[tostring(v)] then
					nearest_points[tostring(v)] = {["Pos"] = v,["H"] = H,["G"] = G,["Dir"] = pos1}
				else
					nearest_points[tostring(v)] = {["Pos"] = v,["H"] = H,["G"] = G,["Dir"] = pos1}
				end]]


					--print("Current Nearest is "..tostring(v).." F = "..F.." H = "..H.." G = "..G)
					m1 = F
					m2 = H
					nearest = v
				end
			end
		end
		--print("Number of Open = "..#open_points.." Number of Closed = "..#closed_points)
		for _,v in pairs(positions) do
			local proceed = true
			local direction = CFrame.lookAt(pos1,v).LookVector
			local posA = CFrame.lookAt(pos1,v)-- * CFrame.new(0,0,-gap/2)


			local ray = Ray.new(posA.p + Vector3.new(0,height,0),direction * gap * 5)
			local h,p = workspace:FindPartOnRay(ray,script.Parent)
			local dist = ((posA.p + Vector3.new(0,height,0)) - p).Magnitude
			if visual == true then
				local p2 = Instance.new("Part",script.Parent)
				p2.Name = "Ray"
				p2.Anchored = true
				p2.CanCollide = false
				p2.Size = Vector3.new(1,1,1)
				p2.Position = p
				p2.BrickColor = BrickColor.Green()
			end
			
			--p2.CFrame = CFrame.new(posA.p + Vector3.new(0,height,0),direction * gap * 100)
			--p2.Size = Vector3.new(dist/2,1,1)
			--game.Debris:AddItem(p2,0.1)
			if h then
				--print("Hitted!")
				proceed = false
				table.insert(closed_points,v)
			end
			if not h then
				local r = Ray.new(pos1 + Vector3.new(0,150,0),Vector3.new(0,-145,0))
				local h,p = workspace:FindPartOnRay(r,script.Parent)
				if h then
					--print("Hitted!")
					proceed = false
				end
			end
			if not table.find(closed_points,v) then
				if not table.find(open_points,v) then
					--print(tostring(v).." not in open")
					table.insert(open_points,v)
				else
					--print(tostring(v).." is in open")
					local num = table.find(open_points,v)
					table.remove(open_points,num)
					table.insert(closed_points,v)
				end
			end
			if table.find(closed_points,v) then
				--print(tostring(v).." is in closed")
				local num = table.find(open_points,v)
				if num then
					table.remove(open_points,num)
				end
				if visual == true then
					local p = createPart(0.12)
					p.Position = v
					p.BrickColor = BrickColor.Red()
				end
				proceed = false
			end
			if proceed == true then
				local H = (pos2 - v).Magnitude
				local G = (pos1 - v).Magnitude
				local F = H + G
				if not nearest_points[tostring(v)] then
					nearest_points[tostring(v)] = {["Pos"] = v,["H"] = H,["G"] = G,["Dir"] = pos1}
				else
					nearest_points[tostring(v)] = {["Pos"] = v,["H"] = H,["G"] = G,["Dir"] = pos1}
				end
				if F < m1 then
					--print("Current Nearest is "..tostring(v).." F = "..F.." H = "..H.." G = "..G)
					m1 = F
					m2 = H
					nearest = v
				elseif F == m1 and H < m2 then
					--print("Current Nearest is "..tostring(v).." F = "..F.." H = "..H.." G = "..G)
					m1 = F
					m2 = H
					nearest = v
				end
			end
		end
		if (pos1 - pos2).Magnitude <= gap then
			print("Found finalpos!")
			finalPos = nearest_points[tostring(pos1)]
			return
		end
		if nearest then
			if visual == true then
				wait()
			end
			Pathfind(nearest,pos2)
		end
	end

	function findPath()
		--print("FINDING PATH...")
		if (finalPos.Pos - origin).Magnitude <= 0 then
			--print("Path found!")
			return
		end
		local m = math.huge
		local nearest
		for _,v in pairs(nearest_points) do
			if v.Pos == finalPos.Dir then
				nearest = v
			end
		end
		if nearest then
			--print("Nearest not nil!")
			table.insert(results,nearest.Pos)
			if visual == true then
				local p = createPart(0.13)
				p.Position = nearest.Pos
				p.BrickColor = BrickColor.Blue()
				p.Name = "Path"
			end
			finalPos = nearest
			findPath()
		else
			--print("Nearest is nil!")
		end
	end

	Pathfind(start,endd)
	if visual == true then
		for _,v in pairs(nearest_points) do
			local part = createPart(1)
			part.Transparency = 1
			part.Position = v.Pos
			local direction = CFrame.lookAt(v.Pos,v.Dir) * CFrame.Angles(0,math.rad(-90),0)
			part.CFrame = direction
			game.ReplicatedStorage.arrow:Clone().Parent = part
		end
	end
	findPath()
	return results
end
local cachedPoints = {}
local function getCachedPoints(sP,eP)
	for _,v in pairs(cachedPoints) do
		if (v.StartPos - sP).Magnitude <= 30 and (v.EndPos - eP).Magnitude <= 30 then
			return v.Points
		end
	end
end
local parts = {}
while wait() do
	local sP = workspace.Start.Position
	local eP = workspace.End.Position
	local cache = getCachedPoints(sP,eP)
	local points
	if cache then
		points = cache
	else
		points = CreatePath(sP,eP,3,10,false)
		table.insert(cachedPoints,{["StartPos"] = sP,["EndPos"] = eP,["Points"] = points})
	end
	for i,v in pairs(parts) do
		v:Destroy()
	end
	table.clear(parts)
	for _,v in pairs(points) do
		local p = Instance.new("Part",workspace)
		p.Name = "Path"
		p.Anchored = true
		p.Size = Vector3.new(1,1,1)
		p.BrickColor = BrickColor.Blue()
		p.Position = v
		table.insert(parts,p)
	end
end

Roblox PathfindingService got 15 ~ 16% activity if i visualize the part.
it also acts the same as A*, if the map is complex or the range is long it will take more activity.

Roblox PathfindService Script

local PS = game:GetService("PathfindingService")
local path = PS:CreatePath()
local cachedPoints = {}
local parts = {}
local function getCachedPoints(sP,eP)
	for _,v in pairs(cachedPoints) do
		if (v.StartPos - sP).Magnitude <= 30 and (v.EndPos - eP).Magnitude <= 30 then
			return v.Points
		end
	end
end
while wait() do
	local sP = workspace.Start.Position
	local eP = workspace.End.Position
	local cache = getCachedPoints(sP,eP)
	local points
	if cache then
		points = cache
	else
		path:ComputeAsync(sP,eP)
		points = path:GetWaypoints()
		table.insert(cachedPoints,{["StartPos"] = sP,["EndPos"] = eP,["Points"] = points})
	end
	for i,v in pairs(parts) do
		v:Destroy()
	end
	table.clear(parts)
	for _,v in pairs(points) do
		local p = Instance.new("Part",workspace)
		p.Name = "Path"
		p.Anchored = true
		p.Size = Vector3.new(1,1,1)
		p.BrickColor = BrickColor.Blue()
		p.Position = v.Position
		table.insert(parts,p)
	end
end

Game Link : A star Pathfinding - Roblox
the place is uncopylocked so you can check it out yourself! theres 2 script there one is A* pathfind one is roblox Pathfind.
the A* pathfind isn’t perfect yet tho. it can pathfind but it still needs a little bit more checking.
right now the A* won’t detect holes under it and it wont work in slopes. but it work perfectly in places with flat grounds.

VortexColor · February 11, 2021, 3:15pm

You should sometimes raycast to the destination and if it can hit the destination do not pathfind but instead walk to the target.

eyrtuiop232 · February 12, 2021, 7:33am

i tried this method, it increases the activity and lag.

EXM_0 · February 12, 2021, 9:56am

If I understand you correctly, your trying to make a NPC AI:

Roblox pathfinding isn’t really good for NPC AI. Especially when your doing a zombie AI. It’s simply not good, since pathfinding will never reach the player. You have to increase the zombie’s speed. Which isn’t ideal. Many people implement custom pathfinding (A* algorithm).

eyrtuiop232 · February 12, 2021, 2:55pm

How do i make the nodes for it tho? since the map would be dynamic the nodes will also need to update, but creating the nodes using script really costs lots of performance.

StraightScared · February 12, 2021, 3:56pm

Here’s the Pathfinding Ai I had, I just tested and placed 60 humanoids with no lag, so

function module.WalkTo(Enemy)
	local Loop = true
	local Playing = false
	
	while Loop == true do
		
		local goalPosition = Vector3.new(Enemy.HumanoidRootPart.Position.X, Enemy.HumanoidRootPart.Position.Y, Enemy.HumanoidRootPart.Position.Z)

		local path = game:GetService("PathfindingService"):CreatePath()
		path:ComputeAsync(Character.HumanoidRootPart.Position, goalPosition)
		local waypoints = path:GetWaypoints()	
		local AnimationObject = script.Walk
		local AnimationLoaded = Humanoid:LoadAnimation(AnimationObject)
		if path.Status == Enum.PathStatus.Success then
			for _, waypoint in pairs(waypoints) do
				
				Humanoid:MoveTo(waypoint.Position) 
				if Playing == false then
					AnimationLoaded:Play()
				end
				Playing = true
				if Enemy.Humanoid.Health == 0 then
					local Found =  Character.Found
					Found.Value = false
					module.Find()
					break
				end
				if (Character.HumanoidRootPart.Position - Enemy.HumanoidRootPart.Position).Magnitude < 4 then
					Character.HumanoidRootPart.Orientation = Enemy.HumanoidRootPart.Orientation + Vector3.new(0, 180, 0)
					Loop = false
					AnimationLoaded:Stop()
					module.Attack(Enemy)
				end
				if Loop == false then
					break
				end
			end

		else
			print("Path unsuccessful")
			wait(2)
		end
		RunService.Heartbeat:Wait()
	end
end

EXM_0 · February 12, 2021, 3:56pm

I think creating nodes with scripts isn’t really a reliable way. Doing it manually would be better. I guess that’s one con when doing a custom algorithm. But that’s a sacrifice for a better AI algorithm.

VortexColor · February 12, 2021, 4:19pm

You can cache the results so it only casts each second.

eyrtuiop232 · February 12, 2021, 4:28pm

Alright, i tested it and got 4% - 10% performance with 50 npc.
it spikes when 50 of them are calculating the path.
and need to add MoveToFinished:Wait() on the for loop or else it wont pathfind.
Capture
but this is the best one so far so i will mark this one as solution for now.
im gonna try A*(with ray) and see if it increases performance.

eyrtuiop232 · February 12, 2021, 4:32pm

yea, i’ve cache the results so it doesnt fire every time.
and i fire 2 rays 1st from the endpoint of the path to the target.
and the 2nd from the humanoid to the target.

VortexColor · February 12, 2021, 4:43pm

You should only fire a ray to the humanoid target.

VortexColor · February 12, 2021, 4:44pm

And always use minimum lenght possible. Also if you recursively raycast use the hit position.

eyrtuiop232 · February 12, 2021, 4:52pm

i use minimum lengths as possible. which is the distance between posA and posB.
i already try the 1 ray method. which only fire a ray to the humanoid target, it got up to 10% meanwhile the one with no ray but only pathfinding service got 8%

i also try to fire 50 rays but with a very short length only about 3 studs. it costs 6% performance.