Planner algorithms
Why A* is the GOAP default, and where Dijkstra, Weighted A*, Anytime A*, D* Lite, IDA*, and HTN actually fit.
[ Deep Dive ]
Why A*, and what about the alternatives?
A tour of the search algorithms relevant to GOAP. Why A* is the field default, and where Dijkstra, Weighted A*, Anytime A*, D* Lite, IDA*, and HTN sit relative to the problem shape Intent Forge actually solves.
The search space
GOAP search is not over geometry. There's no map, no grid, no positions. It's over state space: each node is a complete world state (a set of fact values), and each edge is an applicable action (whose preconditions match the source state and whose effects produce the destination state). The goal is to find a sequence of edges from the current state to any state where the goal predicate evaluates to true.
This framing changes which algorithms apply.
Why heuristics work here
GOAP problems come with a natural admissible heuristic:
h(state) = number of unsatisfied goal facts × min single-action cost
It's admissible because every action satisfies at most some facts at
some cost — you can never reach the goal in fewer than
unsatisfied_facts × min_cost units of work. Stronger heuristics
exist; see Tighter heuristics below.
This single property is the entire reason A* dominates this space: a heuristic is always available. Algorithms that don't use one are strictly throwing away information.
A* — the default
A* expands frontier nodes in order of f = g + h, where g is the
cost-so-far and h is the heuristic estimate to the goal. With an
admissible heuristic, A* returns an optimal-cost plan and never
expands a node it shouldn't.
For GOAP-typical sizes (10–30 actions per archetype, plan depth ≤ 6, plan-cost variance < 10×), A* finds plans in microseconds. The performance benchmark shows planner cost is dominated by world-state read/write, not by search itself.
A* has been the GOAP default since Orkin's 2006 paper on F.E.A.R. established the framework. Twenty years and dozens of AAA shipping titles later, no one has produced a planning algorithm that's meaningfully better for the GOAP search shape.
Verdict: A* is what Intent Forge ships.
Dijkstra — strictly worse here
Dijkstra's algorithm is A* with h = 0. It expands nodes uniformly
in order of g only, with no goal bias. Without a heuristic, Dijkstra
explores the entire reachable state space outward from the start until
it stumbles into a goal-satisfying state.
When Dijkstra wins: when no admissible heuristic exists (GOAP always has one), or when shortest paths to all goals are needed simultaneously (GOAP only cares about one).
For GOAP: don't. Information is being thrown away.
Weighted A* — speed by giving up optimality
Weighted A* expands nodes in order of f = g + w·h where w > 1.
Inflating the heuristic biases the search more aggressively toward the
goal, finding plans faster but no longer guaranteed optimal. The
suboptimality bound is w (the returned plan is at most w times the
optimal cost).
When it wins: large action sets (100+ actions per archetype) where vanilla A*'s optimality preservation expands too many frontier nodes, or real-time constraints where a "good enough" plan now beats an optimal plan in 10 ms.
For GOAP at typical scale: archetypes have 10–30 actions and A*'s expansion count is small (< 50 nodes for plan depth ≤ 6). The weighted variant doesn't buy anything for that shape.
Anytime A* — return early, refine later
Anytime A* (ARA*, AWA*) returns a first plan quickly (suboptimal,
bounded by a weight w that decreases over time) and continues
improving the plan while the agent executes it. If the budget runs
out, the best plan found so far is what's returned.
This is genuinely interesting for GOAP because of the commit-time
floor semantics: the agent commits to an action for at least
MinActionCommitTime seconds, so the planner has that window to
refine. ARA* fits this shape naturally:
- First A* pass with
w = 2.0, return immediately → agent starts executing - Background refinement with
w = 1.5,w = 1.25,w = 1.0 - If a better plan is found before the commit floor expires, swap in atomically; otherwise stick with the first plan
At Intent Forge's targeted archetype sizes the synchronous A* path finishes inside the same window, so the anytime semantics don't pay back. They become relevant for projects with much larger action sets.
D* Lite — incremental search for changing environments
D* and D* Lite are designed for the case where the environment changes between searches and you don't want to redo the whole plan from scratch. They maintain the search tree as state and patch it incrementally when edges are added or removed.
Sounds perfect for GOAP — replan is the bread-and-butter operation — but two factors flip the verdict:
- GOAP plans are short. D* Lite's incremental machinery pays back when the search tree is large and edges change one at a time. At plan depth ≤ 6, replanning from scratch is microseconds. The overhead of maintaining the incremental data structures exceeds the savings.
- Replans coalesce. A burst of fact changes within one tick produces a single replan request, so A* doesn't run 100× per second per agent.
D* Lite would be the right pick for: a 50-step plan, one fact-flip per tick, where each replan must complete in a fraction of a millisecond. That's not the GOAP shape.
Verdict: solves a problem GOAP doesn't have.
IDA* — memory-bounded
IDA* (Iterative Deepening A*) does depth-limited A* with progressively-deeper limits, using O(depth) memory instead of O(states-expanded).
When it wins: very deep search trees where memory becomes the constraint (classic example: 15-puzzle).
For GOAP: plans are shallow. Memory is never the constraint.
HTN — a different paradigm
Hierarchical Task Network (HTN) planning isn't a variant of state- space search — it's a different planning paradigm. Instead of searching forward from a state, HTN decomposes high-level tasks into sub-tasks until everything is a primitive.
HTN gets its own page: HTN vs GOAP. Short version: HTN wins at AAA authoring scale (100+ behaviours per character, designer-controlled decomposition). GOAP wins at smaller authoring scale with emergent plans. Complementary paradigms, not competitors.
Tighter heuristics
A*'s performance is dominated by its heuristic. The default "unsatisfied facts" heuristic is admissible but loose. Tighter options:
- Per-fact cost lower bound — precompute the minimum-cost action
that can satisfy each goal fact;
h = sum of those boundsover unsatisfied facts. Tighter, still admissible. - Action landmarks — identify actions that must appear in any plan to the goal; their cost is a lower bound. Tightest known general-purpose admissible heuristic for STRIPS-style planning.
- Pattern Database (PDB) heuristics — precompute optimal plan costs for a subset of facts and use them as a lower bound. Used in competitive planning benchmarks; overkill for game-AI scale.
Intent Forge currently uses the simple unsatisfied-facts variant. Tightening the heuristic is a much bigger lever than swapping A* for another algorithm — if planner cost ever becomes a bottleneck, this is the first thing to tune.
References
- Orkin, J. (2006). Three states and a plan: the AI of F.E.A.R. GDC. — Foundational GOAP paper, A* on the action precondition graph.
- Jacopin, É. (2015). Optimizing Practical Planning for Game AI. Game AI Pro 2, Ch. 13. — Empirical analysis of planner cost including heuristic choice.
- Hart, P., Nilsson, N., Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE TSSC 4(2): 100–107. — Original A* paper.
- Likhachev, M., Gordon, G., Thrun, S. (2003). ARA*: Anytime A* with Provable Bounds on Sub-Optimality. NIPS. — Anytime A*.
- Koenig, S., Likhachev, M. (2005). Fast Replanning for Navigation in Unknown Terrain. IEEE Transactions on Robotics 21(3). — D* Lite.
- Russell, S., Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. — Textbook treatment of all of the above.
See the consolidated References page for the full annotated bibliography.