Behavior Trees - Decision Making in Games!
Behavior Trees!
After doing a few of these game AI projects I find that it's not terribly hard to slap together an AI that has and performs a single behavior. The trouble seems to come in when you want the same AI to own and perform multiple behaviors, one after another. There are multiple structures/ways to do this but the one I want to talk about in this post involves Behavior Tress! It's a pretty common way of creating elaborate AIs in games and allows you to create separate behaviors that link together to create the illusion of an AI that's making decisions. I plan to split this post into three parts
- What is a behavior tree?
- How would I make a behavior tree?
- My implementation
I don't plan for this to be a step-by-step tutorial but rather a summary of what a behavior tree is and let that inspire you in terms of how to make one and what you could do with it. Ill also talk about some of the benefits of using behavior trees and what it could allow you to do when working with a team, so without further ado
What are Behavior Trees?
As the name implies a behavior tree uses a tree structure to store and transition between behaviors. If you don't know what a tree (the data structure) is then I would recommend watching a few youtube videos or taking a gander through a Wiki article or two because they can be immensely flexible and applied to all sorts of situations as you shall soon see. When it comes to behavior trees there are usually three different nodes that constantly pop up. They have a few names but I called mine check nodes, action nodes, and sequence nodes.
Checks
I like to think of a check node as a node where you would check to see if one or more conditions were true or false and use that to further split the tree into two or more behaviors. An example of a check could be something as simple as "Am I facing the player" or as elaborate as "is this a good situation for me to push in on the player's position?" depending on the result of the check you can move on to either more checks or an action.
 |
| Example of a check/conditional node |
The example above shows a node where depending on a true or false check it can result in the tree moving on to either action A or action B. but depending on the complexity of the check you can have it split into any number of nodes.
The example above shows a basic action that once completed will continue on to the next node after it.
There are tons of ways to execute a behavior tree so it all comes down to the use case. Good behavior trees should read like a choose your own adventure book and make sense at a glance, after all, you shouldn't need to be a programmer to design and understand them. A good behavior tree should be able to flow from behavior to behavior like it was a human making the decisions behind the scenes (because we are, it's just the AI performing the behaviors by our design).
The image above shows the initial design for my behavior tree. I wanted to have three different over-arching behaviors that had smaller behaviors within them. So I split the tree into an IDLE state (tank just patrolling around) an ALERT state (tank knows something is going down) and a FIGHTING state (tank was in combat). I think there is some merit to my initial design but I ended up snipping some parts since it was a little ambitious and other parts because they didn't make sense when you stepped back and looked at it. I also didn't really understand sequences when I designed it so they weren't used in the right way at all. Ill break this section into parts showing the current version of each state/behavior and a clip from the game, starting with idle.
This is a good example of the nodes I used where each one could potentially be interrupted depending on environmental factors in the game. I just listed "enemy spotted" in the chart but the actions could also be interrupted if the AI tank was shot. The "Follow Oldest Path" action would follow the oldest path it had visited unless it found a path it hadn't been to before, then it would go down that instead. It's a pretty simple behavior but it serves its purpose flawlessly
The movement of the tank is sort of slow but it's by design. In the video, you can see the tank as it reaches an invisible point I designated when I made the map and looks around. After it finds nothing it moves on to the follow oldest path action and goes down the invisible path on the right where it repeats the process from the idle entry point after it gets there. The real magic happens in the other behaviors, where the tank starts to show off some more character than just looking around.
This behavior looks like it was cut down a lot but it was really just shoved into the shoot action and some parts were placed elsewhere. It starts off by checking to see if the player's tank is still spotted which works by checking to see if it can see what I called target markers on the player's tank. If it can see the target markers then it can see the tank and returns true which takes it to the sequence where it will check to see if it's poorly angled to the player tank. Angles are a pretty big deal in tank games since in real life the angle a tank takes a shot at can really make a difference. The way I reflect this in my game is by having the AI tank try to optimize his angle in relation to the player (almost 45 degrees on front and sides) while finding the target marker on the player tank that gives him the best chance of penetrating the player's armor (the shot that is most square on). I placed a number of these target markers on the player's tank and the AI looks at each one and finds the angle a shot would hit at. After picking the "best" one it aims and shoots.
The image above shows a visualization of the penetration calculation. The blue line represents the angle the shot came from and the red angle shows the normal of the surface that was hit. since the normal is as square from a surface as you can get I used it to get the "perfect" penetration angle a 90 degree square on shot is a full 100% chance of doing damage while any angle beyond 50 degrees has little to no chance of doing damage.
Actions
An action node is where the "behaviors" of the behavior tree are stored. depending on how granular your tree is these actions can be pretty simple "move forward", "turn left", "look right" or more complex "hide from the player", "flank player position". The benefit of using simple nodes is that you can re-use them in different places while more complex ones are usually used in specific situations. In behavior trees you usually have the action performed to completion then it will move on to the next node in the tree. but you could hypothetically have an action node split into two different nodes if you need to. In my example/implementation, I have a few action nodes that can redirect the tree but I'll talk about that later.
 |
