Design Tool: Designing an AI Decision Tree

Artificial intelligence and enemy design have been quite the topic here on GDKeys: we covered the high-level design part, discussing the rational justification of each enemy in our games (with the one-pager to go with it), as well as the keys to make our enemies believable. Then we dived into the micro, with the anatomy of an attack and moment-to-moment gameplay.

But there is one topic that we stayed clear from, until today: the implementation of an AI agent in our games, and the necessary technical design that connects the theory to the reality of our playable enemies.

How do we implement an AI, in an engine, for it to fulfill all of our crazy paper plans? How do we make an enemy behave logically? In short: how do we create and implement AI intelligence?

AI implementation has been a burning topic in the industry for the last decades: it made games enter the Pantheon of video games, created highly specialized positions, like AI designer, and is reaching far beyond our industry (we have rovers on Mars that are running using the very methods we will discuss today!).

This is also an extremely complex, and pricey, topic: AAA teams usually have full-strike teams working for years on their AI in order to bring us the enemies we are all used to play against. This brings us to this article’s purpose: what is the most straightforward, versatile, debug-friendly, and designer-friendly way to design and implement AI in our games?

In this article, we will focus on the decision tree approach, a philosophy that is still used today by AAA teams to create amazing AI agents, and yet that is accessible enough for anyone to implement relatively easily on their own games.

Here is the plan for this article:

Frame our topic and identify the strengths and weaknesses of Decision Trees compared to different approaches.
Design an enemy from scratch, using a human-friendly visualization, as well as going through each necessary creation step to ensure a clean design and enemy.
Finish with a ready-to-use design tool for you to leave with.

This is a tough topic to tackle, but if all goes well it should be a lot less scary in no time! Let’s dive in.

The Many Forms of AI

To begin, we need to realize that there is a multitude of approaches when it comes to creating an AI, each of them with its own advantages and disadvantages.

Historically, AI was created the same way we have been automating other industries before: with Finite State Machine (FSM). In essence, every behavior and action of an enemy was coded as a state, which would transition to another one following some conditions (spot the player, run out of ammo, timer, being shot at, die, etc.).

This approach is robust and easy to implement, which is probably why it is still used today for simple system automation. Here is what an FSM would look for in a Pacman Ghost:

Pretty straightforward! The main catch with FSM is that it, unfortunately, tends to get extremely dense and confusing. Trying to code, improve on, and debug enemies as complex as the ones we find in games today can easily become impossible as their FSM will become a monstrosity of hundreds of interconnected states and rebounds.

Another approach then appeared: behavior/decision tree (there is a technical evaluation difference between the 2 but can be roughly approached the same way for the sake of this article). This approach is very straightforward: every frame, the game will run the decision tree of an AI agent. This tree is composed of a root, branching into layers of nodes, like selectors, and always reaches a child/leaf which represents every action this agent can perform.

Here is the decision tree of the original Quake enemies (Inputs: D = dead, E = enemy spotted, L = low on life, S = sound heard):

Decision trees have been used for decades in the industry and are still very relevant today. They are the approach that brings implementation the closest to the design, are extremely easy to debug and improve upon, and are pretty efficient in terms of resources.

The main criticism about decision trees relates to the “fake” intelligence it provides: just like an FSM, an enemy will never swerve from its decision tree even if a truly intelligent creature would have used every opportunity at its disposal.

Enters the advanced AI approaches!

The first one we will discuss is called GOAP, for Goal-Oriented Action Planning. This approach has been heavily theorized by Jeff Orkin and applied to his game F.E.A.R, which received critical acclaim for its enemies’ behaviors.

In short, enemies using GOAP are going to make their own decisions based on the actions at their disposal, the state of the world, and the goal they are trying to accomplish… Pretty crazy, right?

F.E.A.R was the first game using the GOAP approach

To do that, the game will continuously feed AI agents with a goal, as well as with the current state of the world. The agent GOAP Planner will then run every possible chain of actions said agent can accomplish and assign costs to each of these chains. It will finally select the optimal sequence of actions to fulfill the goal and act on them!

