Pathfinding

Pathfinding is a library of queries your loop calls, not a movement runtime that owns your NPCs. One handler fronts four methods — AStar, ThetaStar, Direct, Roblox — and each is lazily required on first use: a game that never calls AStar never loads it. Searches are synchronous, budgeted, and return reasons on failure, so a sealed-off goal can never eat the frame. Movement is a helper too: the follower wraps re-pathing and waypoint consumption in a per-agent handle that your loop steps.

Mental model

Every method answers the same request shape and returns the same result shape — (true, { Vector3 waypoints }) or (false, reason):

Method	Algorithm	When it wins
AStar	8-connected grid A*, octile heuristic, corner-cut safe	Complete search on a rasterized grid — mazes, dungeons, anywhere the answer must be exact
ThetaStar	Any-angle A* — parents shortcut through grid line of sight	Open ground. Same grid, same cost model, but paths come out as straight segments instead of staircases
Direct	One line test — grid raster line, or a single workspace raycast	“Can I walk straight at it” — the cheapest possible answer, and the default
Roblox	PathfindingService navmesh. Yields	Humanoid NPCs on real terrain — slopes, gaps, jumps, agent radius handled by the engine

AStar and ThetaStar share one implementation: Theta* is A* with an anyAngle flag that eagerly checks line of sight at relaxation and routes a neighbor through its grandparent when the segment is clear and cheaper. Any-angle mode also switches the heuristic from octile to euclidean — octile overestimates euclidean segment costs, and an inadmissible heuristic produces worse paths.

Both searches run their open set on a binary min-heap (Heap.luau): parallel Items/Priorities arrays, push/pop/isEmpty, sift-up and sift-down. 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/grid-Direct run on a Grid: a world rectangle rasterized lazily with caching. No cell is probed until a search touches it, and once probed the answer is cached until you say the map changed.

local Root = game:GetService("ServerScriptService").ChloeKernelServer
local Pathfinding = require(Root.Pathfinding)

return function(kernel)
  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 path plane
    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),
  })
end

Grid construction

Field	Default	Description
Origin	required	Min-X/min-Z world corner. Origin.Y is the waypoint plane when no ground heights exist
Width / Height	required	Cell counts along X / Z
CellSize	4	Studs per cell
AgentHeight	6	Clearance column height for the default rasterizer
MaxStepHeight	4	Max climbable rise between adjacent cells, and the line-of-sight height band
IsWalkable	default rasterizer	(position) → (boolean, groundY?). Inject for RTS maps, dungeons, or deterministic specs

The default rasterizer

When you don’t inject IsWalkable, the grid probes the live workspace. Per cell it:

1. Raycasts down for ground (from +100 studs, 300 studs deep). Terrain, parts, and model geometry all count; RespectCanCollide means CanCollide = false decor is never floor. No hit means void — not walkable.
2. Skips bodies. Anything under a Humanoid model is excluded from the ray and never rasterizes — players and NPCs are transient, and a cell probed while someone stood on it would cache blocked forever, including the asker’s own start cell.
3. Requires the clearance column open. A GetPartBoundsInBox query checks the agent-height column above ground for CanCollide obstacles. The column starts at step height (min(2, AgentHeight / 2) above ground), so a 1-stud lip or shin-high debris doesn’t dead-strip the ring of cells around it.
4. Narrow-phases non-block shapes. The overlap query matches bounding boxes, and a wedge ramp’s bbox is a full-height slab that would block every cell of its own slope. Wedges, cylinders, meshes, and unions confirm against real geometry with five footprint down-rays (center plus four inset corners); blocks still test exactly by bbox.

The rasterizer returns the ground Y, so waypoints follow elevation and searches can reject cliffs.

Heights, cliffs, and step limits

When cells carry ground heights, every step in A*/Theta*/distanceField is gated: adjacent cells differing by more than MaxStepHeight read as cliffs and are refused. The same limit gates straight lines — see feet and photons below — so a Theta* shortcut can never walk an agent off a sheer cliff that a stepwise search would refuse.

Cache invalidation

Call	Effect
grid:refresh()	Clears the whole walkability + height cache. Cells re-rasterize lazily on next touch. Bumps grid.Version
grid:refreshRegion(minWorld, maxWorld)	Drops only the cells inside the world rect — a sliding gate invalidates the cells it swept, the rest of the map keeps its cache. Bumps grid.Version

Version is the re-path signal: followers compare their route’s version to the grid’s each step, so a moved gate invalidates cached routes without you telling anyone.

Caution

Cells cache forever until a refresh. If geometry moves and you never call refresh()/refreshRegion(), searches keep answering from the stale raster. Wire your door/gate/elevator code to refreshRegion with the swept bounds.

