pathfinding
stableGrid-based pathfinding algorithms including A*, Dijkstra, BFS, JPS, Theta*, and hierarchical pathfinding, plus steering behaviours and utility functions for 2D game worlds.
use plugin pathfinding::{astar, dijkstra, bfs, …} Functions (14)
- astar A* shortest path on a 2D grid
- dijkstra Dijkstra shortest path on a 2D grid
- bfs Breadth-first shortest path on a 2D grid
- flow_field Direction vectors pointing toward a target
- distance_field BFS distance from every cell to target
- line_of_sight Bresenham ray-cast visibility check
- smooth_path Remove redundant collinear waypoints
- jps Jump Point Search optimised A*
- theta_star Any-angle Theta* pathfinding
- hierarchical_path Two-level HPA* with chunk abstraction
- flee Greedy path away from threat positions
- wander Biased random walk within a radius
- path_cost Total Euclidean length of a path table
- is_reachable Quick BFS connectivity check
Overview
pathfinding is a collection of grid-based navigation algorithms for 2D game
worlds. Every function operates on the same simple world model: a flat table
that represents a w-by-h grid, where the cell at column x, row y lives at
index y*w + x + 1 (tables are 1-based). A cell value of 0 means walkable and
any non-zero value means blocked. Coordinates passed to the functions are 0-based
(x, y) pairs, and the algorithms move in the four cardinal directions (JPS adds
the diagonals).
Path-returning functions all share one output shape: an ordered table of
{x, y} waypoint tables from start to goal, or an empty table when no path
exists. That uniformity means you can freely chain results — feed an astar
path into smooth_path, measure any path with path_cost, or swap one solver
for another without changing the calling code. Use the classic solvers
(astar, dijkstra, bfs) for single-agent routing, the field builders
(flow_field, distance_field) when many agents share one goal, the
any-angle and hierarchical solvers (theta_star, jps, hierarchical_path)
for smoother or large-map paths, and the steering helpers (flee, wander)
for reactive AI movement.
Common patterns
Find a route, then strip redundant waypoints and measure its length:
use plugin pathfinding::{astar, smooth_path, path_cost}
let grid = [0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
0, 1, 0, 0, 0,
0, 0, 0, 0, 0]
let path = astar(grid, 5, 5, 0, 0, 4, 4)
let trimmed = smooth_path(path)
print("waypoints {path.len} -> {trimmed.len}, length {path_cost(trimmed)}")
Check connectivity before paying for a full path:
use plugin pathfinding::{is_reachable, dijkstra}
let grid = [0, 0, 1, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 0, 0]
if is_reachable(grid, 5, 3, 0, 0, 4, 0) {
let path = dijkstra(grid, 5, 3, 0, 0, 4, 0)
print("reached goal in {path.len} steps")
} else {
print("goal is walled off")
}
Drive many agents toward one goal with a shared flow field:
use plugin pathfinding::{flow_field, distance_field}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let field = flow_field(grid, 5, 3, 4, 2)
let dist = distance_field(grid, 5, 3, 4, 2)
let here = field[1]
print("cell 0 steers ({here["x"]}, {here["y"]}), {dist[1]} steps from goal")
A* shortest path on a 2D grid
Finds the shortest path from (sx, sy) to (ex, ey) using A* with Manhattan heuristic. Returns an ordered table of {x, y} waypoints, or an empty table if no path exists.
use plugin pathfinding::{astar}
// 5x5 grid, all open
let grid = [0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
0, 1, 0, 0, 0,
0, 0, 0, 0, 0]
let path = astar(grid, 5, 5, 0, 0, 4, 4)
print("Steps: {path.len}")
When the goal is walled off, astar returns an empty table — check the length
before stepping along it:
use plugin pathfinding::{astar}
let grid = [0, 1, 0,
0, 1, 0,
0, 1, 0]
let path = astar(grid, 3, 3, 0, 0, 2, 0)
if path.len == 0 {
print("no route to the far side")
}
Dijkstra shortest path on a 2D grid
Finds the shortest path using Dijkstra's algorithm (uniform-cost, no heuristic). Guaranteed optimal on uniform-cost grids. Returns the same {x, y} waypoint format as astar.
use plugin pathfinding::{dijkstra}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 1, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 0, 0]
let path = dijkstra(grid, 5, 5, 0, 2, 4, 2)
print("Path length: {path.len}")
Breadth-first shortest path on a 2D grid
Finds the shortest path in terms of step count using breadth-first search. Faster than A* when the heuristic adds overhead, but explores more cells. Returns {x, y} waypoints.
use plugin pathfinding::{bfs}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let path = bfs(grid, 5, 3, 0, 0, 4, 2)
print("BFS path steps: {path.len}")
Direction vectors pointing toward a target
Builds a flow field: a per-cell direction vector pointing toward (target_x, target_y). Each entry is a {x, y} unit direction. Useful for moving many agents toward the same goal without per-agent pathfinding.
use plugin pathfinding::{flow_field}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let field = flow_field(grid, 5, 3, 4, 2)
let dir = field[1]
print("Cell 0 direction: {dir["x"]}, {dir["y"]}")
BFS distance from every cell to target
Computes the BFS distance from every walkable cell to (target_x, target_y). Returns a flat table of integers indexed by cell. Unreachable cells have value -1.
use plugin pathfinding::{distance_field}
let grid = [0, 0, 0, 1, 0,
0, 0, 0, 1, 0,
0, 0, 0, 0, 0]
let dist = distance_field(grid, 5, 3, 4, 0)
print("Distance at (0,0): {dist[1]}")
Bresenham ray-cast visibility check
Tests whether there is an unobstructed line between (x1, y1) and (x2, y2) using Bresenham's line algorithm. Returns true if all traversed cells are walkable.
use plugin pathfinding::{line_of_sight}
let grid = [0, 0, 0, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 0, 0]
let visible = line_of_sight(grid, 5, 3, 0, 1, 4, 1)
print("Can see: {visible}")
Use it to decide whether an AI can fire on a target before committing to a path:
use plugin pathfinding::{line_of_sight, astar}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
if line_of_sight(grid, 5, 3, 0, 0, 4, 2) {
print("clear shot")
} else {
let path = astar(grid, 5, 3, 0, 0, 4, 2)
print("must close in over {path.len} steps")
}
Remove redundant collinear waypoints
Removes collinear waypoints from a path table, keeping only direction-change points. Use after astar or bfs to reduce unnecessary waypoints for steering.
use plugin pathfinding::{astar, smooth_path}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let path = astar(grid, 5, 3, 0, 0, 4, 2)
let smooth = smooth_path(path)
print("Before: {path.len}, After: {smooth.len}")
Jump Point Search optimised A*
Jump Point Search — an optimised A* that skips symmetric path expansions for faster traversal on uniform-cost grids. Supports 8-directional movement. Returns {x, y} waypoints.
use plugin pathfinding::{jps}
let grid = [0, 0, 0, 0, 0,
0, 1, 1, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let path = jps(grid, 5, 4, 0, 0, 4, 3)
print("JPS path steps: {path.len}")
Any-angle Theta* pathfinding
Any-angle pathfinding that shortens paths by checking line-of-sight to grandparent nodes. Produces smoother, more natural paths than grid-constrained A*. Returns {x, y} waypoints.
use plugin pathfinding::{theta_star}
let grid = [0, 0, 0, 0, 0,
0, 0, 1, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 0, 0]
let path = theta_star(grid, 5, 4, 0, 0, 4, 3)
print("Theta* steps: {path.len}")
Two-level HPA* with chunk abstraction
Two-level hierarchical A* (HPA*): builds a chunk graph at chunk_size granularity, finds an abstract path, then refines each segment with full A*. Faster than flat A* on large open maps. Returns {x, y} waypoints.
use plugin pathfinding::{hierarchical_path}
let w = 20
let h = 20
let grid = []
// fill with 0s (walkable)
let path = hierarchical_path(grid, w, h, 0, 0, 19, 19, 4)
print("Hierarchical path steps: {path.len}")
Greedy path away from threat positions
Computes a greedy escape path from (sx, sy) that maximises distance from all threat positions. threats is a table of {x, y} positions. The path continues for up to max_dist steps. Returns {x, y} waypoints starting at (sx, sy).
use plugin pathfinding::{flee}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let threats = [#{"x": 0, "y": 0}]
let path = flee(grid, 5, 3, 4, 2, threats, 5)
print("Flee path steps: {path.len}")
Biased random walk within a radius
Performs a deterministic biased random walk from (sx, sy) for up to radius steps. bias_angle (degrees) steers the walk in a preferred direction. Returns {x, y} waypoints.
use plugin pathfinding::{wander}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let path = wander(grid, 5, 3, 2, 1, 45.0, 8)
print("Wander steps: {path.len}")
Total Euclidean length of a path table
Calculates the total Euclidean length of a path by summing distances between consecutive {x, y} waypoints. Works with any path returned by pathfinding functions.
use plugin pathfinding::{astar, path_cost}
let grid = [0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0]
let path = astar(grid, 5, 3, 0, 0, 4, 2)
let cost = path_cost(path)
print("Total path length: {cost}")
Compare two solvers by the real length of the paths they produce, not just the waypoint count:
use plugin pathfinding::{astar, theta_star, path_cost}
let grid = [0, 0, 0, 0, 0,
0, 0, 1, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 0, 0]
let a = astar(grid, 5, 4, 0, 0, 4, 3)
let t = theta_star(grid, 5, 4, 0, 0, 4, 3)
print("astar {path_cost(a)} vs theta* {path_cost(t)}")
Quick BFS connectivity check
Quickly tests whether (ex, ey) is reachable from (sx, sy) using BFS, without returning the full path. More efficient than running astar when you only need a yes/no answer.
use plugin pathfinding::{is_reachable}
let grid = [0, 0, 1, 0, 0,
0, 0, 1, 0, 0,
0, 0, 1, 0, 0]
let ok = is_reachable(grid, 5, 3, 0, 0, 4, 0)
print("Reachable: {ok}")