Pathfinding

Pathfinding is a library of queries your code calls. It does not own a loop or move anyone. One handler fronts four methods, AStar, ThetaStar, Direct and Roblox, and each is required the first time it is used, so a game that never calls AStar never loads it. Grid searches are synchronous, bounded by an expansion budget, and return a reason when they fail, so a sealed-off goal cannot eat a frame. Movement is a helper too: a follower wraps re-pathing and waypoint consumption in a per-agent handle that your own loop steps. NPCKit builds its movement on followers, and Senses and NPCKit vision use the grid’s sight lines.

Mental model

Every method takes the same request and answers (true, { Vector3 }) or (false, reason):

Method	Algorithm	Use it for
AStar	8-connected grid A*, octile heuristic, no corner cutting	Exact routes on a rasterized grid: mazes, dungeons, anywhere the answer must be complete.
ThetaStar	Any-angle A*: a node’s parent can shortcut through grid line of sight	Open ground. Same grid and costs as AStar, but paths come out as straight segments instead of staircases.
Direct	One line test: a grid raster line, or one world raycast	“Can I walk straight at it.” The cheapest answer, and the default method.
Roblox	PathfindingService navmesh. Yields.	Humanoid NPCs on real terrain, where the engine handles slopes, gaps, jumps, agent size and PathfindingLinks.

AStar and ThetaStar are one implementation. ThetaStar runs A* with an any-angle flag that checks line of sight when it relaxes a neighbor and routes the neighbor through its grandparent when that segment is clear and no longer. Any angle mode also switches the heuristic from octile to euclidean: octile overestimates the cost of a straight segment, and an inadmissible heuristic produces worse paths.

Both searches keep their open set in a binary min-heap (Heap.luau). There is no decrease-key: an improved node is pushed again, and the stale entry is skipped when it pops against the closed set.

Grids

AStar, ThetaStar and grid Direct run on a grid: a world rectangle rasterized lazily and cached. No cell is probed until a search touches it, and a probed cell stays cached until you say the map changed.

local Paths = Pathfinding.attach(kernel)
local Arena = Pathfinding.grid({
  Origin = Vector3.new(-200, 0, -200), -- min-X/min-Z corner; Origin.Y is the fallback waypoint height
  Width = 100, -- cells along X
  Height = 100, -- cells along Z
  CellSize = 4, -- studs per cell
})

local Ok, Waypoints = Paths:find({
  Method = "AStar",
  Grid = Arena,
  Start = Vector3.new(-180, 0, -180),
  Goal = Vector3.new(120, 0, 90),
})

Grid construction

Field	Default	Description
Origin	required	The min-X/min-Z world corner. Origin.Y is the waypoint height when no ground heights exist.
Width, Height	required	Cell counts along X and Z.
CellSize	4	Studs per cell.
AgentHeight	6	Clearance column height for the default rasterizer.
MaxStepHeight	4	Largest rise between adjacent cells, and the height band for line tests.
IsWalkable	the default rasterizer	(position) -> (boolean, groundY?). Inject one for RTS maps, dungeons, deterministic specs, or grids searched on ActorPool workers.

The default rasterizer

Without IsWalkable, the grid probes the live Workspace. For each cell it:

1. Raycasts down for ground from 100 studs above the cell center, 300 studs long. Terrain, parts and models count. The ray respects CanCollide, so decor with CanCollide = false is never floor. No hit means void, and the cell is not walkable.
2. Skips bodies. Anything under a model with a Humanoid is excluded from the ray and never rasterizes: players and NPCs move, and a cell probed while someone stood on it would stay cached as blocked, including the asker’s own start cell.
3. Requires the clearance column to be open. GetPartBoundsInBox checks the column above the ground for parts with CanCollide on. The column starts at step height (min(2, AgentHeight / 2) above the ground), so a low lip or loose debris does not block the ring of cells around it.
4. Confirms non-block shapes against real geometry. The overlap query matches bounding boxes, and a wedge ramp’s box is a full-height slab that would block its own slope. Wedges, cylinders, balls, meshes and unions are confirmed with five down-rays (the cell center and four inset corners) filtered to that part. Blocks still block by bounding box.

