A* Pathfinding system!

Help and Feedback Code Review
, , ,
1

Optimization

I’ve found that the normal roblox pathfinding is just not working the way I expect it to, so i’ve just decided to make my own, Its working as intended but the grid generation just takes too long on larger scale maps (especially with visuals on) and the pathfinding is also kinda slow at times

I’ve added some checks to the grid generation that give the server a little bit of time to rest, and it might just be that i need to fine tune the values a little bit more, but i cant help but think there might be a faster way to do it

  • Note there is some residual code left from different things i tried, so its still a little bit rough
local MonsterFunctions = {}

type Node = {
	Position: Vector3,
	GridCoordinates: Vector2,
	ConnectedNodes: {},
	Index: number,
	Active: boolean,
	Visual: Model,
	f: number,
	g: number,
	h: number,
	PTFPos: number,
	Parent: Node
}

function MonsterFunctions.GridCreation(AgentRadius: number, PassesBeforeWaitingMAX: number, GRID_DENSITY: number, GRID_SIZE_Y: number, GRID_SIZE_X: number, NavMesh:Model)

	local RunService = game:GetService("RunService")

	local PassesBeforeWaiting = PassesBeforeWaitingMAX
	local NodeBase = game.ReplicatedStorage.TestingAssets.Node

	local GRID_MAX_X = math.round(GRID_SIZE_X / GRID_DENSITY)
	local GRID_MAX_Y = math.round(GRID_SIZE_Y / GRID_DENSITY)

	local NodeList = {}

	local NodeContructor = function(Pos: Vector3, coords: Vector2, Index: number)
		local NewNode: Node = {}
		NewNode.GridCoordinates = coords
		NewNode.Position = Pos
		NewNode.Active = nil
		NewNode.Index = Index
		NewNode.f = nil
		NewNode.g = nil
		NewNode.h = nil
		NewNode.ConnectedNodes = {NewNode.Index + 1, 
			NewNode.Index - 1, 
			NewNode.Index - GRID_MAX_Y,
			NewNode.Index - GRID_MAX_Y + 1,
			NewNode.Index - GRID_MAX_Y - 1,

			NewNode.Index + GRID_MAX_Y,
			NewNode.Index + GRID_MAX_Y + 1,
			NewNode.Index + GRID_MAX_Y - 1}

		print(NewNode.ConnectedNodes, NewNode.Index)

		return NewNode
	end

	local CreateGrid = function()
		local Center = NavMesh.PrimaryPart.Position
		local PassesLeft = GRID_MAX_Y
		local Xcoord = 0
		local Ycoord = 0
		for Passes = 1, GRID_MAX_X * GRID_MAX_Y do
			if PassesLeft == 0 then
				PassesLeft = math.round((GRID_SIZE_Y/GRID_DENSITY))
				Xcoord = Xcoord + 1
				Ycoord = 0
			end
			local NodePos = Center - Vector3.new(GRID_SIZE_X/2 - (GRID_DENSITY * Xcoord), 0, GRID_SIZE_Y/2 - (GRID_DENSITY * Ycoord))
			local coords = Vector2.new(Xcoord, Ycoord)
			local Node = NodeContructor(NodePos, coords, Passes)
			Ycoord = Ycoord + 1
			PassesLeft = PassesLeft - 1
			PassesBeforeWaiting = PassesBeforeWaiting - 1
			if PassesBeforeWaiting == 0 then
				PassesBeforeWaiting = PassesBeforeWaitingMAX
				RunService.Heartbeat:Wait()
			end
			local NodeVisual = NodeBase:Clone()
			NodeVisual.Parent = game.Workspace
			NodeVisual:MoveTo(Node.Position)
			Node.Visual = NodeVisual
			Node.Visual.Parent = game.Workspace.Nodes
			Node.Visual:SetAttribute("GridCoordinates", Node.GridCoordinates)
			table.insert(NodeList, Node)
			NodeVisual:AddTag(table.find(NodeList, Node))
		end
	end

	CreateGrid()

	print("Begin The Purge")
	print(#NodeList.." Nodes Created")

	for i, Node: Node in NodeList do
		local OvParams = OverlapParams.new()
		OvParams.FilterType = Enum.RaycastFilterType.Include
		OvParams.FilterDescendantsInstances = NavMesh:GetChildren()
		if table.find(game.Workspace:GetPartsInPart(Node.Visual:FindFirstChild("Collision"), OvParams), NavMesh.PrimaryPart) then
			print("found", Node.GridCoordinates, i)
			Node.Active = true
		else
			Node.Visual.PrimaryPart.Color = Color3.new(0.388235, 0.368627, 1)
			Node.Active = false
			print("not found", Node.GridCoordinates, i)
		end
		PassesBeforeWaiting = PassesBeforeWaiting - 1
		if PassesBeforeWaiting == 0 then
			PassesBeforeWaiting = PassesBeforeWaitingMAX
			RunService.Heartbeat:Wait()
		end
	end

	return NodeList
end

function MonsterFunctions.CreatePath(Posi: Vector2, ObjPos: Vector2, List: {}, Density: number)
	local CheckedNode: Node = nil
	local StartingNode: Node = nil
	local GoalNode: Node = nil
	local Dist = nil
	local PathMaker

	local FindClosestNode = function(Pos: Vector2, Goal: boolean)
		for i, v:Node in List do
			if v.Active then
				if CheckedNode then
					if (Vector2.new(v.Position.X, v.Position.Z) - Pos).Magnitude < Dist then
						CheckedNode = v
						Dist = (Vector2.new(CheckedNode.Position.X, CheckedNode.Position.Z) - Pos).Magnitude
						if Dist < Density - 0.5 then
							print("FOUND CLOSEST NODE")
							if Goal then
								GoalNode = CheckedNode
								print("ADDED GOAL")
								GoalNode.Visual.PrimaryPart.Color = Color3.new(0.988235, 1, 0.243137)
							else
								StartingNode = CheckedNode
								StartingNode.Visual.PrimaryPart.Color = Color3.new(0.192157, 1, 0.247059)
								StartingNode.f = 0
								StartingNode.g = 0
								StartingNode.PTFPos = 1
							end
							CheckedNode = nil
							break
						end
					end
				else
					CheckedNode = v
					Dist = (Vector2.new(CheckedNode.Position.X, CheckedNode.Position.Z) - Pos).Magnitude
					if Dist < 1 then
						print("FOUND CLOSEST NODE")
						if Goal then
							print("ADDED GOAL")
							GoalNode = CheckedNode
							GoalNode.Visual.PrimaryPart.Color = Color3.new(0.988235, 1, 0.243137)
						else
							StartingNode = CheckedNode
							StartingNode.Visual.PrimaryPart.Color = Color3.new(0.192157, 1, 0.247059)
							StartingNode.f = 0
							StartingNode.g = 0
							StartingNode.PTFPos = 1
						end
						CheckedNode = nil
						break
					end
				end
			end
		end
		StartingNode.Visual.PrimaryPart.Color = Color3.new(0.192157, 1, 0.247059)
	end

	task.spawn(FindClosestNode, Posi, false)
	task.spawn(FindClosestNode, ObjPos, true)

	local OpenList = {}
	local ClosedList = {}

	table.insert(OpenList, StartingNode)

	PathMaker = function()
		local FoundPath = {}
		while task.wait() do
			print("Running")
			local stop = false
			local Q: Node = nil
			table.sort(OpenList, function(a:Node, b:Node)
				return a.f < b.f
			end)
			Q = OpenList[1]

			table.remove(OpenList, table.find(OpenList, Q))
			local succesors = {}

			for i = 1, 8 do
				local Succesor: Node = List[Q.ConnectedNodes[i]]
				if Succesor.Active then
					--print(Q.ConnectedNodes[i])
					table.insert(succesors, Succesor)
				end
			end

			for i, C: Node in ipairs(succesors) do
				if C == GoalNode then
					C.Parent = Q
					stop = true
					break
				else
					local dx = math.abs(C.GridCoordinates.X - GoalNode.GridCoordinates.X)
					local dy = math.abs(C.GridCoordinates.Y - GoalNode.GridCoordinates.Y)

					local NewG = Q.g + 1
					local NewH = 1 * (dx + dy) + (1.414 - 2 * 1) * math.min(dx, dy)

					local NewF = NewG + NewH

					local OpenIndex = table.find(OpenList, C)

					if OpenIndex then
						if OpenList[OpenIndex].f <= NewF then
							continue
						end
					end

					local ClosedIndex = table.find(ClosedList, C)

					if ClosedIndex then
						if ClosedList[ClosedIndex].f <= NewF then
							continue
						end
					end

					C.g = NewG
					C.h = NewH
					C.f = NewF
					C.Parent = Q
					table.insert(OpenList, C)
				end
			end

			Q.Visual.PrimaryPart.Color = Color3.new(0.984314, 0.537255, 1)
			table.insert(ClosedList, Q)

			if stop then 
				local P = GoalNode
				while task.wait() do
					print(P.Index)
					table.insert(FoundPath, P)
					P.Visual.PrimaryPart.Color = Color3.new(1, 0, 0.0156863)
					if P.Parent then
						P = P.Parent
					else
						break
					end
				end
				break 
			end

		end
	end

	PathMaker()

end

return MonsterFunctions
2 Likes
2

few issues i could find.. that makes yours slow.

while task.wait() do

this waits roughly per frame,

table.sort(OpenList, function(a:Node, b:Node)
				return a.f < b.f
			end)

instead of using table.sort() which is slow on big datas, u could make a heap keyed table.

also consider O(1) here!

local OpenIndex = table.find(OpenList, C)
3 Likes
3

note that it is possible to beat roblox pathfinding by the way. i’ve tried this. roughly 6-10x speed up from roblox , involving custom navmesh and custom pathfinding too

1 Like
4

Seems you are implementing an unoptimized version of A*.

  1. You are using table.find to determine whether a node is “Open” or “Closed” which iterates through the entire list. A better alternative is to store nodes using a dictionary and retrieve the nodes using fast access with a key.
  2. You are using table.sort to find the Node with the lowest score everytime you are evaluating a new node. Sorting is an expensive operation. For n nodes, the operations a computer would have to perform is proportional to n^2 * log n. Most A* implementations use an optimization to avoid sorting the same array multiple times, which is a min-heap. A min-heap is efficient at insertions and removals while still keeping the lowest score efficiently retrievable. Instead of n^2 log n operations for getting the lowest scored node, it is only log n with a min-heap, This is a pretty useful video explaining: https://www.youtube.com/watch?v=3Dw5d7PlcTM
1 Like
5

First of all, thank you so much for your help!

Secondly, could you elaborate a bit more on what a heap keyed table is? i tried to research about it and even though i did find what a keyed and a heap table are, i couldnt really figure out how i could implement it onto roblox or how it would be any faster than sorting the table

6

What I think they meant is a table implementation of a heap. Meaning that you are still using a table, but the way you store data and retrieve, add, and remove data from it is equivalent to a heap.

See this image:

image
image902×722 58.2 KB

The way to do this is by storing the value of the left child of a node in the index i * 2 + 1 and the right child of the same node in i * 2 + 2.

The left child of the node 4 (which is 10) should be stored in 1 * 2 + 1 = 3 and the right child (which is 8) should be stored in 1 * 2 + 2 = 4.

You can also calculate the index of the parent of a node with this formula: (i - 1) // 2.

Here is an implementation in Luau:

This text will be hidden

-- Add a value to the heap
local function heap_push(heap, value)
    table.insert(heap, value)
    
    -- Bubble up
    local index = #heap
    while index > 1 do
        local parent = math.floor(index / 2)
        if heap[index] >= heap[parent] then break end
        
        heap[index], heap[parent] = heap[parent], heap[index]
        index = parent
    end
end

-- Remove and return the minimum value
local function heap_pop(heap)
    local size = #heap
    if size == 0 then return nil end
    
    local min = heap[1]
    heap[1] = heap[size]
    table.remove(heap, size)
    
    -- Bubble down
    local index = 1
    local new_size = size - 1
    while index * 2 <= new_size do
        local left = index * 2
        local right = left + 1
        local smallest = left
        
        if right <= new_size and heap[right] < heap[left] then
            smallest = right
        end
        
        if heap[index] <= heap[smallest] then break end
        
        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest
    end
    
    return min
end


local my_heap = {}

heap_push(my_heap, 15)
heap_push(my_heap, 5)
heap_push(my_heap, 20)
heap_push(my_heap, 1)

print(heap_pop(my_heap)) -- 1
print(heap_pop(my_heap)) -- 5
print(heap_pop(my_heap)) -- 15