# A* Pathfinding Module

So I’ve made an A* Pathfinding Module, which works with NPC’s (Which does work but not really sometimes if you know but I’ll give you the example), including Parts.

So for NPC’s you just need the part you want to start with in the NPC and the another Part to end it (or just a vector3). Here’s the module:
Pathfinding.rbxm (5.6 KB)

Main A* Pathfinding Code:

``````local pathfinding = {}

local SIZE = 3

local DIRECTIONS = {
Vector3.xAxis;
Vector3.zAxis;

Vector3.xAxis * -1;
Vector3.zAxis * -1;

Vector3.zAxis + Vector3.xAxis;

Vector3.xAxis * -1 + Vector3.zAxis;

Vector3.xAxis + Vector3.zAxis * -1;
}

for i, dir in DIRECTIONS do
DIRECTIONS[i] = dir * SIZE -- scale the directions with the grid size
end

local function RoundToNearest(v)
return Vector3.new(
math.round(v.X / SIZE) * SIZE,
math.round(v.Y / SIZE) * SIZE,
math.round(v.Z / SIZE) * SIZE
)
end

local Params = OverlapParams.new()
local filterdDescendantsInstances = {}

local function CheckForHumanoids()
for _, Object in ipairs(workspace:GetDescendants()) do
if Object:IsA("Model") then
if Object:FindFirstChildWhichIsA("Humanoid") then
Params.FilterType = Enum.RaycastFilterType.Exclude
end
end
end
end

local function NodeIsTraversable(point: Vector3)
local collisions = workspace:GetPartBoundsInBox(CFrame.new(point), Vector3.new(SIZE, 0, SIZE), Params)

if collisions[1] then
return false
end
return true
end

local D = math.sqrt(2) -- A constant

local function ConstructNode(worldPos: Vector3, target: Vector3)
local function HeuristicFunction(a: Vector3, b: Vector3): number
local D2 = 1

local dx = math.abs(a.X - b.X)
local dy = math.abs(a.Y - b.Y)
local dz = math.abs(a.Z - b.Z)

return D * math.min(dx, dy, dz) + (D2 - D) * math.max(0, dx + dy + dz - 2 * math.min(dx, dy, dz))
end

local Object = setmetatable({
Traversable = false;
Position = worldPos;

Costs = setmetatable({
G = 0;
H = 0;
}, {
__index = function(t, k)
if k == 'F' then
return rawget(t, 'H') + rawget(t, 'G') -- F is the sum of H and G
end

return rawget(t, k)
end,
});

HeapIndex = 0; -- For our new heap
Parent = nil; -- No more storing Parents table
}, {
__sub = function(a, b)
local compare = a.Costs.F - b.Costs.F -- Substract a's F and b's F

if compare == 0 then -- If the F costs are equal, compare the H cost instead
compare = a.Costs.H - b.Costs.H
end

return -compare -- Return the negated comparison
end,

__eq = function(a, b)
return a.Position == b.Position
end,
})

Object.Costs.G = (worldPos - target).Magnitude
Object.Costs.H = HeuristicFunction and HeuristicFunction(worldPos, target) or 0 -- Heuristic is 0 if no function is set

Object.Traversable = NodeIsTraversable(worldPos)

return Object
end

local function roundToStep(pos : Vector3)
return Vector3.new(math.floor(pos.X/3)*3+1.5,math.floor(pos.Y/3)*3+1.5, math.floor(pos.Z/3)*3+1.5)
end

local Heap = require(script:WaitForChild("Heap"))

local function FindPath(start: Vector3, target: Vector3)
start = RoundToNearest(start)
target = RoundToNearest(target)

local StartNode = ConstructNode(start, target)
local TargetNode = ConstructNode(target, target)

-- Safety precaution checks so we don't waste time computing the path
assert(StartNode.Traversable, 'Starting Node is intraversable, thus path is intraversable')
assert(TargetNode.Traversable, 'Target Node is intraversable, thus path is intraversable')

local Grid = {[start] = StartNode, [target] = TargetNode}

local OpenSet = Heap.new()-- :: Heap.Heap<typeof(ConstructNode(Vector3, Vector3))>
local ClosedSet = {}

while OpenSet:Count() > 0 do
local CurrentNode = OpenSet:RemoveFirst()
ClosedSet[CurrentNode.Position] = true

local function RetracePath()
local Path = {}
local CurrentPathNode = TargetNode

