My nodegraph based A-Star pathfinder [Open Source]

EDIT:
had some bugs in the code but I think I fixed all of them

So I decided to release my pathfinder to the public. It uses manually placed nodes to generate a nodegraph, and it then uses the A-Star algorithm to find the shortest path.

You might ask, why would I use this when there is pathfindingservice!

Well, I created this way before pathfindingservice existed, and a fun fact, this pathfinder relies on a precompiled nodegraph, so it is MUCH MUCH MUCH faster.
I had problems with 20 npcs and pathfindingservice, but with this pathfinder I have no performance issues with large numbers of npcs.

I included code for:

  • A plugin that places these nodes
  • A plugin that generates a nodegraph from these nodes
  • The actual pathfinder and a usage example

Here’s an example how the nodes should be placed, doesn’t really matter how as long as they can be compiled by the nodegraph generator(it will connect all visible nodes to eachother)

Heres how the nodegraph should look like after compiling on larger maps if done right

local Plugin = PluginManager():CreatePlugin()
local Toolbar = Plugin:CreateToolbar("nSource Tools")
local Button = Toolbar:CreateButton("","Place Nodes","icon4.png")
local Event = {}
local glib = assert(LoadLibrary("RbxGui"))
local selectedtype = "node_walk"
local history = {}
local holderGui
local brightSlider, brightSliderValue

local nodeDir = workspace:findFirstChild("Nodes")

if not nodeDir then
	nodeDir = Instance.new("Model", workspace)
	nodeDir.Name = "Nodes"
end


local function Disconnect(...)
	for _,name in pairs{...} do
		if Event[name] then
			Event[name]:disconnect()
			Event[name] = nil
		end
	end
end


