Topological Planning with Post-unique and Unary Actions

Guillaume Prévost, Stéphane Cardon, Tristan Cazenave, Christophe Guettier, Éric Jacopin

Introduction

In modern open-world video games, Non-Playable Characters (NPCs) utilize Goal-Oriented Action Planning (GOAP) to navigate complex behavioral requirements. Since its introduction in F.E.A.R. (2005), GOAP has predominantly relied on the A search algorithm. However, A suffers from exponential time complexity, creating a significant performance bottleneck. In high-performance engines where AI logic is often restricted to a 2ms window per frame, developers are forced to limit planning to only a few dozen NPCs, often relying on ad-hoc "tricks" that lack formal guarantees.

The SAS-PUC Formalism

To address this, the authors propose the SAS-PUC (Simplified Action Structure with Post-unique and Unary actions and Cycles) formalism. This framework codifies common practical constraints used by game developers into a rigorous mathematical model:

  1. Unariness (U): Each action modifies exactly one state variable.
  2. Post-uniqueness (P): For any given context, no two actions produce the same effect.
  3. Non-redundancy: Plans are assumed to be efficient, avoiding repeated actions for the same short-term goal.
Table 1: Action definitions for the Horse Breeder domain, illustrating pre-conditions, post-conditions, and prevail (prv) conditions.

As shown in the table above, actions are defined by their effects on state variables ($v_0, v_1, v_2$) and the conditions that must prevail during their execution. This structure allows the planner to avoid exhaustive search.

The TopoPlan Algorithm

By leveraging these constraints, the planning problem is transformed from a search-based exploration into a graph-based construction task. The TopoPlan algorithm operates in two primary phases:

  • Chain Building: The algorithm identifies the specific sequence of actions required to transition a state variable from its initial value to the target value.
  • Topological Sorting: These chains are then ordered based on their "prevail conditions"—dependencies where one action requires a specific state to be maintained (e.g., "holding a bucket" while "filling it").
Figure 1: The Domain-Action Graph for the Horse Breeder benchmark, showing the dependencies between actions like picking up buckets and feeding animals.

The resulting algorithm achieves linear time complexity $O(|A| + |E_A|)$, where $A$ is the action set and $E_A$ represents dependencies. This shift from exponential to linear complexity is critical for real-time scalability.

Evaluation and Results

The algorithm was evaluated using abstract benchmarks modeled after complex NPC behaviors in titles like Red Dead Redemption 2 (The Horse Breeder), Assassin’s Creed: Origins (Citizens), and Horizon Zero Dawn (Acquisition Machines).

The quantitative results demonstrate a massive leap in performance:

  • Throughput: TopoPlan generated over 3,000,000 plans per frame.
  • Latency: Total processing time was under 1.67ms on a consumer-grade CPU (AMD Ryzen 7 2700X).
  • Efficiency: This performance comfortably fits within the standard 10% AI budget for a 60 FPS game, even when simulating city-scale populations.

Conclusion and Future Work

TopoPlan provides a theoretical foundation for the "tricks" of game AI, proving that restricted planning domains can be solved with extreme efficiency. While the current model requires Post-uniqueness, which limits choices between multiple methods for the same goal (e.g., "unlocking" vs. "breaking" a door), future work aims to relax these constraints and integrate the system into commercial engines for massive-scale emergent crowd simulations.

Summary updated

Abstract

We are interested in realistic planning problems to model the behavior of Non-Playable Characters (NPCs) in video games. Search-based action planning, introduced by the game F.E.A.R. in 2005, has an exponential time complexity allowing to control only a dozen NPCs between two frames. A close study of the plans generated in first-person shooters shows that: (1) actions are unary, (2) actions are contextually post-unique and (3) there is no two instances of the same action in an NPC’s plan. By considering (1), (2) and (3) as restrictions, we introduce new classes of problems with the Simplified Action Structure formalism which indeed allow to model realistic problems and whose instances are solvable by a linear-time algorithm. We also experimentally show that our algorithm is capable of managing millions of NPCs per frame.
BibTeX
@inproceedings{prevost2023topological,
  author = {Guillaume Prévost and Stéphane Cardon and Tristan Cazenave and Christophe Guettier and Éric Jacopin},
  title = {{Topological Planning with Post-unique and Unary Actions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/603},
}
Figure