while CurrentPathNode ~= StartNode do
table.insert(Path, 1, CurrentPathNode)
CurrentPathNode = CurrentPathNode.Parent
end

return Path
end

if CurrentNode == TargetNode then
return RetracePath()
end

for _, direction in DIRECTIONS do
local NeighborPos = CurrentNode.Position + direction

-- If neighbor already evaluated/not traversable, skip
if ClosedSet[NeighborPos] or not NodeIsTraversable(NeighborPos) then
continue
end

-- Get neighbor node
local NeighborNode = Grid[NeighborPos] or ConstructNode(NeighborPos, target)
Grid[NeighborPos] = NeighborNode

-- Get new G cost to the neighbor
local CostToNeighbor = CurrentNode.Costs.G + (CurrentNode.Position - NeighborPos).Magnitude

-- If cost turns out to be better or not in openset
if CostToNeighbor < NeighborNode.Costs.G or not OpenSet:Contains(NeighborNode) then
NeighborNode.Costs.G = CostToNeighbor
NeighborNode.Costs.H = (NeighborPos - target).Magnitude

NeighborNode.Parent = CurrentNode

if not OpenSet:Contains(NeighborNode) then -- If it doesn't have the neighbor node yet, add the node
end
end
end
end
end

local debugFinished = false

local allParts = 0

function debugParts(self, path)
end

pathfinding.roundToStep = function(pos)
return roundToStep(pos)
end

pathfinding.Character = nil

pathfinding.new = function(startPos, goalPos)

local newAStar = {}
setmetatable(newAStar, {__index = pathfinding})

newAStar.Service = workspace

local debugPartsFolder

if pathfinding.Character then
if not pathfinding.Character:FindFirstChild("DebugParts") then
debugPartsFolder = Instance.new("Folder", pathfinding.Character)
debugPartsFolder.Name = "DebugParts"
else
debugPartsFolder = pathfinding.Character:FindFirstChild("DebugParts")
end
else
if not workspace:FindFirstChild("DebugParts") then
debugPartsFolder = Instance.new("Folder", workspace)
debugPartsFolder.Name = "DebugParts"
else
debugPartsFolder = workspace:FindFirstChild("DebugParts")
end
end

newAStar.debugPartsFold = debugPartsFolder

newAStar.startPos = startPos
newAStar.goalPos = goalPos

return newAStar
end

pathfinding.debugParts = function(self: AStar, path)

local DebugPartsFold = self.debugPartsFold

for i, child in pairs(DebugPartsFold:GetChildren()) do
if child.Name == tostring(i) then
child:Destroy()
end
end

debugFinished = false
for _, node in pairs(path) do
local nodePos = node.Position

local a = Instance.new("Part", DebugPartsFold)
a.Name = _
a.Position = Vector3.new(nodePos.X, 0, nodePos.Z)
a.Size = Vector3.new(1, 1, 1)
a.Anchored = true
a.CanCollide = false
a.CanTouch = false
a.CanQuery = false
end
debugFinished = true
end

pathfinding.FindPath = function(self: AStar, debug: boolean)
local startPos = self.startPos
local goalPos = self.goalPos

local path = FindPath(startPos, goalPos)

if debug then
self:debugParts(path)
end

return path
end

type AStar = typeof(pathfinding.new(..., ...))

return pathfinding
``````

Heap Module Code:

``````local Heap = {}

function Heap.new<T>() -- Just some typechecking stuff we'll be using later on
-- Our heap private virables
type Item = {HeapIndex: number} & T

local Items = {} :: {[number]: Item} -- The items in our heap tree (in this case, our nodes)
local CurrentItemCount = 0 -- The number of items currently in our tree

local function Swap(a: Item, b: Item)
Items[a.HeapIndex], Items[b.HeapIndex] = b, a
local itemAIndex = a.HeapIndex

a.HeapIndex = b.HeapIndex
b.HeapIndex = itemAIndex
end

local function SortUp(item: Item)
local parentIndex = (item.HeapIndex-1)/2

while true do
local parentItem = Items[parentIndex]

-- Check if the parent item exists and if the item is greater than the parent
if parentItem and item - parentItem > 0 then
-- If so, swap the item with the parent item
Swap(item, parentItem)
else
-- Otherwise, the item is in the correct position, so break out of the loop
break
end

parentIndex = (item.HeapIndex-1)/2
end
end

