Hello There Developers,
I got a little bored so I decided to make some A* Pathfinding, If you wanna see it in full action go watch the video below!
Creation Process
I wont be diving very deeply into each system but very primitive or vanilla operations were done to create this system, so Its nice to leave a like on this post! 
**HIS AREA IS SOLEY TO SHOW ITS FUNCTIONALITY**
Grid System
Initializer
function makeGrid(size) : {}
local grid = {}
for x = 1, size do
grid[x] = {}
end
for x = 1, size do
for y = 1, size do
grid[x][y] = {x = x, y = y, data={role = "Empty"}}
end
end
return grid
end
function GridModule:Create(Size:number) : GridClass
self = setmetatable({}, {__index = GridModule})
self.Grid = makeGrid(Size)
self._width = 1
self._centre = Vector3.zero
self._size = Size
return self
end
This is where all the magic happens! Briefly this just makes a square grid, specifically square for simplicity,
Basic Operations and Functions
function GridModule:Visualize(Width:number, Centre:Vector3) : Model
if self.VisualGrid and typeof(self.VisualGrid) == "Instance" then self.VisualGrid:Destroy() end
Centre = typeof(Centre) == "Vector3" and Centre or Vector3.zero
Width = typeof(Width) == "number" and Width or 1
self._width = Width
self._centre = Centre
local grid = self.Grid
local model = Instance.new("Model")
model.Name = "Grid"
self.VisualGrid = model
model.Parent = workspace
local GridSize : number = self._size
local totalGridWidth = GridSize * Width
local startOffset = -(totalGridWidth/2) + (Width/2)
for x = 1, self._size do
for y = 1, self._size do
if not self.VisualGrid then print("Stopping grid build process..") break end
local part = Instance.new("Part")
part.Name = `{x}_{y}`
part.Anchored = true
part.Size = Vector3.new(Width, 0.25, Width)
part.Material = Enum.Material.SmoothPlastic
local xPos = startOffset + (x-1) * Width
local zPos = startOffset + (y-1) * Width
part.Position = Vector3.new(xPos, 0, zPos) + Centre
part.Parent = model
if (x + y) % 2 == 0 then
part.Color = PatternColor1 -- Light color
else
part.Color = PatternColor2 -- Dark color
end
end
end
self.VisualGrid = model
return model
end
function GridModule:GetCell(Position: Vector2): (Cell, Part)
local x = Position.X
local y = Position.Y
if not self.Grid[x] then return end
local cell = self.Grid[x][y] or nil
if not cell then return end
local part = self.VisualGrid:FindFirstChild(`{x}_{y}`)
return cell, part
end
function GridModule:SetCellData(Position:Vector2, Data:{})
local cell, part = self:GetCell(Position)
if not cell then warn("Invalid cell") return end
self.Grid[cell.x][cell.y].data = Data
end
function GridModule:HighlightCell(Position: Vector2, Color: Color3 | BrickColor, Role: string): Cell
local cellData, part = self:GetCell(Position)
if not cellData then return end
self.Grid[Position.X][Position.Y].data.role = Role or cellData.role
if not part then return cellData, nil end
part.Color = (typeof(Color) == "BrickColor") and Color.Color or Color
task.wait(0.05)
return cellData, part
end
function GridModule:Clean()
self.Grid = makeGrid(self._size)
self:Visualize(self._width, self._centre)
end
Most of the functions you see here are to visualize the data we’ll produce from the algorithm, Each were made in such a way that its easy to understand but accurate, Here are the types if your eager to see:
type Cell = {
x : number,
y: number,
data : {any}
}
type GridType = {
x:
{y:
{
x:number,
y:number,
data:{any}
}
}
}
type GridClass = {
Grid : {},
VisualGrid : Model,
Visualize : (GridClass, Width:number, Centre:Vector3) -> (Model),
GetCell : (GridClass, Position:Vector2) -> (Cell?),
SetCell : (GridClass, Position:Vector2, data :{any}) -> (Cell?),
HighlightCell : (GridClass, Position:Vector2, Color:Color3 | BrickColor, Role:string) -> (),
GetNeighbouringCells : (GridClass, Position:Vector2, Radius:number) -> ({Cell?}),
DistanceToCell : (GridClass?, Position:Vector2, ToPosition:Vector2) -> (Distance),
GetGridSize : (GridClass, GridType) -> (number),
Clean : (GridClass) -> (),
}
Experimental Functions
function GridModule:GetNeighbouringCells(Position: Vector2, Radius: number): {Cell}
local list = {}
local x = Position.X
local y = Position.Y
Radius = math.max(math.floor(Radius), 1)
for i = x - Radius, x + Radius do
for j = y - Radius, y + Radius do
-- Skip the current cell
if i == x and j == y then continue end
if not self.Grid[i] then continue end
local cell = self.Grid[i][j]
if not cell then continue end
table.insert(list, cell)
end
end
return list
end
function GridModule:IsCellObstacle(Position:Vector2)
local cell = self:GetCell(Position)
if not cell then return true end
return cell.data.role == "Wall"
end
function GridModule:IsCellEmpty(Position:Vector2)
if not Position then return true end
if typeof(Position) ~= "Vector2" then return true end
local cell, part = self:GetCell(Position)
return cell == nil
end
function GridModule.DistanceToCell(Position:Vector2, ToPosition:Vector2) : number
local cell, part = GridModule:GetCell(ToPosition)
if not cell then warn("Invalid cell") return end
local distance = (Position - ToPosition).Magnitude
return distance
end
These are the functions used mostly within the A* Pathfinding algorithm, created with simplicity and efficiency.
A✦ Algorithm
Definition
For a more detailed explanation this Article by Mr. Swift should definitely shoot out all your questions! This algorithm is simple if you really break it down into its finite sections and clear meaning. (remember to refactor!)
According to Wikipedia (23/02/2025) : “A-star is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.). It does this by maintaining a tree of paths originating at the start node and extending those paths one edge at a time until the goal node is reached.”
Implementation
function APath:FindPath(Start: Vector2, Goal: Vector2): ({any}, boolean)
local _0 = tick()
self.Nodes = {}
local Path = {}
local PathFound = false
local StartNode = self:CreateNode(Start, 0, 0, (Goal - Start).Magnitude)
local GoalNode = self:CreateNode(Goal, 0, 0, 0)
local OpenSet = {[Start] = StartNode}
local ClosedSet = {}
local iterations = 0
while next(OpenSet) do
iterations += 1
if iterations % 100 == 0 then task.wait() end
local Current, LowestF = nil, math.huge
for _, Node in pairs(OpenSet) do
if Node.F < LowestF then
Current = Node
LowestF = Node.F
end
end
-- Check if we've reached the goal position
if Current.Position == Goal then
PathFound = true
GoalNode.Parent = Current.Parent
Current = GoalNode
break
end
OpenSet[Current.Position] = nil
ClosedSet[Current.Position] = Current
for _, NeighborPos in ipairs(self:GetNeighbors(Current)) do
if ClosedSet[NeighborPos] then continue end
if self.Env:IsCellEmpty(NeighborPos) or self.Env:IsCellObstacle(NeighborPos) then continue end
local tentativeG = Current.G + 1
local Neighbor = OpenSet[NeighborPos]
if not Neighbor then
Neighbor = self:CreateNode(
NeighborPos,
0,
tentativeG,
(Goal - NeighborPos).Magnitude
)
OpenSet[NeighborPos] = Neighbor
Neighbor.Parent = Current
elseif tentativeG < Neighbor.G then
Neighbor.Parent = Current
Neighbor.G = tentativeG
else
continue
end
Neighbor.F = Neighbor.G + Neighbor.H
end
if iterations > 1000 then
warn("Pathfinding took too long - path may be impossible")
break
end
end
-- Path reconstruction from goal to start
if PathFound then
local Current = GoalNode
while Current do
table.insert(Path, 1, Current.Position)
Current = Current.Parent
end
end
print(`Process Completion Time : {(tick() - _0) * 1000}ms`)
return Path, PathFound
end
This script isn’t user friendly (hard to understand) and is complex to write out completely, so I’d recommend reading the article I provided.
Review
Thank you for reading! If you can, would you please rate this post? All choices are not forced and are not negatively taken, rather its used for Improvement and Engagement.
- Yes!
- Meh…
- Could Be Better.
- No.
0 voters