| An example of an action node |
The example above shows a basic action that once completed will continue on to the next node after it.
Sequences
Sequence nodes usually branch into a series of actions that need to be performed in a sequence. It's easy to understand why this is useful if you imagine something like an AI for a SWAT game where you might need to "Breach a Door" and then after it is finished breaching it will move on to a "Clear the Room" behavior and then maybe something like "Check for Hostages".
 |
| Example of a sequence node |
The example above shows a sequence node for stopping at a stop sign and would be performed from left to right, Once the car was stopped the AI could look both ways, and then when that is finished it would be able to continue driving.
With these three nodes alone you can make some pretty elaborate AIs in games. Some AAA studios will create Behavior Trees with hundreds of checks, actions, and sequences for things like NPCs you would just pass on the street, see for a few seconds and forget. But they make them this elaborate because the end product is something that can seem uncannily human. People don't always appreciate good AIs in games because when it works the AI becomes a part of the game world.
They shift from:
NPCs whose purpose is to fill in empty space
into
Characters or elements in a game world that flesh out space in between gameplay.
Similar to how side characters in books or background actors/extras in movies make the media they exist in seem more real, you just expect them to work and exist. Anyways back to behavior trees...
How do you make a Behavior Tree?
I would say that the first step to making a behavior tree is to think about the behaviors you want your AI to have. Things like walking around a park, looking for food, Stalking prey, Attacking a player, Running away, etc. After that, you need to decide how to switch/choose between these behaviors. This is where you would want to use some of the check/conditional nodes. An example could be "if hungry look for food, else walk around". This step is crucial because it connects the behaviors together and controls ultimately the flow of the tree, determining when each behavior is performed. Finally, you should think about each specific behavior, and how you could potentially break that behavior into specific actions. As I mentioned before it's nice if you can break the behavior into smaller/reusable pieces since large specific actions can't usually be used outside of the behavior it was designed for.
Another major part of behavior tree design that you might want to think about is how you want to traverse the tree. Some designs will always start evaluating the tree from the head/start node. This is nice for creating dynamic trees that can change behaviors pretty flexibly. The downside of this is the fact that a large tree can be potentially demanding to traverse if you have hundreds of branches to go down just to reach a leaf. Another method is to have a current node placeholder that remembers where it left off. this means that for each frame you can continue performing your action immediately and skip all of the checks that would take you there. The problem with this however is that you might have missed a vital check that would have changed the behavior/action you were performing. You can try to mix the methods by starting from a point in-between your action and the start but this isn't always an option. One solution I used was to have interruptable nodes that could at any moment start evaluating from one of three entry points that would lead to different behaviors.
 |
| An example of an interrupt/re-direct from an action node to another action node |
There are tons of ways to execute a behavior tree so it all comes down to the use case. Good behavior trees should read like a choose your own adventure book and make sense at a glance, after all, you shouldn't need to be a programmer to design and understand them. A good behavior tree should be able to flow from behavior to behavior like it was a human making the decisions behind the scenes (because we are, it's just the AI performing the behaviors by our design).
My Behavior Tree!
I decided to create a little Tank Game to implement a behavior tree for. I thought a tank game would be good since there are a few concepts in tank-to-tank combat that I thought could become good behaviors for my tree.
 |