Let’s imagine, for example, that our agent has the goal of “get wood”. One of its actions is to “Collect branches” which would definitely fulfill the goal. The agent planner decides to assign a cost of 10 to this action (weighting the time and energy necessary to carry the task to completion). But another of its actions would also fulfill this goal, “Cut Tree”, which is a way more efficient solution! That action gets a cost of 4 by the Planner. The problem is that to cut a tree, the agent needs an ax. “Purchasing an ax from the market” is another action that our agent can perform, this time getting a cost of 5 (again, weighing in the time, money cost, and energy involved).

Once our agent has run all the possible scenarios, it is finally left with 2 scenarios:

“Collect branches”. Cost = 10
“Purchase an ax” + “Cut down a tree”. Cost = 5 +4 = 9

This time, our agent will decide on the ax scenario. If he didn’t have enough money for the ax (and thus should have found a way to get enough money first), the cost would have probably gone above the simple “Collect Branch”.

Also, since our agent now has an ax, but also one less tree, the cost calculation the next time it will need to collect wood will be entirely different. And this is the beauty of this approach: AI agents will adapt to the world, and react accordingly in the most efficient and logical way. It can lead enemies to make fabulous tactical decisions in accordance with a world state they are just discovering every frame.

So why isn’t every game running with this approach then? Well, first of all, because it’s extremely costly in resources. But also, this approach is hell to work with and debug: imagine a gigantic state machine but without any link between states, where the AI itself takes care of bouncing between these states as it pleases.

Then we could push the discussion even further and talk about Utility AI, abstracting, even more, the path to a goal by measuring its performance towards it, which is a phenomenal AI approach for strategy games with long-term victory conditions and a huge number of agents. And how about Neural Networks?

But we are opening too many doors…

My Approach

AI is a fascinating topic, but when it comes to our games we need to be realistic. Very few of us will ever have the need to implement a fully-fledged GOAP system and go for the cost and extra time and resources needed to polish it properly. And even if we could… Would it benefit our games?

And this is a very important question to discuss: there is a belief that “more intelligent AI = better games” which couldn’t be further from the truth! Most games will better benefit predictable, pattern-oriented enemies, some will even shine with sequenced enemies, repeating their actions without even a speck of AI behind it. Finally, some rare cases will really gain from having a state-of-the-art AI, like the amazing work that has been done on Alien: Isolation.

Having worked with all these systems on different games over the years, I came to the conclusion that most action games are best suited with a combination of 2 elements for their AI:

A high-level state machine, dealing with the key behaviors of our enemy,
A decision tree per state of the state machine.

It’s designer-friendly, very understandable even for non-initiated, easy to improve upon and debug, cheap in resources, and can be extremely efficient in displaying intelligence if properly designed: games like The Division 2, or the fact that at its core, the Xenomorph is driven by a decision tree are proof of it.

The bonus part? Unity and Unreal have all the tools to implement this approach with minimal work.

So let’s give it a shot, and design together, step-by-step, the AI of a basic enemy for a random action-adventure game!

Designing an Enemy

For the sake of this exercise, we will design the AI of a pretty basic enemy, let’s call it the Bandit, that will be a grunt enemy in our third-person action-adventure game.

His high-level behavior will be fairly classic: he will be placed in our fighting zones (camps, VIP locations, arenas…) and if undisturbed will just idle around. If he notices something suspicious he will go investigate and, of course, will attack the player on sight.

Our Bandit will have a dagger for melee combat, a gun for mid-range, and that’s pretty much it. So… where do we start?

0. High-Level State Machine

I personally prefer not to keep the entire logic of my enemies in a single decision tree: they become bulky, run excessively long logic sequences, and become a pain to work with (the picture above represents only a third of the Xenomorph decision tree for example).

For this reason, I like to have a state machine at the root of my enemies’ AI, breaking their behavior into a multitude of small decision trees: one per state.