local function SortDown(item: Item)
while true do
local childLeftIndex = item.HeapIndex * 2 + 1
local childRightIndex = item.HeapIndex * 2 + 2
local swapIndex = 0

-- Check if the left child exists
if childLeftIndex < CurrentItemCount then
swapIndex = childLeftIndex

-- If the right child has a higher priority, set the swap index to the right child index
if childRightIndex < CurrentItemCount then
-- If so, compare the priorities of the left and right children
if Items[childLeftIndex] - Items[childRightIndex] < 0 then
-- If the right child has a higher priority, set the swap index to the right child index
swapIndex = childRightIndex
end
end

-- Compare the priority of the item with the priority of the child at the swap index
if item-Items[swapIndex] < 0 then
-- If the child has a higher priority, swap the item with the child
Swap(item, Items[swapIndex])
else
-- Otherwise, the item is in the correct position, so break out of the loop
return
end
else
-- If the left child does not exist, the item is at the bottom of the heap and in the correct position
return
end
end
end

local Object = {} -- The class' instantiated object

function Object:RemoveFirst() : Item
local firstItem = Items[0] -- Get the root node
CurrentItemCount -= 1 -- Decrease the items count
Items[0] = Items[CurrentItemCount] -- Set the root node to lowest item
Items[0].HeapIndex = 0

SortDown(Items[0]) -- Sort down since the lowest item is at the root node

return firstItem
end

item.HeapIndex = CurrentItemCount
Items[CurrentItemCount] = item

SortUp(item) -- Sort up since our heap item is at the bottom
CurrentItemCount += 1
end

function Object:Contains(item: T)
return Items[item.HeapIndex] == item
end

function Object:Count() -- Just a simple getter
return CurrentItemCount
end

return Object
end

return Heap
``````

Very Useful.

Where I got this: How 2 make A* Pathfinding

13 Likes

personally i cant wait for new pathfinding since roblox’s pathfinding is actual hellspawn…
but this uhh

this…

this needs work.

3 Likes

I mean I wanted to put this in the description but I didn’t want to. Since usually A* is 2D/Vector2 platforming it can’t really have a part that is upper than the NPC or part (which is the start). If that what your talking about. It only detects walls. You can tell the person that helped me which it is in the description. I just know how to make it to where it can detect walls (including the NPC). Sorry. (Again if that’s what your talking about and I know roblox’s pathfinding service is hell I can relate. Also currently my wifi sucks so I might not know what your talking about)

1 Like

To be honest. I’m not really the best programmer. I usually suck at coding and I’ve been just trying something new. and just testing it.

2 Likes

alright after reviewing that, last video its the `local SIZE = 1` you need to change to`3` or any number but 3 works best for me.

1 Like

but also might have to tell the person that helped me, how to actually make it where it can jump.

also if you roundToStep (function) then do it to the goal part/position.

Make a version of this where you have to place down actual part nodes manually by hand then the module should take in those nodes and calculate a path based on the desired position and start position. This way they wont fall off the edge e.t.c.

quite a while ago I had checked out the tutorial you used to make this, (albeit I had much less successful results) but while it is mainly 2d, in the pathfinding module, I believe you can add Vector3.yAxis (and the corresponding values) to the directions table,. and that MAYBE (?) should fix the crashing.

don’t worry about the module, or anything, errors happen. but I’d say wait for the tutorial guy to release the D* tutorial, it will probably be better

the only reason to use the hell that is a navmesh
but there has to be a better way, maybe shapecasting could be useful for this

doesn’t the debugParts function help you with that? plus the parts don’t fall off there anchored.

I mean yes it can be, but also be helpful for some things like here’s point a there’s point b oh no a wall I have to navigate through it. But I guess maybe you have a point because I don’t know shapecasting I just really test out things with NPCs and Parts and see if they can navigate through it. But if your waiting for the guy to release D* . (is it like Dijkstra?)

also manually placing nodes are in my way are kind of boring honestly. So it creates them for you

a navmesh could have potential, but the way roblox implemented theirs has just made me throw out even the thought of it out the window.

think of them as raycasts with volume,

imagine a raycast is the size of a pixel. with shapecasts, you can make it 1 stud instead
and it can also raycasts as shapes! (e.g. circles,boxes, and even meshes! i think)

its A* but adapts to the environment to my knowledge. I think that it calculates during runtime for if the environment changes

alright. but I guess it could be used for you know shapecast and some other things.