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 goalIf you plan to use this for your games, I have nothing against it,
however it would be nice if my name was mentioned 