The rasterizer returns the ground Y, so waypoints follow elevation and searches can refuse cliffs. Its query parameter objects are built once per grid and reused for every probe.

Heights, cliffs and step limits

When cells carry ground heights, every step in AStar, ThetaStar and distanceField is gated: adjacent cells whose heights differ by more than MaxStepHeight are a cliff and the step is refused. The same limit gates straight lines (see Feet and photons), so a Theta* shortcut can never walk an agent off a cliff that a step-by-step search would refuse.

Cache invalidation

Call	Effect
grid:refresh()	Clears the whole walkability and height cache. Cells rasterize again on their next touch. Increments grid.Version.
grid:refreshRegion(minWorld, maxWorld)	Clears only the cells inside the world rectangle, for a sliding gate or an opening door. Increments grid.Version.

Version is the re-path signal. A follower compares its route’s version with the grid’s on every step, so a moved gate invalidates cached routes without anyone being told.

Caution

Cells stay cached until a refresh. If geometry moves and nothing calls refresh() or refreshRegion(), searches keep answering from the old raster. Wire door, gate and elevator code to refreshRegion with the swept bounds.

Off-mesh links

grid:addLink(fromWorld, toWorld, cost?) adds a jump or vault edge the step rules cannot express: a ledge, a window sill, a gap. AStar and ThetaStar traverse links as graph edges but never shortcut across them, because grid line of sight does not hold across a jump. The cost is in cell units and defaults to the straight-line cell distance; raise it to model climb time. Links are one-way (add two for both directions), survive refresh(), and error when an endpoint is off the grid.

Arena:addLink(LedgeBottom, LedgeTop, 6) -- costs 6 cells of walking: the climb takes time

A follower reports Jump = true when the next waypoint rises past step reach, so a humanoid hops the link.

Forgiving inputs

grid:nearestWalkable(position, maxCells?) is the entry point for player-driven targets. It clamps an off-grid point into bounds, then searches outward ring by ring (8 rings by default) for the closest walkable cell center. A click on top of a wall snaps to the ground beside it. It returns nil when no ring has a walkable cell.

Feet and photons

Walking and seeing are different questions, and the grid answers both with a Bresenham cell walk:

• grid:lineOfSight(x0, z0, x1, z1) asks whether an agent can walk straight there. A diagonal step needs both adjacent cardinal cells open (no threading through corners). Cells whose ground sits outside the endpoints’ height band (the lower endpoint minus MaxStepHeight to the higher plus MaxStepHeight) block, and consecutive cells on the line may differ by at most MaxStepHeight. Without that last rule a Theta* shortcut could cross a cliff that stays inside the band.
• grid:sightLine(x0, z0, x1, z1) asks whether an agent can see there. Ground below the band never blocks, so pits and valleys stay transparent. Ground rising above the band blocks, an unwalkable cell blocks unless its ground sits below the band, and there is no corner rule: sight passes diagonal gaps that walking cannot.

A trench blocks feet but not eyes. A ridge blocks both. A wall’s walkable top surface still occludes, because it rises above the band. NPCKit vision uses sightLine and movement uses lineOfSight; Senses covers hearing.

Searching

local Ok, Result = Paths:find({
  Method = "ThetaStar", -- AStar | ThetaStar | Direct | Roblox. Default "Direct"
  Grid = Arena, -- required by AStar and ThetaStar; optional line-of-sight source for Direct
  Start = StartPosition,
  Goal = GoalPosition,
  MaxExpansions = 4096, -- AStar/ThetaStar budget. Default 8192
})
if Ok then
  -- Result is { Vector3 }: Start first, the exact Goal last
else
  -- Result is a reason string, such as "NoPath" or "BudgetExhausted"
end

Grid routes carry exact endpoints: the first waypoint is Start itself and the last cell center is replaced with the exact Goal. Waypoint Y comes from the cells’ ground heights when the rasterizer reports them.

Direct without a Grid raycasts the Workspace from Start to Goal with RespectCanCollide = true, so trigger volumes and other non-colliding parts never block a walk line. Pass Exclude = { Npc.Model } or the agent blocks its own ray. The parameter object is created on the first world test and reused.