| The initial design for my behavior tree |
The image above shows the initial design for my behavior tree. I wanted to have three different over-arching behaviors that had smaller behaviors within them. So I split the tree into an IDLE state (tank just patrolling around) an ALERT state (tank knows something is going down) and a FIGHTING state (tank was in combat). I think there is some merit to my initial design but I ended up snipping some parts since it was a little ambitious and other parts because they didn't make sense when you stepped back and looked at it. I also didn't really understand sequences when I designed it so they weren't used in the right way at all. Ill break this section into parts showing the current version of each state/behavior and a clip from the game, starting with idle.
Idle
This is the state that the AI tank would spend most of its time in (unless it's in combat a lot). I wanted this state to exists so the tank could wander around the map while looking for the player.
 |
| The final Idle behavior tree |
This is a good example of the nodes I used where each one could potentially be interrupted depending on environmental factors in the game. I just listed "enemy spotted" in the chart but the actions could also be interrupted if the AI tank was shot. The "Follow Oldest Path" action would follow the oldest path it had visited unless it found a path it hadn't been to before, then it would go down that instead. It's a pretty simple behavior but it serves its purpose flawlessly
The movement of the tank is sort of slow but it's by design. In the video, you can see the tank as it reaches an invisible point I designated when I made the map and looks around. After it finds nothing it moves on to the follow oldest path action and goes down the invisible path on the right where it repeats the process from the idle entry point after it gets there. The real magic happens in the other behaviors, where the tank starts to show off some more character than just looking around.
Alert!
This is the behavior the tank turns to when it's been shot, just barely lost sight of the player, or it knows the general direction the player was in. The behavior tree also used to redirect here when it spotted the player but I ended up changing that after I realized that it didn't make sense to divert here just so it could divert again, it added extra steps and complexity when it didn't need to.
 |
| The final Alert tree/behavior |
This behavior has an initial starting check that sees what type of alert brought it there. The options are either "GotShot", "EnemyNearby", "HaveClue". based on these the tree splits into three (sort of four) behaviors. Got shot triggers the tank to look in the direction it got shot from and if it doesn't spot the enemy then it re-enters the alert stage with a "HaveClue" alert since it knows the direction the shot came from. The Enemy Nearby alert happens when the player tank goes from spotted to not spotted, this triggers a check to see if the AI tank is healthy enough to pursue the last known location of the player's tank. If the AI tank either reaches the last known location or defends its location until a cooldown is over then it will re-enter the alert tree via the "HaveClue". And finally, the Have Clue behavior will move in the general direction of the player until a cooldown is over. If the cooldown ends without the tank spotting the player then it will enter the idle state.
This video shows off mainly the Enemy Nearby behavior where it moves to the last known location of the player in an attempt to find me (and it does). This clip is also nice because it also shows off just a bit of the fighting behavior as well. There is a part where it gets stuck on the wall for a moment but that is largely my fault for some poorly placed transport/movement markers (the barrel might have also gotten stuck on the scenery).
Fighting
This behavior is run whenever the enemy is spotted in the other behaviors and controls both defense and offense for the tank. This is also where a lot of the "cool" tech is hidden for both the combat system I made and the AIs thought process
 |
| The final Fighting tree/behavior |
This behavior looks like it was cut down a lot but it was really just shoved into the shoot action and some parts were placed elsewhere. It starts off by checking to see if the player's tank is still spotted which works by checking to see if it can see what I called target markers on the player's tank. If it can see the target markers then it can see the tank and returns true which takes it to the sequence where it will check to see if it's poorly angled to the player tank. Angles are a pretty big deal in tank games since in real life the angle a tank takes a shot at can really make a difference. The way I reflect this in my game is by having the AI tank try to optimize his angle in relation to the player (almost 45 degrees on front and sides) while finding the target marker on the player tank that gives him the best chance of penetrating the player's armor (the shot that is most square on). I placed a number of these target markers on the player's tank and the AI looks at each one and finds the angle a shot would hit at. After picking the "best" one it aims and shoots.
I hope it's evident in the video but when the player is spotted the tank does its checks and realizes that it's pretty square on in relation to the player so it shifts to a better position and then starts targeting various spots on my tank.
Each shot that is fired will fly until it either hits something or dies of old age (5 seconds). If the thing it hits is a tank then it will tell the tank's damage script where it hit and the angle it hit from. from there it does a short calculation to see if the shot would "penetrate" and deal damage.
 |
| Visualization of the hit calculation |
The image above shows a visualization of the penetration calculation. The blue line represents the angle the shot came from and the red angle shows the normal of the surface that was hit. since the normal is as square from a surface as you can get I used it to get the "perfect" penetration angle a 90 degree square on shot is a full 100% chance of doing damage while any angle beyond 50 degrees has little to no chance of doing damage.
The End
That's all I had to say about Behavior Trees. This was a pretty long post so I hope it got the concept across. Behavior Trees can be pretty powerful but just like some of the other methods, I talk about in my other blog posts it's not the ultimate solution to AI in games. There is a place and time for behavior trees, and they are pretty flexible so it might just be the case that you can use it quite often. Feel free to leave a comment below if you have any questions and ill try to respond or update the post if I find out anything new.
Until next time,
Written by Adam Currier
5/7/21
Comments
Post a Comment