AStar

A* heuristic-guided shortest-path search.

A* finds the shortest weighted path from start to goal using a user-provided admissible heuristic to guide the search. By preferring vertices that appear geometrically (or otherwise) closer to the goal, A* typically expands far fewer vertices than Dijkstra while still guaranteeing an optimal result — provided the heuristic never overestimates the true cost.

Choosing a heuristic

Graph type	Good heuristic
2-D grid / world-space	Euclidean or Manhattan distance
Road network	Straight-line distance
Abstract graph	0 (degrades to Dijkstra)

Admissibility

The heuristic must be admissible — it must never return a value greater than the true cheapest cost to reach goal from vertex. An inadmissible heuristic can cause A* to return a suboptimal path.

All functions accept either callback form for GetNeighbors — see GraphUtil for details.

Example (grid pathfinding)

-- Each node is a Vector2 grid position.
-- Edge weight = 1 (uniform grid), heuristic = Manhattan distance.

local function getNeighbors(pos: Vector2): { Vector2 }
    local neighbors = {}
    for _, dir in { Vector2.new(1,0), Vector2.new(-1,0), Vector2.new(0,1), Vector2.new(0,-1) } do
        local next = pos + dir
        if not walls[next] then
            table.insert(neighbors, next)
        end
    end
    return neighbors
end

local function getWeight(_from: Vector2, _to: Vector2): number
    return 1
end

local function heuristic(v: Vector2, goal: Vector2): number
    return math.abs(v.X - goal.X) + math.abs(v.Y - goal.Y)
end

local result = AStar.shortestPath(
    Vector2.new(0, 0),
    Vector2.new(5, 5),
    getNeighbors,
    getWeight,
    heuristic
)

Functions

shortestPath

directedundirected

</>

AStar.shortestPath(

start: V,

goal: V,

getNeighbors: GetNeighbors<V>,

getWeight: GetWeight<V>,

heuristic: GetHeuristic<V>,

shouldStop: ShouldStop<V>?

) → PathResult<V>?

Finds the shortest weighted path from start to goal using A* search guided by heuristic. Returns a PathResult, or nil if goal is unreachable from start.

The heap is keyed on f-score = g(v) + h(v, goal) where g(v) is the known cheapest cost from start to v and h is the heuristic.

local result = AStar.shortestPath(start, goal, getNeighbors, getWeight, heuristic)
if result then
    print("Path cost:", result.cost)
    for _, v in result.path do print(v) end
end

Pass an optional ShouldStop predicate to abort a long-running search — it is checked once per expanded vertex (after the goal check, so a within-budget goal is never abandoned) and returning true makes the search stop and return nil:

-- Give up after half a second.
local deadline = os.clock() + 0.5
local result = AStar.shortestPath(start, goal, getNeighbors, getWeight, heuristic, function()
    return os.clock() > deadline
end)
-- result == nil if the deadline hit before the goal was reached

Time complexity: O((V + E) log V) in the worst case, but typically much better in practice due to heuristic pruning.