Roblox yields while the engine computes. It builds a Path with PathfindingService:CreatePath(AgentParams), or recomputes the Path passed in the request (its agent parameters were fixed when it was created). It returns three more values:

local Ok, Waypoints, Path, Jumps, Details = Paths:find({
  Method = "Roblox",
  Start = From,
  Goal = To,
  AgentParams = { AgentRadius = 3, AgentHeight = 6, AgentCanJump = true },
})
-- Path: the engine Path, returned on failure too so you can recompute it with { Path = Path }
-- Jumps: { [waypointIndex] = true } for waypoints whose Action is Jump
-- Details: the engine's PathWaypoints (Position, Action, Label); a Custom action starts a PathfindingLink crossing

Failure reasons

Reason	Methods	Meaning
AStar needs request.Grid (build one with Pathfinding.grid)	AStar, ThetaStar	No grid in the request.
StartOutsideGrid, GoalOutsideGrid	AStar, ThetaStar, grid Direct	An endpoint is off the grid rectangle.
StartBlocked, GoalBlocked	AStar, ThetaStar	An endpoint cell rasterized as not walkable.
NoPath	AStar, ThetaStar	The search ran out of cells: the goal is sealed off.
BudgetExhausted	AStar, ThetaStar	More than MaxExpansions nodes expanded. Raise the budget or accept the miss.
Blocked	Direct	The straight line is obstructed.
ComputeAsync failed: ..., or a PathStatus name such as NoPath	Roblox	The engine could not route.

An unknown Method errors with the list of valid names. paths.Stats counts Searches and Failed across every method, which is enough for a debug panel row.

Distance fields

paths:distanceField({ Grid, Origin, MaxDistance? }) floods route distances outward from one origin with Dijkstra, up to MaxDistance studs, under the same step rules as A*. One flood answers “how far by the actual route” for every listener at once. It backs NPCKit’s emitSound path occlusion, so a gunshot near fifty listeners costs one flood instead of fifty searches.

local Field = Paths:distanceField({ Grid = Arena, Origin = ShotPosition, MaxDistance = 80 })
if Field then
  local X, Z = Arena:worldToCell(ListenerPosition)
  if X and Z then
    local RouteDistance = Field[(Z - 1) * Arena.Width + X] -- nil: not reachable within MaxDistance
  end
end

The result is keyed by cell key, (z - 1) * Width + x, and leaves unreachable cells out. It is nil when the origin is off the grid or blocked.

The follower

Pathfinding.follower(options) is per-agent waypoint following. Build one per agent, call step(position, goal) from your own loop, and apply the returned point however the agent moves: Humanoid:MoveTo, a root velocity, a vehicle controller. The follower never owns a loop, and step never yields.

src/Server/Game/Services/CultistService.luau

--!strict
-- CultistService: walks the cultist to the shrine while the ritual runs.

local ServerScriptService = game:GetService("ServerScriptService")

local Pathfinding = require(ServerScriptService.ChloeKernelServer.Pathfinding)

local CultistService = {
  Name = "CultistService",
}

function CultistService.init(self: any, kernel: any)
  self.Kernel = kernel
  self.Paths = Pathfinding.attach(kernel)
  self.Grid = Pathfinding.grid({ Origin = Vector3.new(-200, 0, -200), Width = 100, Height = 100 })
end

function CultistService.start(self: any)
  self.Connection = self.Kernel.Bus:subscribe("Ritual.Started", function(_, cultist: Model, shrine: BasePart)
    self:walk(cultist, shrine)
  end)
end

function CultistService.walk(self: any, cultist: Model, shrine: BasePart)
  local Chaser = Pathfinding.follower({ Paths = self.Paths, Grid = self.Grid, Method = "ThetaStar" })
  if self.Job then
    self.Job:cancel()
  end
  self.Job = self.Kernel.Scheduler:every(0.1, function()
    local Root = cultist.PrimaryPart
    local Humanoid = cultist:FindFirstChildOfClass("Humanoid")
    if not Root or not Humanoid or cultist.Parent == nil or (Root.Position - shrine.Position).Magnitude < 4 then
      self.Job:cancel() -- gone, or arrived: nothing left to follow
      self.Job = nil
      return
    end
    local NextPoint, Info = Chaser:step(Root.Position, shrine.Position)
    Humanoid:MoveTo(NextPoint)
    if Info.Jump or Info.Stuck then
      Humanoid.Jump = true
    end
  end, self.Kernel.Priority.Normal)
