A* Pathfinding (Roblox / Rojo)

A grid-based A* pathfinding system for Roblox, built for grids on complex terrain (uneven ground or maze-like walls) with support for dynamic, moving obstacles. The grid is generated at runtime by raycasting the actual terrain — no manual navmesh baking required.

Table of Contents

• Features
• Architecture
• Setup
• Usage
• Configuration
• How It Works
• Known Limitations
• Troubleshooting

Features

• Runtime grid generation via downward raycasts (no pre-baked navmesh)
• A* pathfinding with 8-directional movement, corner-cut prevention, and an octile heuristic
• Dynamic obstacle support — only the changed region is rescanned, not the whole grid
• Scan region is derived automatically from the Start/Goal parts (no separate bounds markers needed)
• Debug visualization: a countdown, waypoints revealed one at a time with a color gradient from start to goal

Architecture

src/
  shared/
    GridScanner.luau   -- builds/updates the walkable grid via raycasts
    AStar.luau          -- A* search over the grid
  server/
    PathfindingTest.server.luau  -- usage example / demo

GridScanner and AStar are independent modules with no dependency on each other's internals — AStar.FindPath only calls GridScanner:GetCell and GridScanner:GetClosestCellCoords, so either module can be swapped out (e.g. a different search algorithm, or a different grid source) without touching the other.

Setup

1. Install Rojo (recommended via Rokit):

   rokit init
   rokit add rojo-rbx/rojo

2. Install the Rojo Studio plugin (search "Rojo" in the Creator Store, or install manually from the Rojo GitHub releases).
3. Serve the project:

   rojo serve

4. In Studio, open the Rojo plugin panel and click Connect (localhost:34872 by default).

Usage

Place two parts in Workspace:

Name	Type	Purpose
PathStart	Part	Path start point
PathGoal	Part	Path goal point

Tag any part that should block movement with the DynamicObstacle CollectionService tag (Model > Tag Editor, or CollectionService:AddTag(part, "DynamicObstacle")).

Running PathfindingTest.server.luau will:

1. Print a 5-second countdown (5, 4, 3, 2, 1, Start!) in the Output panel
2. Scan the region around PathStart/PathGoal and run A*
3. Reveal the path one waypoint at a time as colored cubes, and print Finish! once the reveal completes
4. Rescan and recompute automatically whenever a DynamicObstacle-tagged part is added, removed, or moved

Minimal example

GridScanner and AStar can be used directly without the demo script, for example from any server-side module:

local GridScanner = require(ReplicatedStorage.Modules.GridScanner)
local AStar = require(ReplicatedStorage.Modules.AStar)

-- Build a grid covering a 100x100 stud region, 4 studs per cell
local grid = GridScanner.new(Vector3.new(-50, 20, -50), Vector3.new(50, 20, 50), 4)
grid:ScanAll()

-- Find a path between two world-space points
local path = AStar.FindPath(grid, startPart.Position, goalPart.Position)
if path then
	for _, waypoint in path do
		print(waypoint) -- Vector3, in order from start to goal
	end
else
	warn("no path found")
end

-- When an obstacle moves, only rescan the area it occupies
grid:RescanRegion(obstacleWorldMin, obstacleWorldMax)

Configuration

All tunable values live as named constants near the top of each file:

File	Constant	Meaning
GridScanner.luau	DEFAULT_CELL_SIZE	Grid cell size in studs
GridScanner.luau	MIN_FLOOR_NORMAL_Y	Max slope steepness still considered walkable
GridScanner.luau	OBSTACLE_CHECK_HEIGHT	Height of the overlap check above the floor
GridScanner.luau	FLOOR_TOLERANCE	How far above the floor counts as "on top of a wall"
PathfindingTest.server.luau	GRID_PADDING	Margin (studs) added around the Start/Goal bounding box
PathfindingTest.server.luau	REVEAL_DELAY / COUNTDOWN_SECONDS	Debug visualization timing

How It Works

Grid generation. For each cell, a single downward raycast finds the landing surface. A first pass over the whole region records the lowest landing height as the reference floor; a second pass marks any cell that landed noticeably higher as "on top of a wall" (unwalkable), and only checks for loose obstacles above cells that landed near the real floor. This keeps grid generation to one raycast per cell while still correctly rejecting vertical walls — a plain "raycast down, then look for obstacles above the landing point" approach gets fooled by walls, because the ray lands on the wall's top instead of the true floor.

Search. A* runs over the grid with a binary min-heap as the open set (O(log n) push/pop, using lazy deletion instead of decrease-key: stale entries are simply skipped via a closed set rather than removed from the heap). The heuristic is octile distance, which is tight and admissible for 8-directional grids with diagonal cost √2 — Manhattan distance underweights diagonal movement, and Euclidean distance is looser than necessary. Diagonal moves are only allowed when both straight neighbors are walkable, preventing the path from cutting across wall corners.

Dynamic obstacles. Instead of rescanning the entire grid whenever an obstacle changes, only the world-space region touched by that obstacle (plus a small margin) is rescanned, keeping updates proportional to the size of the change rather than the size of the map.

Known Limitations

• Single floor height per (X, Z) column. The floor-vs-wall classification assumes one walkable height at each grid cell — bridges, overpasses, or multi-level structures at the same X/Z position are not supported.
• GRID_PADDING trade-off. The scan region is derived from Start/Goal position plus a fixed margin. Too small, and a path that needs to detour further than the margin won't be found. Too large, and the scan region can spill past a level's outer walls into open exterior space, letting A* route around the outside of a maze instead of through it. Keep this close to one cell size unless you know the level needs more room, and make sure open exterior space isn't reachable from Start/Goal within that margin (e.g. wall it off, as the maze Start point in this project does).
• No concurrent obstacle-change throttling. Rapid obstacle changes each trigger a rescan + recalculation; a run-ID guard prevents overlapping debug-visualization races, but there's no debounce on the underlying recalculation itself. Add one if obstacles change frequently in your game.

Troubleshooting

• No path found immediately: check whether Start/Goal resolve to a walkable cell — a common cause is the marker part sitting on a wall edge, or GRID_PADDING being too small/large (see above).
• Grid scan reports 0 cells: the scan region has zero or negative size. Usually caused by Start/Goal being placed identically, or a very small GRID_PADDING relative to cell size.
• Path cuts through walls: confirm FLOOR_TOLERANCE in GridScanner.luau is smaller than your wall height, and that walls are tall enough to be hit by the initial downward raycast (very short walls under the tolerance won't be detected as walls, only as loose obstacles).