For our Bandit, this FSM would simply contain 3 states

Idle State: his undisturbed state. Also, the one he will spawn into.
Combat State: the core purpose of our enemy.
Investigation State: to ease the transition between the 2 previous states in a believable way, as well as bring a light stealth aspect to our game.

Once each stage is defined, we can now finish this FSM with every transition between them:

Full FSM, with transitions between states

Our full FSM will be extremely simple:

While in Idle, our Bandit will attack the player on sight, but will also investigate weird noises.
While investigating, if 10 seconds pass without spotting the player, the enemy will go back to idle. “Must have been the rats!”.
Finally, while in combat, if the Bandit loses sight of the player, and the player is more than 10 meters from him, he will enter an investigation (this is very rudimentary but will do the job for now).

This is a pretty good start! We can now finally enter the crunchy part of the AI: the different decision trees! Today, we will focus on a particular one, the combat state decision tree, but the other two would follow the same logic.

1. Combat State Decision Tree: The Core

Let’s start by talking a bit about what is a decision tree.

In broad terms, decision trees are a succession of nodes, on multiple branches, starting from a root node and ending on a leaf node (the actions). To reach one of the leaves, the algorithm will pass through a series of gates and conditions, branching every time.

A decision tree will always run top-to-bottom (or left to right depending on the directions you take it): every time a condition (the parent node) is reached, the algorithm will assess every one of its child nodes one by one. If the first condition of a child node isn’t answered, the tree will move to the second child, and so on until it finds a suitable one.

For easier reading, I will represent the actual flow of decisions in the tree in the rest of this article. This isn’t how it is typically represented but will ease our discussions (I will show you both representations at the end).

So, let’s put our first blocks together!

Our Root node will be the entry point of the Combat State.

Now we need to put our first conditions. Where do we even start? Well, I personally advise going to the root of the enemy: what will be its main decision parameters? Or, in other words, what is the primary parameter that will make it decide between different actions? This is a very important question!

For our Bandit, as well as most enemies you will encounter in action-adventure games, the answer is distance: “I am far away from the player, there is no use for my dagger and I should use my gun!”. But it may be different: mages could first make decisions based on their spells’ cooldowns, shapeshifters could make them based on their current form,and enemies in a musical-inspired game could make them based on rhythm… There are a lot of possible answers!

Now that we have our core decision parameter, let’s create our first meta conditions: we are laying down the big categories of behaviors of our enemy, the broad strokes. Our bandit will have 3:

Is the player out of range (then it can’t attack)?
Is the player in long-range (and thus in range for its gun but not its dagger)?
Is the player in melee range (in range for both, but mainly for the dagger)?

Once again, every enemy for every game will have a different set of conditions: think them through carefully, and slap some rough values on them (we will polish them later).

With distance used for my core conditions, I took the habit of ordering them from furthest to closest from the player: in this case, the order wouldn’t matter, but we may end up with overlapping conditions and it usually works better this way (and is easier to read in my opinion).

2. Decision Tree Core Leaves

Now that our core conditions are in place, let’s attach actions to each of them, and give the first proper combat behavior to our Bandit:

The actions will stay very straightforward for now: we are slowly chiseling away and shaping our enemies: let’s not get carried away in details that may confuse us.

Player out of range: our Bandit can’t attack and thus will navigate towards the player (run, bounce, whatever your action is).
Player in long-range: it will use its gun for a single-shot action.
Player in melee range: it will use its dagger slash (a base dagger attack).

And look at us: we already have a fully functioning enemy! Simple, sure, but it could definitely work as-is. Now a little advice: test it! Each step of our designs needs to be self-contained and testable, and this is the perfect moment to spot problems and refine our condition values.

Also, you may have noted the shape differences of my leaves (dotted lines and solid ones). This is a habit I took to help me read my designs more easily: solid lines represent the combat actions, dotted ones the fluff, repositioning, navigation, etc.

