Planification dans les jeux-vidéos : À quoi servent les coûts des actions ?

Guillaume Prévost, Stéphane Cardon, Tristan Cazenave, Eric JacopinRJCIA 2019 · OpenReview

TL;DR

This paper investigates the role of action costs in the Goal-Oriented Action Planning (G.O.A.P.) system used for non-player character (NPC) control in video games like F.E.A.R. The authors found that action costs have a surprisingly small impact on the planning process and NPC behavior in practice, suggesting that other mechanisms within the G.O.A.P. framework are more influential.

What Problem Does This Paper Address?

In real-time video games, controlling non-player characters (NPCs) effectively is crucial for creating immersive and challenging experiences. A common approach is to use planning systems that allow NPCs to dynamically decide on sequences of actions to achieve their goals. The Goal-Oriented Action Planning (G.O.A.P.) system, a popular choice, relies on actions with preconditions, effects, and crucially, costs. These costs are intended to guide the planner towards more desirable action sequences. However, the authors question the actual utility of these costs in practice, particularly within the context of a fast-paced video game like F.E.A.R., where planning must occur in real-time. They aim to understand why and if these costs truly influence the planning outcome.

Methods

The researchers instrumented the planning activity within the video game F.E.A.R. to analyze how the G.O.A.P. planner utilizes action costs. They conducted experiments by comparing two configurations: one using the game's original action costs and another where all action costs were set to a uniform value of 1. This allowed them to directly observe the impact of cost variations on the generated plans. They analyzed the generated plans, their lengths, their probabilities of appearance, and the time taken for planning.

Datasets

The study used data generated from gameplay sessions of F.E.A.R. The "dataset" consists of the sequences of plans generated by the G.O.A.P. system during these sessions under two different cost configurations. No new benchmark datasets were introduced.

Key Insights and Ideas

  • Action costs are surprisingly ineffective: The core finding is that varying action costs has a minimal impact on the plans generated by the G.O.A.P. system in F.E.A.R. This challenges the intuitive assumption that costs are a primary driver of planning decisions.
  • Short plans dominate: The vast majority of successful plans consist of only one or two actions. This brevity limits the opportunities for the A* search algorithm (used by G.O.A.P.) to explore complex action sequences where costs would typically play a more significant role.
  • Contextual filtering is more powerful: The G.O.A.P. system in F.E.A.R. employs strong pre-filtering mechanisms based on action effects (postconditions) and NPC memory/sensors. These contextual filters effectively prune the search space before action costs become a major factor, rendering the costs less influential.
  • A*'s potential is underutilized: While G.O.A.P. uses A* for planning, the short plan lengths and aggressive filtering mean that A* rarely needs to explore deeply enough for cost differences to significantly alter the chosen path.

Key Results

  • Plan diversity is minimal: Only a 5.14% difference in plan diversity was observed between the original cost configuration and the uniform cost configuration.
  • Plan content is largely the same: 94.86% of plans generated with uniform costs were also generated with original costs, indicating significant overlap.
  • Failure rates are high: A significant portion of planning attempts resulted in failure (around 74-77%), meaning the planner couldn't find a valid plan to achieve a goal. This suggests that even with costs, achieving goals is not always straightforward.
  • Planning time is unaffected: Changing action costs had no discernible impact on the time taken to generate a plan, which remained in the order of tens of microseconds.

Limitations and Future Work

The authors acknowledge that their findings are specific to the G.O.A.P. implementation in F.E.A.R. and the observed plan lengths. They suggest that in games with more complex goals or longer action sequences, action costs might indeed play a more significant role. Future work could explore how to design action costs more effectively to influence NPC behavior in scenarios where they are more impactful, or investigate alternative mechanisms for guiding planning beyond simple cost assignments. The paper also notes that the specific implementation of A* and the filtering mechanisms are key to understanding these results.

Summary updated

Abstract

en fr This paper suggests a reflection on the costs of the actions used by the planner G.O.A.P. (Goal-Oriented Action Planning) which is used in some video games like F.E.A.R. to have real-time control of the non-playable character. We have analysed the planning activity of F.E.A.R. to study the utility of the costs in the planner. We show and explain why they have little impact in practice. Nous discutons de l’intérêt des coûts des actions dans le planificateur G.O.A.P. (Goal-Oriented Action Planning), qui est utilisé pour le contrôle en temps-réel des personnages non-joueurs dans certains jeux-vidéos. Nous avons instrumenté l’activité de planification du jeu vidéo F.E.A.R. afin d’étudier l’usage des coûts des actions par le planificateur. Nous montrons et nous expliquons pourquoi leur impact est faible en pratique.
BibTeX
@inproceedings{prevost2019planification,
  author = {Guillaume Prévost and Stéphane Cardon and Tristan Cazenave and Eric Jacopin},
  title = {{Planification dans les jeux-vidéos : À quoi servent les coûts des actions ?}},
  booktitle = {RJCIA},
  year = {2019},
  url = {https://openreview.net/forum?id=78lKaJRInJ},
}

Loading related content...

Figure