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 the Goal Oriented Action Planning (GOAP) or SHOP.

First consideration: this is not a technical problem

The first thing to know is that writing game AI is not a race for best technology, instead, it is just about chosing the right tool for serving the gameplay as good as possible. So, there is no urgency of chosing 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 perfectly challenging and it extremely straightforward. The important 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 solved by simpler reactive methods such as BTs or Finite-State Machines? In order to answer this question, you need to know the basic 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 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 instances, 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 this 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 in a certain situation. GOAP (and other plan-based AI technique), instead, works in a different way. 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, depending on the situation, it generates a different sequence of actions. Now, on paper, this is awesome. Why we are 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 on the AI. If we say that the character 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?

At 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 contents and it is impossible to predict during the development all the possible ways for the players to interact with my characters.

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 many ways to make huge BTs more manageable. This reduce the importance of motivation number 1. Number 2, instead, remains still a hot motivation for planning. We will talk more about this in the future, if you like.