local function Activate()
	print("nSource node placer loaded \n Press Z to undo \n Press X to undo all")
	Button:SetActive(true)
	
	local function onItemSelected(item)
		selectedtype = item
		print("'" .. item .. "' was selected!")
	end
 
	local listOfItems={"node_walk","node_jump"} -- our list of items
	local dropDownList, updateSelection=glib.CreateDropDownMenu(listOfItems, onItemSelected)
	dropDownList.Size = UDim2.new(1, 0, 1, 0) -- this is to make the drop down list fit in our GUI correctly
	
	
	holderGui = Instance.new("ScreenGui",game:GetService("CoreGui")) -- make the screen gui that holds everything
	
	local holderFrame = Instance.new("Frame") -- make a frame to hold the drop down list
	holderFrame.Size = UDim2.new(0, 200, 0, 26) -- make it the size you want
	holderFrame.Position = UDim2.new(0.1, 0, 0.1, 0)
	holderFrame.BackgroundTransparency = 1 -- make it transparent for the drop down list
	holderFrame.Parent = holderGui
	dropDownList.Parent = holderFrame
 
	local Mouse = Plugin:GetMouse()
	Event.MDown = Mouse.Button1Down:connect(function()
		local pos = Mouse.Hit.p
		local p = Instance.new("Part",nodeDir)
		p.Transparency = 0
		p.CanCollide = false
		p.Anchored = true
		p.BrickColor = BrickColor.new("Lime green")
		p.Locked = true
		p.formFactor = "Custom"
		p.Size = Vector3.new(2,1,2)
		p.Name = selectedtype
		p.Position = pos + Vector3.new(0, p.Size.y / 2, 0)
		table.insert(history, p)

		
	end)
	Event.Down = Mouse.KeyDown:connect(function(key)
		key = key:lower()
		if key == "z" then
			table.remove(history, #history)
		elseif key == "x" then
			for i = 1, #history do
				table.remove(history, i)
			end
		end
	end)
end

local function Deactivate()
	print("nSource node placer unloaded")
	Button:SetActive(false)
	if holderGui ~= nil then
		holderGui:Destroy()
	end
	down = false
	Disconnect("Down","MDown")
end

local active = false
Button.Click:connect(function()
	active = not active
	if active then
		Plugin:Activate(true)
		Activate()
	else
		Deactivate()
	end
end)

print("/nSource/nodePlace.lua loaded")

Plugin.Deactivation:connect(Deactivate)
local NODEGRAPH_COMPILER_IGNORE_LIST = {}
local Plugin = PluginManager():CreatePlugin()
local Toolbar = Plugin:CreateToolbar("nSource Tools")
local Button = Toolbar:CreateButton("","Recalc Nodegraph","icon3.png")
local Event = {}
local glib = assert(LoadLibrary("RbxGui"))
local history = {}
local nodeselected
local selectedtype
local showConnections = true


local ignore = workspace:findFirstChild("Ignore")

if not ignore then
	ignore = Instance.new("Model", workspace)
	ignore.Name = "Ignore"
end

local function Disconnect(...)
	for _,name in pairs{...} do
		if Event[name] then
			Event[name]:disconnect()
			Event[name] = nil
		end
	end
end

local nodes = workspace:findFirstChild("Nodes", true)

function disconnectAll()
	for _, c in pairs(nodes:children()) do
		if c.Name == "connection" then
			c:Destroy()
		end
	end
end

function drawLine(pos1, pos2)
	local dist = (pos1-pos2).magnitude
	local rayPart = Instance.new("Part", ignore)
	rayPart.Name = "NodeConnector"
	rayPart.BrickColor = BrickColor.new("Lime green")
	rayPart.Transparency = 0.5
	rayPart.Anchored = true
	rayPart.CanCollide = false
	rayPart.TopSurface = Enum.SurfaceType.Smooth
	rayPart.BottomSurface = Enum.SurfaceType.Smooth
	rayPart.formFactor = Enum.FormFactor.Custom
	rayPart.Size = Vector3.new(0.2, 0.2, dist)
	rayPart.CFrame = CFrame.new(pos1, pos2) * CFrame.new(0, 0, -dist/2)
end

function connect(a, b)
	local conVal = Instance.new("ObjectValue", a)
	local conVal2 = Instance.new("ObjectValue", b)
	conVal.Name = "connection"
	conVal2.Name = "connection"
	conVal.Value = b
	conVal2.Value = a
	if selectedtype == "draw connections" then
		drawLine(a.Position, b.Position)
	end
end


function isConnected(a, b)
	local pos1 = a.Position
	local pos2 = b.Position
	local ray = Ray.new(pos1,(pos2-pos1).unit * 999)
	local hit,pos = workspace:FindPartOnRayWithIgnoreList(ray, NODEGRAPH_COMPILER_IGNORE_LIST)
	if hit == b then
		return true
	end
	return false
end

function connectNodes(nodes)
	for _, n1 in pairs(nodes:children()) do
		for _, n2 in pairs(nodes:children()) do
			if isConnected(n1, n2) then
				connect(n1, n2)
			end
		end
	end
end


local function Activate()
	Button:SetActive(true)
	disconnectAll()
	
	local function onItemSelected(item)
		selectedtype = item
		connectNodes(nodes)
	end
 
	local listOfItems={"draw connections","dont draw connections"} -- our list of items
	local dropDownList, updateSelection=glib.CreateDropDownMenu(listOfItems, onItemSelected)
	dropDownList.Size = UDim2.new(1, 0, 1, 0) -- this is to make the drop down list fit in our GUI correctly
	
	
	holderGui = Instance.new("ScreenGui",game:GetService("CoreGui")) -- make the screen gui that holds everything
	
	local holderFrame = Instance.new("Frame") -- make a frame to hold the drop down list
	holderFrame.Size = UDim2.new(0, 200, 0, 26) -- make it the size you want
	holderFrame.Position = UDim2.new(0.1, 0, 0.1, 0)
	holderFrame.BackgroundTransparency = 1 -- make it transparent for the drop down list
	holderFrame.Parent = holderGui
	dropDownList.Parent = holderFrame
end

local function Deactivate()
	Button:SetActive(false)
	down = false
	if holderGui ~= nil then
		holderGui:Destroy()
	end
end

local active = false
Button.Click:connect(function()
	active = not active
	if active then
		Plugin:Activate(true)
		Activate()
	else
		Deactivate()
	end
end)

print("/nSource/autoNodeConnect.lua loaded")

Plugin.Deactivation:connect(Deactivate)
local thenodes
local master_node_table, mnt_index
local ai_max_range = math.huge

thenodes = workspace:findFirstChild("nodeDir", true)


function searchByBrick(brick)
    for i, j in pairs(master_node_table) do
        if j.Brick == brick then
            return j.ID
        end
    end
    return nil
end
 
function searchById(id)
    for i, j in pairs(master_node_table) do
        if j.ID == id then
            return j.Brick
        end
    end
    return nil
end



function nodeObjectFromBrick(brick)
	if brick.ClassName ~= "Part" then
		return nil
	end
	local node_index = mnt_index
	master_node_table[node_index] = {
		ID = mnt_index,
		Brick = brick,
		Connections = {}
	}
	for i, child in pairs(brick:GetChildren()) do
		if child.ClassName == "ObjectValue" and child.Name == "connection" then
			local brick2 = child.Value
			local ID = searchByBrick(brick2)
			if ID == nil then
				mnt_index = mnt_index + 1
				ID = nodeObjectFromBrick(brick2)
			end
			local con = {
				ID = ID,
				G = (master_node_table[ID].Brick.Position - brick.Position).magnitude
			}
			table.insert(master_node_table[node_index].Connections, con)
		end
	end
	
	return node_index
end


function collectNodes(model)
	master_node_table = {}
	mnt_index = 1
	for i, child in pairs(model:GetChildren()) do
		if child.ClassName == "Part" and searchByBrick(child) == nil then
			nodeObjectFromBrick(child)
			mnt_index = mnt_index + 1
		end
	end
end


function heuristic(id1, id2)
	local p1 = master_node_table[id1].Brick.Position
	local p2 = master_node_table[id2].Brick.Position
	return (p1 - p2).magnitude
end


function len(t)
	local l = 0
	for i, j in pairs(t) do
		if j ~= nil then
			l = l + 1
		end
	end
	return l
end


function getPath(t, n)
	if t[n] == nil then
		return {n}
	else
		local t2 = getPath(t, t[n])
		table.insert(t2, n)
		return t2
	end
end


function AStar(startID, endID)
	--local now = tick()
	local closed = {}
	local open = {startID}
	local previous = {}
	local g_score = {}
	local f_score = {}
	
	g_score[startID] = 0
	f_score[startID] = heuristic(startID, endID)
	
	while len(open) > 0 do
		local current, current_i = nil, nil
		for i, j in pairs(open) do
			if current == nil then
				current = j
				current_i = i
			else
				if j ~= nil then
					if f_score[j] < f_score[current] then
						current = j
						current_i = i
					end
				end
			end
		end
		
		if current == endID then
			local path = getPath(previous, endID)
			local ret = {}
			for i, j in pairs(path) do
				table.insert(ret, master_node_table[j].Brick)
			end
			--print("Time taken for AStar to run: "..tostring(tick() - now))
			return ret
		end
		
		open[current_i] = nil
		table.insert(closed, current)
		
		for i, j in pairs(master_node_table[current].Connections) do
			local in_closed = false
			for k, l in pairs(closed) do
				if l == j.ID then
					in_closed = true
					break
				end
			end
			if in_closed == false then
				local tentative_score = g_score[current] + j.G
				local in_open = false
				for k, l in pairs(open) do
					if l == j.ID then
						in_open = true
						break
					end
				end
				if in_open == false or tentative_score < g_score[j.ID] then
					previous[j.ID] = current
					g_score[j.ID] = tentative_score
					f_score[j.ID] = g_score[j.ID] + heuristic(j.ID, endID)
					if in_open == false then
						table.insert(open, j.ID)
					end
				end
			end
		end
	end
	--print("Time taken for AStar to run: "..tostring(tick() - now))
	return nil
end



function getNearestNode(position,returnBrick,dir)
	local nodeDir = dir
	local smallest = ai_max_range
	local nodes = {}
	if type(dir) ~= "table" then
		nodeDir = dir:children()
	end
	for k,v in pairs(nodeDir) do
		if v:IsA("BasePart") then
			local dist
			dist = (position.Position - v.Position).magnitude
			nodes[searchByBrick(v)] = dist
			if dist <= smallest then
				smallest = dist
			end
		end
	end
	for k,v in pairs(nodes) do
		print(k)
		if v <= smallest then
			if returnBrick then
				return searchById(k)
			else
				return k
			end
		end
	end
end



collectNodes(thenodes)  --generate nodegraph
local start = getNearestNode(workspace.Start, true, thenodes)
local goal = getNearestNode(workspace.Goal, true, thenodes)

local path = AStar(searchByBrick(start), searchByBrick(goal)) --returns table of parts(nodes), in order from start to goal

If you plan to use this for your games, I have nothing against it,
however it would be nice if my name was mentioned :slight_smile:

9 Likes

Anyone? :confused:

I haven’t had the time to really play around with it yet, but from what you’ve shown it looks really nice. Me and a few others tried something similar a while back and had some interesting results, it’ll be interesting to compare yours to what we had.

Another RbxDev post to add to my list of “Looks like it’s really useful, I might need it later” bookmarks. :stuck_out_tongue:

You should definitely not be auto placing your nodes. In the screenshot you posted half of those nodes are redundant and the other half should be adjusted to optimize the number of steps. Even if you have the fastest algorithm in the world if you’re doing a bunch of redundant calculations then you won’t get the benefits.

The nodes arent auto placed. Theyre manually placed.

They are just automatically connected

I could have a flood fill algorithm go through all the playable space and auto place nodes but I don’t think its worth doing, and besides, most games today still use manually placed AI nodes.

I did this once. Don’t try doing this. It’s a bad idea. Trust.

Oya I also did some experimenting. You can prebake the pathfinding calculations (calculate every possible path before hand so you can just do a table look up when you need a path). Only problem is trying to fit this somewhere. https://dl.dropboxusercontent.com/u/46495247/pathdump.txt

[quote] I did this once. Don’t try doing this. It’s a bad idea. Trust.

Oya I also did some experimenting. You can prebake the pathfinding calculations (calculate every possible path before hand so you can just do a table look up when you need a path). Only problem is trying to fit this somewhere. https://dl.dropboxusercontent.com/u/46495247/pathdump.txt [/quote]

Yeah I was planning to do that aswell :slight_smile:
Procrastination is just too good.

i just stumbled upon this in 2022, and the plugin part of it still works (with a few edits since :CreatePlugin() is deprecated)

i’m absolutely putting your name EVERYWHERE on my game, this is one hell of an ancient gem that deserves recognition and it works great

1 Like

a bit of jank pausing since i raised the wait time for the loop, but here’s your script in action: it first walks to the gray brick (the primary goal) but once i hit the NPC, it’ll change goal to the hospital location

oh yeah and that random janky running it did when i first hit them is because i made a script from the old version of this game that them makes them run in a random spot, might remove that

I have newer versions of the plugin that I’ve forgotten to post here

Can’t remember which one is newer since the last updated timestamp doesn’t seem to work on the page

4 Likes

https://www.roblox.com/library/207049192/A-Pathfinding-System-v2-11 this one is 5 years younger than the other also THANKS THIS RULES