Off-mesh links

grid:addLink(fromWorld, toWorld, cost?) authors jump/vault edges the step rules cannot express — ledges, window sills, gaps. A*/Theta* traverse links as graph edges but never Theta-shortcut across them*: grid line of sight does not hold across a jump. Cost is in cell units and defaults to the straight-line cell distance; raise it to model climb time. Links are one-way (call twice for both directions) and survive refresh().

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

Followers emit Jump = true when the next waypoint rises past step reach, so humanoid movers hop the link.

Forgiving inputs

grid:nearestWalkable(position, maxCells?) is the front door for user-driven queries: it clamps off-grid points into bounds, then searches outward ring by ring (default 8 rings) for the closest standable cell center. A click on top of a wall snaps to the ground beside it instead of failing on a technicality. Returns nil when no ring has a walkable cell.

Feet and photons

Walking and seeing are different queries, and the grid answers both:

• grid:lineOfSight(x0, z0, x1, z1) — “can I walk straight there.” A Bresenham cell walk where diagonals require both adjacent cardinals open (no corner threading), cells above the endpoints’ height band (± MaxStepHeight) block, and consecutive line cells must differ by ≤ MaxStepHeight — otherwise a Theta* shortcut could cross an in-band cliff.
• grid:sightLine(x0, z0, x1, z1) — “can I see there.” Same walk, different blocking rules: valleys and pits below the band stay transparent to eyes, only ground rising past the band (or an eye-level obstruction) occludes, 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. NPCKit vision rides sightLine and movement rides lineOfSight — see Senses for how hearing plugs in.

Searching

local Ok, Result = Paths:find({
  Method = "ThetaStar", -- AStar | ThetaStar | Direct | Roblox. Default "Direct"
  Grid = Arena, -- required by AStar/ThetaStar; optional LoS source for Direct
  Start = StartPosition,
  Goal = GoalPosition,
  MaxExpansions = 4096, -- A*/Theta* search budget. Default 8192
})
if Ok then
  -- Result is { Vector3 } — Start first, exact Goal last
else
  warn("no route:", Result)
end

Waypoints carry exact endpoints: the first waypoint is Start verbatim, and the last cell center is overwritten with the exact Goal. Waypoint Y comes from cell ground heights when the rasterizer reports them.

Direct without a Grid raycasts the live workspace instead — pass Exclude = { Npc.Model } or the agent blocks its own ray. Roblox passes AgentParams straight to PathfindingService:CreatePath and yields while the engine computes.

Failure reasons

Reason	Source	Meaning
StartOutsideGrid / GoalOutsideGrid	AStar, ThetaStar, Direct	Endpoint doesn’t land on the grid rectangle
StartBlocked / GoalBlocked	AStar, ThetaStar	Endpoint cell rasterized unwalkable
NoPath	AStar, ThetaStar	Search exhausted — 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: … / a PathStatus name	Roblox	Engine-side failure

Paths.Stats counts Searches and Failed across all methods — cheap health telemetry for a debug panel.

Distance fields

Paths:distanceField({ Grid, Origin, MaxDistance? }) Dijkstra-floods route distances from one origin out to MaxDistance studs, with the same step rules as A*. One search answers “how far by the actual route” for every listener at once — it backs emitSound’s Path occlusion in NPCKit, so a gunshot near fifty listeners costs one flood, not fifty searches.

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

The result is keyed by cell key ((z - 1) * Width + x); unreachable cells are simply absent. Returns nil when the origin is off-grid or blocked.

The follower

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

local RunService = game:GetService("RunService")

local Npc = workspace.Cultist -- a Humanoid model
local Target = workspace.Shrine -- any Part to walk to

local Chaser = Pathfinding.follower({
  Paths = Paths,
  Grid = Arena,
  Method = "ThetaStar", -- plain field: writable between steps
})

RunService.Heartbeat:Connect(function()
  local RootPart = Npc.PrimaryPart
  local Humanoid = Npc:FindFirstChildOfClass("Humanoid")
  if not RootPart or not Humanoid then
    return
  end
  local NextPoint, Info = Chaser:step(RootPart.Position, Target.Position)
  Humanoid:MoveTo(NextPoint)
  if Info.Jump or Info.Stuck then
    Humanoid.Jump = true
  end
end)

Each step handles:

