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.
