Choosing between Behavior Tree and GOAP (Planning)

I would like to expand the answer I gave on /r/gamedesign some days ago. The main point of the question was: how can I decide if it “better” to implement the decision-making layer of our game AI with Behavior Trees (BTs) or with more advanced plan-based techniques such as Goal Oriented Action Planning (GOAP) or Simple Hierarchical Ordered Planner (SHOP).

First consideration: this is not a technical problem

The first thing to know is that writing game AI is not a race for the best technology. Instead, it is just about choosing the right tool for serving the gameplay as well as possible. So, there is no urgency to select the most advanced algorithm. You need to choose the simplest one that is good enough for your game. Remember Pac-Man. The AI of Pac-Man is still utterly challenging, and yet it is exceptionally straightforward.

The critical question you need to ask yourself, in this case, is: what is the problem that you want to solve? Then, you can ask yourself the real question: can this problem be solved using simpler, reactive methods such as BTs or Finite-State Machines? To answer this question, you need to know the fundamental differences between the two.

Behavior Trees vs. Planning

BTs, roughly speaking, are a fancy way to encode complex sequences of rules. A Bt acts as a sequence of programming statements (e.g., “if … then … else …") and basic loops. It takes as input the current state of the world and additional data (the blackboard) and return an action (or sequence of actions). For instance, rules can be like: “if your life is less than 40% then run away”, or “if do not have a weapon, go to the closest weapon,” and so on. If you want more info on BTs, there is this super-old introduction I did.

The main point here is that you are writing all these rules. BTs are “reactive” in the sense that they “react” to the state of the world. There is no search, no thought about the future outcome of specific actions. It is the developer’s job to specify which action is right within a particular situation. GOAP (and other plan-based AI techniques), instead, works differently. You give to the character a goal (expressed as a desired state of the world) and a set of actions (the things that the character can do), and then you say to the character “now find your own rules”. There is no predefined sequence of actions in GOAP. Every time you run the algorithm, it generates a different course of action depending on the situation. Now, on paper, this is awesome. Why are we still writing all the sequence of actions and rules by hand! Unfortunately, we pay such power with three main drawbacks:

  1. Much higher implementation complexity. BTs are quite easy to understand and to implement. Moreover, BTs are already built-in into a lot of game engines! GOAP, on the other hand, is not as simple. It harder to implement, and it is harder to debug.
  2. In general, plan-based techniques are computationally more expensive than BTs. Implementing GOAP in a way that is good enough for real-time games requires fine-tuning and a good design for the “state representation” and the set of possible actions (and we came back to point 1).
  3. By not writing the rules of AI by ourselves, we lose control of the AI. If we say that the character’s goal is to kill the player, we may have some situation in which the solution to this goal is too effective or, in general, not fun. Because fun is the goal, we need to change this, but we can only act on the goal, not the way the character reaches the goal. For another example, if the character starts doing something strange, it will be harder to understand “why”. In BTs, we can follow the tree and find the problem. In GOAP, this is much harder.

When to chose what?

In the end, you came here for an answer to the question: “when I need to prefer GOAP (or other planning) to BTs?”. As a rule of thumbs, BTs are usually enough 80% of your game AI necessity. To adopt GOAP, you really need some specific use case in mind that can not be solved in any other way. In general, there are two strong motivations:

  1. The number of possible action sequences, and the number of rules governing them, is too high. For instance, I can have too many different possible actions (or better, too many ways to combine these actions), and encoding all of them becomes a nightmare.
  2. You do not know at “design phase” the possible ways a character can act. For instance, your game may involve a lot of user-created content, and it may be impossible to predict how the player would interact with your characters during development.

Conclusion

This is a very high-level view of the problem, and it is nowhere complete. Things are more complicated and nuanced than that. For instance, there are many ways to make huge BTs more manageable. This reduces the importance of motivation number (1). The number (2), instead, remains still a hot motivation for planning. We will talk more about this in the future if you like.

Update (19 June 2020): I refreshed this page adding grammatical clarity and some other reference.

Header Image
GameDesign Math: RPG Level-based Progression

Level-based progression is an extremely popular way of providing the player with the feeling of “getting stronger.” The system is born with Role-Playing Games (RPG), but it is nowadays embedded in …

Read
Header Image
Playerunknown's Battlegrounds did everything wrong. And doing so, it won.

This small article is born from a discussion I had with a friend of mine this week. He was writing a review on Playersunknown’s Battlegrounds (from now on, PUBG) and he ended up talking about the …

Read
Header Image
Improve Inventory-Aware Pathfinding with Map Preprocessing

This article has been originally published on Gamasutra. In the last article we introduced a basic approach for Inventory-Aware Pathfinding (IAP), a pathfinding algorithm capable of interacting with …

Read
comments powered by Disqus