• Re-pathing when there was never a route, the goal drifted 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 NPC holding position would re-search every step.
• Failure backoff — a failed search sets a 1-second no-path window; the raw goal is returned meanwhile, so an unreachable goal never re-burns the full search budget every tick.
• Waypoint consumption — waypoints within ArriveDistance (flat XZ distance) are consumed; the first remaining waypoint is the returned point, falling back to the raw goal.
• A stuck watchdog — under 1 stud of ground covered over a full second drops the route and flags Stuck = true; the caller should jump and keep stepping. Agents already settled at their point skip the check, or an NPC holding position would be flagged (and hopped) once a second.
• Jump hints — Jump = true when the next point rises more than 2.5 studs within 8 horizontal studs (links, ledges).
• Off-thread "Roblox" — ComputeAsync yields, so the follower runs it in a spawned task and adopts the result on the caller’s thread at the next step. Your loop never stalls on the navmesh.

follower:reset() drops the route and watchdog memory — call it on teleports and target swaps. Info.Path carries the full fresh route (agent position first) whenever a search succeeded that step, for debug drawing or client hinting.

Budgets and the scheduler

Grid searches are synchronous and bounded by MaxExpansions (default 8192 node expansions), so a find call fits inside a Scheduler job without blowing the frame budget — size the budget to your grid, not to the worst case. "Roblox" is the exception: it yields, so run it off-thread (the follower already does). For batches of searches — fifty NPCs re-planning at once, terrain analysis — move the whole grid computation onto ActorPool workers with an injected IsWalkable over plain data; grids built on the default rasterizer touch the workspace and must stay on the main thread.

How NPCKit consumes it

NPCKit takes { Pathfinding = Paths, Grid = Arena } at attach and wires the whole stack: npc:moveTowards is a thin wrapper over a follower, vision checks ride sightLine, movement legality rides lineOfSight, and Sounds = { Occlusion = "Path" } measures hearing distance through one distanceField flood per noise. Nothing in the kit re-implements a search — it’s the same four methods behind the same front door. Recipes live in the NPCs & pathfinding cookbook.

API reference

Pathfinding

Member	Description
Pathfinding.attach(kernel?) → paths	Handler instance. kernel is optional — only Stats live here
paths:find(request) → (ok, waypointsOrReason)	Run one search. request: {Method? = "Direct", Start, Goal, Grid?, MaxExpansions?, Exclude?, AgentParams?}. "Roblox" yields
paths:distanceField({Grid, Origin, MaxDistance?}) → {[cellKey] = studs}?	One Dijkstra flood serving many listeners. nil when the origin is off-grid or blocked
Pathfinding.grid(config) → grid	Build a lazy grid — config table above
Pathfinding.follower(options) → follower	Per-agent following handle — {Paths, Grid, Method? = "ThetaStar", RepathDistance? = CellSize, ArriveDistance? = max(2, CellSize / 2), Clock? = os.clock}
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	Cell center; Y from 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 for a rasterized cell; nil when the rasterizer reports no heights
grid:nearestWalkable(position, maxCells? = 8) → Vector3?	Clamp into bounds, then ring-search for the nearest standable cell center
grid:lineOfSight(x0, z0, x1, z1) → boolean	Feet: corner-safe, height-band and per-step gated
grid:sightLine(x0, z0, x1, z1) → boolean	Eyes: pits stay clear, rising ground and eye-level walls occlude
grid:refresh()	Drop the whole cache; bump Version. Links survive
grid:refreshRegion(minWorld, maxWorld)	Drop only the swept cells; bump Version
grid:addLink(fromWorld, toWorld, cost?)	One-way off-mesh jump/vault edge; cost in cell units, default straight-line distance. Errors if an endpoint is off-grid
grid.Version	Increments on refresh — followers re-path on change
grid.Width / grid.Height / grid.CellSize / grid.Origin / grid.MaxStepHeight	Construction values, readable

Follower

Member	Description
follower:step(position, goal) → (nextPoint, info)	info = { Path: {Vector3}?, Jump: boolean, Stuck: boolean }
follower:reset()	Drop route and watchdog memory (teleports, target swaps)
follower.Method / follower.RepathDistance	Plain fields — writable between steps

Bus topics

Pathfinding publishes and consumes nothing on the Bus. It is a pure query library — consumers like NPCKit own the events.

Design notes

Caution

Direct without a Grid raycasts the live workspace — always pass Exclude = { Npc.Model } or the agent’s own character blocks the ray. With a Grid, Direct answers from the raster cache instead and costs no raycast at all.

Caution

"Roblox" yields the calling thread. Never call it from a scheduler job or a hot loop directly — hand it to a follower (which computes off-thread) or wrap it in task.spawn yourself.

Status

Grid searches, line-of-sight rules, height gates, distance fields, off-mesh links, cache invalidation, and nearestWalkable are spec-verified with injected walkability over deterministic ASCII maps — no workspace access. The default rasterizer and the "Roblox" method touch the live engine (raycasts, PathfindingService); both run in Studio, but their behavior depends on your map’s real geometry.