end

function CultistService.stop(self: any)
  if self.Job then
    self.Job:cancel()
  end
  if self.Connection then
    self.Connection:disconnect()
  end
end

return CultistService

Each step:

• Re-paths when there was never a route, the goal moved more than RepathDistance, or Grid.Version changed. An empty waypoint list is not stale on its own: it means the agent already walked the route. Without that rule an agent holding position would search on every step.
• Backs off for 1 second after a failed search and returns the raw goal meanwhile, so an unreachable goal does not burn the full search budget on every tick.
• Consumes waypoints within ArriveDistance, measured flat on X and Z, and returns the first remaining one, or the raw goal when none remain.
• Runs a stuck watchdog: less than 1 stud of movement over a full second drops the route and sets Stuck = true. The caller should jump and keep stepping. An agent already within ArriveDistance of its point skips the check, or one holding position would be flagged, and hopped, once a second.
• Sets Jump = true when the next point rises more than 2.5 studs within 8 horizontal studs (links, ledges).

Info.Path carries the full fresh route, agent position first, on the step where a search succeeded. Use it for debug drawing or client hints. follower.Method and follower.RepathDistance are plain fields you can change between steps.

Roblox followers

With Method = "Roblox" the follower runs ComputeAsync on its own thread and adopts the result on the caller’s thread at a later step, so your loop never stalls on the navmesh. Beyond the rules above:

• One Path per follower. The first search creates it with the follower’s AgentParams (AgentRadius, AgentHeight, AgentCanJump, AgentCanClimb, WaypointSpacing, Costs); every re-path recomputes that same Path. Only one ComputeAsync runs on it at a time. Changing AgentParams after the first search has no effect.
• The follower watches the route’s Path.Blocked. A block reported at or past the next waypoint drops the route, and the next step re-paths. A block behind the agent is ignored, and so is one that arrives while a newer route is being computed or waiting to be adopted.
• Info.Jump is also set when the next waypoint is one the navmesh marked Jump.
• Info.Link = { Label, From, To } reports a PathfindingLink crossing. When the agent has reached the link’s start (a waypoint whose action is Custom), the next point is the landing, and step returns the same table on every step until the agent reaches it. Being close on X and Z is not enough: a rising link’s landing counts once the agent has climbed to its height, and any other landing once the agent is no more than 5 studs above it, so a ladder’s top is not skipped while the agent stands at its foot. Compare the table by identity to run a traverse once.
• follower:reset() drops the route and the watchdog memory, releases the Path.Blocked watch, and discards a search still running: its result is ignored when it lands, and the next search waits for it to finish before recomputing the shared Path. Call it on teleports and target changes.

A Roblox follower still needs a Grid: Grid.CellSize sets the RepathDistance and ArriveDistance defaults and Grid.Version drives re-paths. The navmesh search never rasterizes it, so any Pathfinding.grid works.

Budgets and the scheduler

Grid searches are synchronous and bounded by MaxExpansions (default 8192 expansions), so a find call fits inside a Scheduler job without breaking the frame budget. Size the budget to your grid. Roblox is the exception: it yields, so run it off the scheduler step (the follower already does). For batches, such as fifty NPCs re-planning at once, run the grid search on ActorPool workers with an injected IsWalkable over plain data. A grid on the default rasterizer queries the Workspace, and PathfindingService is not thread safe, so both stay on the main thread.

How NPCKit consumes it

NPCKit takes { Pathfinding = Paths, Grid = Arena } at attach. npc:moveTowards wraps one follower per NPC and picks ThetaStar or AStar from the NPC’s path skill unless the kit sets PathMethod. With PathMethod = "Roblox", the follower gets the archetype’s AgentParams, with AgentRadius and AgentHeight defaulting from the rig’s extents. A route that reaches a PathfindingLink publishes Npc.PathLink(npc, label, from, to) once and runs the archetype’s Traverse[label](npc, from, to) handler, which moves the NPC across the link. Vision checks use sightLine, and Sounds = { Occlusion = "Path" } measures hearing through one distanceField flood per noise. Recipes live in the NPCs and pathfinding cookbook.