But we have a lot more expectations for our enemy (and killer animators that need work), so let’s densify this behavior a bit.

3. Variety and Random

Let’s face it: an enemy doing the exact same actions in the exact same circumstances will feel gamey and robotic. This could be a great thing if we are actually designing robots (cf. the enemy believability article) but our Bandit is human and should thus behave like one.

Not only that, but we may create terrible game situations! Let’s take an example: 4 Bandits spot me from afar (out of reach): they will all start running towards me, stop at the exact same distance (long-range), and all shoot at me at the same time. Not very immersive…

This is actually a situation where GOAP would shine by letting each enemy weigh its own actions independently (and this could be done with a simple ticketing system too!) But this doesn’t mean that we can’t fake it with our decision tree! Let’s bring random into play.

The idea is simple: for each condition met, our Bandit will roll a dice to decide between different actions:

When the player is out of reach, the Bandit will either run toward (75%) or taunt the player without changing position (25%).
When the player is in long-range, he will either keep running towards (50%) or take a shot with his gun (50%)

Let’s reassess our previous situation with these additions: out of our 4 enemies, on average 1 will taunt the player while 3 of them start running towards the player. arriving in long-range, half of them will take a shot while the other half will close the gap and engage the player in melee.

This feels a lot better already! And now it’s time to test again, with different situations, numbers, and positions of enemies, player inputs or not (what happens if you don’t touch any button? You can easily see AI flaws without the chaos that the player brings in the system).

This is also an important point: it may still sound artificial (every enemy stopping at the same distance from the player to take a shot for example), but the player is going to be our best ally here: the player is always in movement, always creating chaos and varying situations. This will create a very organic battlefield, even with seemingly artificial conditions.

Now let’s take care of our melee range.

4. Sequences and Combos

Having an enemy in melee range (thus really visible on screen) repeating the same attack can quickly feel odd and unnatural. This time we’ll try something else than using random branching: combos. And this is as easy as chaining leaf nodes.

Here is what our Bandit will now do when closing on the player:

He will start with the dagger slash we had before (called now the Dagger Slash Right, we’ll assume he is a righty).
Then he will come back to his original position with the mirror action (the Dagger Slash Left).
Finally, he will extend and stab the player.

This sounds like a pretty sound succession of attacks: each attack uses the energy from the previous one, and they flow nicely together… But discussing it would be a topic for our Anatomy of an Attack article.

Now you may rightfully wonder why do we go with the struggle of creating 3 different nodes, thus 3 different actions, when we could simply create a simple action called “Dagger Combo”. The answer is control.

5. Abort Conditions

If we had all our attacks packed in a single action, then they would all play out exactly as expected all the time. But breaking them into different nodes will allow us to gain multiple opportunities as we will see. Another strong argument to make is that each of these bricks can be reused separately at different moments of the experience, for different attacks later on.

In our case, we will try and avoid the situation that many games suffer from, where an enemy starts a combo, but the player moves away and can now watch the enemy trying to land attack after attack while it’s evident they are just embarrassing themselves. Not very smart.

To do that, we will add an extra condition that will check if a hit has landed: if positive, then the combo continues. If negative, then our Bandit will “realize” that he isn’t hitting the player and will abort the combo.

I decided not to put an abort condition between the first 2 attacks as I believe they will flow in a continuous motion (going back to the idle position).

Abort conditions are probably the most common use of this split approach, but there are others: we could bring some random in it to create multiple combos at little cost or check where the player is after the first 2 hits to chain into different stabs (direct stab, 180+stab, jump+stab, etc.).

Let’s clean our decision tree by grouping this combo into its own little tree: it may seem useless here, but as combos often get dense and convoluted this helps keep the core tree readable:

Decision trees can be linked to others, for legibility and organization

We have a strong AI base, but it is now time to consider what could go wrong with it, and plan against it.

6. Core Extremes

Our Bandit core is based on distance conditions, and we already tackled the gameplay ones. But we are missing some scenarios, like the extremes of the system.