API reference

Pathfinding

Member	Description
Pathfinding.attach(kernel?) -> paths	The handler. kernel is optional; only Stats lives here.
paths:find(request) -> (ok, waypointsOrReason, path?, jumps?, details?)	One search. request: { Method? = "Direct", Start, Goal, Grid?, MaxExpansions?, Exclude?, AgentParams?, Path? }. The last three results come from Roblox, which yields; path is returned on failure too.
paths:distanceField({ Grid, Origin, MaxDistance? }) -> { [cellKey]: number }?	One Dijkstra flood of route distances in studs. nil when the origin is off the grid or blocked.
Pathfinding.grid(config) -> grid	A lazy grid. Config in Grid construction.
Pathfinding.follower(options) -> follower	A per-agent follower. Options: { Paths, Grid, Method? = "ThetaStar", RepathDistance? = CellSize, ArriveDistance? = max(2, CellSize / 2), Clock? = os.clock, AgentParams? }.
paths.Stats	{ Searches, Failed } counters.

Grid

Member	Description
grid:worldToCell(position) -> (x?, z?)	nil, nil when the point is off the rectangle.
grid:cellToWorld(x, z) -> Vector3	The cell center. Y is the rasterized ground height, else Origin.Y.
grid:isWalkable(x, z) -> boolean	Probes and caches on first touch. Out of bounds is false.
grid:groundY(x, z) -> number?	Ground height of a rasterized cell; nil when the rasterizer reports no heights.
grid:nearestWalkable(position, maxCells? = 8) -> Vector3?	Clamps into bounds, then searches rings for the nearest walkable cell center.
grid:lineOfSight(x0, z0, x1, z1) -> boolean	Feet: no corner threading, height band, per-step limit.
grid:sightLine(x0, z0, x1, z1) -> boolean	Eyes: pits stay clear, rising ground and eye-level obstructions block.
grid:refresh()	Drops the whole cache and increments Version. Links survive.
grid:refreshRegion(minWorld, maxWorld)	Drops the cells inside the rectangle and increments Version.
grid:addLink(fromWorld, toWorld, cost?)	A one-way off-mesh edge. Cost in cell units, default the straight-line distance. Errors when an endpoint is off the grid.
grid.Version	Increments on every refresh. Followers re-path when it changes.
grid.Width, grid.Height, grid.CellSize, grid.Origin, grid.MaxStepHeight	The construction values.

Follower

Member	Description
follower:step(position, goal) -> (nextPoint, info)	info is { Path: { Vector3 }?, Jump: boolean, Stuck: boolean, Link: { Label, From, To }? }. Never yields.
follower:reset()	Drops the route and watchdog memory, releases the Path.Blocked watch and discards a running search.
follower.Method, follower.RepathDistance	Plain fields, writable between steps.

Bus topics

Pathfinding publishes and consumes nothing on the Bus. It is a query library; consumers such as NPCKit own the events (Npc.Path, Npc.PathLink).

Design notes

Caution

Direct without a Grid raycasts the Workspace. Pass Exclude = { Npc.Model }, or the agent’s own body blocks the ray. With a Grid, Direct answers from the raster cache and casts no ray.

Caution

Method = "Roblox" yields the calling thread. Never call it from a Scheduler job or a tight loop. Hand it to a follower, which computes off-thread, or wrap it in task.spawn.

Status

Tests/Pathfinding.spec.luau covers the grid methods with injected walkability over deterministic ASCII maps (routes, failure reasons, Theta* shortcuts, height gates, line and sight rules, distance fields, off-mesh links, nearestWalkable, refresh and refreshRegion) and the Roblox follower against Path doubles: blocks ahead and behind, jump waypoints, reset during a search, one Path per follower with its AgentParams, and link crossings. The Studio spec gate runs all of it. The gameplay regression runner runs the follower suite, plus world checks that Direct passes through non-colliding volumes and that the default rasterizer confirms non-block shapes with its footprint rays. Real navmesh routes and real map geometry need a play test on your own map.