In our case, the first extreme will be the Target Unreachable state. It may happen that our Bandit won’t be able to find any pathfinding route toward the player (having the player on top of a cliff for example). In this case, we will need an emergency solution that won’t involve our enemy trying to reach the player: we will reuse our “Gun Single Shot” attack (even if the player is not in range, it makes sense that our Bandit will try nonetheless), and an occasional taunt specific for the situation, like “Get down there, you coward!”. This will prove that our enemy is very aware of the situation unfolding and his inability to act.

Note: unreachable conditions can vary widely from one game to another. This solution is given as an example but your own game may have a very different approach.

The second extreme is actually a realization and gameplay one: our dagger combo has a condition “player less than 4 meters away”. But having the player too close to the enemy will make the combo look glitchy (or straight-up passing through the player). So we will add a fourth distance condition, making our Bandit jump back when too close to the player. This should position him at the proper distance for our Dagger Combo!

We are now covering all basic situations and the full range of our core (distance): our enemy should behave fairly well. After another round of testing to confirm it, we can now start looking into the secondary conditions driving our AI.

7. Situational Conditions and Sequences

What interests us here is all the unique situations, happening outside our enemy, that could make him look stupid, and plan against them. In our mock game, let’s assume 2 situations:

The player can block attacks (classic unlimited block with reduced mobility).
After taking a strong hit, the player can be thrown on the ground (a disabled state with a button press to go back up).

These 2 possibilities are dangerous for our Bandit: his Dagger combo may look inefficient against a player blocking all attacks (and players would expect him to think around that), but will sure look ridiculous if the player is lying on the ground with the enemy doing all kind of inefficient flourishes above them.

Not only that, but gameplay-wise we want the game to push the players to react fast and vary gameplay approaches on the flight: we need to have enemies breaking the player’s guard and emphasizing that being on the ground is an extremely dangerous situation.

We are then going to add 2 actions to our Bandit AI: a kick that will break the player’s block (and allow the Bandit to properly start his Dagger Combo next), and a Dagger Finisher: a very deadly attack that will punish players ending up on the ground for too long.

Remember that decision trees run sequentially: our unique conditions must be checked every time before the common ones, and thus our Dagger Combo will end up at the bottom of this branch.

8. Security Leaf

Our enemy seems pretty solid for now and it seems like we are covering all the possible situations he may find himself in, but we may have overlooked a few extreme cases and thus will always need to add a security leaf: the extreme bottom of our decision tree, the action that will run when nothing else can.

You may tell me: “If he can’t do anything he will just do nothing, what’s the big deal?”. Well, there are 2 dangers here actually: the first one is that we may not notice that there is a problem with our enemy (and we will keep trying to solve why our enemy isn’t aggressive enough). The other is that it may add chaos to our enemy’s pacing.

Not only it is very helpful to add this leaf, but it is also good practice to never leave a condition floating without a leaf for every output.

I personally like to throw my taunts there: they are the least impacting actions of my enemies (no navigation nor player interaction) and are extremely visible: if I see my bandits taunting constantly out of the blue, I’ll immediately know there is a problem in their AI.

Almost there! We have but one last thing to take care of.

9. Priority Conditions and Sequences

In step 7, we talked about having our enemy react to situational conditions (player on the ground, player positioned behind him, player aiming at the enemy, obstacle obscuring his FoV, etc.) but we may want the enemy to have some extra conditions: conditions that should take-over everything else.

For our Bandit, we will imagine 2 conditions:

Let’s say our Bandit can be stunned (smoke bomb, dirt thrown in his eyes, headshot maybe?): we will make him enter a Shooting Frenzy, an action where he will cover his eyes with his left arm while emptying his magazine shooting in random directions.
We will go a bit over-the-top and create a Raging state when our Bandit’s HP falls below 20%. For this example, I made it branch to another completely different decision tree dedicated to this Raging state (that we won’t deal with today), making this moment one of the pillars of our Bandit (and inviting the player to finish off enemies fast).

As you can see, these conditions are very meta (can happen at all times and distances) and thus will be placed at the very top of our tree: at every tick, our decision tree will first ensure that the Bandit has more than 20% HP and isn’t stunned, then it will check that the player is reachable, then finally it will start running his core conditions.

Quite a lot of priority conditions can be added here: every gameplay’s unique states, strong hurt reactions, etc.

10. Final Decision Tree

Finally, after all these steps, here is our final Bandit decision tree (minus the Raging state):

This tree should very much be tested, polished, and iterated, but it holds together and should look smart and consistent in all scenarios. The next steps for me would be to polish the unreachable state and playtest a lot of this enemy to see how the random conditions hold (are the probabilities feeling right? Should I add more possibilities? Less? This can only be judged pad in hand in the end).

Our Bandit is quite expensive too, with its 10 unique actions, not counting the Raging state (definitely a AAA enemy budget, or a very important enemy in a more modest game). This could definitely be scoped down if need be.

At the start of this article, I mentioned that I would represent all the decision flow for easier reading. Since our decision trees will always run the exact same top-bottom way, I actually represent my decision trees in this format:

This is the exact same decision tree, but in my opinion, it’s a lot more convenient to work with and really represents how it will be coded in the engine (branches and leaves clearly identified). I leave it up to you to find the best format to work with.

Tool: Visio Decision Tree

Personally, I find it invaluable to have this paper design of my AIs before implementing anything. It ensures that I thought my enemy through beforehand, gives me a visual, legible representation of its brain, and really accompanies me in its different iterations and polish.

If you liked the approach I developed here and want to give it a try yourself, I prepared a Visio template for you to use, with the final decision tree of our Bandit in both formats, as well as the legend of my blocks.

You can access it here:

Exercise

If you want something to practice on, why not design our bandit-raging state? Let’s make it interesting: this state will only get a single new action, a signature move. The rest will have to be made of re-use from the normal Combat state (then bring a snapshot of it on our Discord!).

Conclusion

There would be so much more to cover when it comes to AI… A decision tree is but one of the bricks that will make an enemy behave smartly: pacing, group AI, animation inverse kinematics (look-at), animations themselves, etc. Like every topic with games, the suspension of disbelief will be kept in place by a multitude of different elements.

Whatever AI implementation approach you decide to go with, the search for smarter enemies (but not too smart or the gameplay falls apart) will never stop, and technology alone will only get you so far.

Advanced enemies are among the most difficult game design challenges, and are often botched: implementing it well will instantly put you above the vast majority of games and will surely become a stamp of quality for your games (even if it isn’t noticed directly by players). It feeds the game’s fantasy, makes the gameplay shine, and gives a soul to games.

Now go make fake brains!

To Continue Beyond

Should you want to continue beyond this article, here are excellent resources:

An introduction to Behavior Trees by the excellent AI in Games channel

Behaviour Trees: The Cornerstone of Modern Game AI

Because GOAP is a fascinating topic (even though I usually advise against using it, it can be a pretty amazing tool to use on the right game):

Building the AI of F.E.A.R. with Goal Oriented Action Planning

To continue on GOAP, here is the site of Jeff Orkins, the father of the approach, filled with excellent resources:
http://alumni.media.mit.edu/~jorkin/goap.html

And a last article on GOAP, more code-oriented this time:
https://gamedevelopment.tutsplus.com/tutorials/goal-oriented-action-planning-for-a-smarter-ai–cms-20793

Finally, let’s open the discussion with an excellent article from Nikki Zee that approaches the topic of enemy AI from a different lens and really analyzes the various forms of AI and their pros and cons (FSM, utility AI, behavior trees, etc.):
https://nikkizee.com/ai-decisionmaking

Did you enjoy this article? If so, please consider supporting GDKeys on Patreon. It helps keep this place free of ads and paywalls, ensures we can keep delivering high-quality content, and gives you access to our private Discord where designers worldwide gather to discuss design and help each other on their projects.