Overview
So it has been a while since my last post, but since then I have been busy learning lots of details about behavior trees, HTN planning (or Hierarchical Task Network), and coming up with my own architecture modeled after these systems. Since then I have implemented behavior trees a few times and done extensive research on HTN planning based mostly off of Dana Nau's SHOP HTN techniques, so if you more interested and didn't find all the information you are looking for here go check out SHOP or SHOP 2 there are articles and pdfs around if you google it. Everything I will be explaining is about behavior trees and HTNs at the moment I will write about my new architecture when I finish it as my research project because I will have a better understanding of it's successes or failures by then.The Basics
To start off a basic understanding of behavior trees is needed to understand both behavior trees (obviously...) but also HTN's as well because they are very similar. So assuming you know what a tree is there are 3 types of nodes required to get a behavior tree up and running which are Composite (or I call them action nodes I'll explain why in a minute), sequence, and selector nodes. These are the 3 most commonly used nodes and they are really all you need, but there are things like decorators, parallel, or other variants of the any of the above nodes that are just added specializations to the basic tree. I like to call composite nodes action nodes because they typically hold the logic for performing the behaviors in the tree thus performing action and makes the name more explicit.
Action Nodes (Composites)
These nodes will be what holds the logic for performing some action for your agent the basic functionality of it is to have an update to check your logic and perform anything related to that action, and tell you if it has succeeded or failed. That is really it nothing too fancy just an update function and an example of this might be a find target action all it would do is check if target is in range, and if the agent can see the target and if it can then you have a success, if not then it failed.Selector Nodes
Next is the selector node this node helps determine how to traverse down the tree to find the behavior you are looking for. If you making your tree correctly most of you actions will be toward the bottom of the tree and the selectors will be there to determine which set of leaf nodes you will be updating for your current agent. An example might be at certain health intervals do one thing over the other like if the agent has less than 50% health. The selector node will consult a set of actions else consult a different set of actions. In figure 1 there is a basic notation and showing possible result of 1, 2, and 3 for some condition (there will be an example tree later). Another thing to be aware of is when you are creating your selector nodes is the order of your options is important. Actions with a higher priority should be placed first because if that action is the most preferred action you don't want them to do something you don't want them to.
For example your agent has low health his options are suicide rush target, cower in fear, or go heal and lets say you order that in that order. It will check suicide rush first and if that succeeds then the agent will do that, but if there was a health pack the agent could have used it would never make it to the heal option if he can always suicide rush the target. Now you can add functionality to prioritize the selector with a values for each option, but really you doing the same thing as if you had just organized it from the get go and it saves a bit of computation time (just a bit).
Sequence Nodes
Lastly is the sequence node. This node controls the execution of the actions. The core principle is that each action executes after the one before it succeeds. If it fails then the whole sequence fails. There are 2 notations commonly used for this one displayed in figure 2 the other in figure 3. Figure 2 is the notation is more commonly found in HTN planning and I find more appealing because it covers all of the nodes that are in the sequence and is more explicit especially if you end up having a large tree you could lose track of what nodes are in the sequence.
An example of what a tree might look like with all of these things is displayed here.
Behavior Trees (In detail)
Specialized Nodes (the others)
I mentioned above about other types of nodes that you may want or need depending on the demands of your game, so here are some examples of nodes you might want they aren't all needed and you should only add them as you need them. You may also find that you need something I don't mention and if that is the case by all means add it in yourself :). Decorators are a very vague type of node because it typically modifies the execution of another. This can be anything from adding a cooldown timer to an action before it can be used again, limiting the amount of updates that can run on a particular action, or maybe you just want to invert the logic. These are there to modify/decorate existing nodes, and it can be done however you see fit.Parallel nodes are very similar to sequence nodes, but instead of waiting for an action to succeed or fail it simply executes all of the actions in that set at the same time. I personally haven't found a good use for this node just because I feel like it takes away some of the structure of how actions execute, but if you have a reason and need it now you know about it.
A node I have heard requested by me is a random selector node. This essentially ignores any priority set up by a standard selector node and randomly picks one of the selector nodes children at random.
Detailed Tree Example
I made a quick example of how you might organize a standard guard in a game it's very simple and gets the point across you probably want something a little more detailed and explicit if you were to put this into a game but it's a good game example for explaining and actually relates to a game scenario and not something silly like opening a door.
EDIT =>So I made a mistake. All of the preconditions such as "has cover" or "seen enemy" is a precondition check for a sequence So I want to clarify what that means because I think it maybe have come off as misleading. What that means is that it's the first node in the sequence the selector should contain no logic on determining what branch to go down other than using a type of priority selection if a precondition of a sequence fails then the tree will move to the other branch. A redone example of how this works is that for the attack branch is shown below.
As you can see the first check if to see if you have a target or not and if there is a target it is a much higher priority than doing nothing, so combat takes precedence over simple patrolling.
The next check is between types of weapons and self preservation. Self preservation is typically top priority because if the agent dies then it is game over for the agent literally so that check is done first. A secondary check takes into account for cover if the agent has available cover he will go to cover then heal if he finds cover. If there is no cover available then the agent will just heal at the current location.
Next is ranged combat this agent prefers ranged attacks, it's first (if you had a melee character you may want to switch these 2 or just get rid of it all together). It's nearly the same as healing, but instead if the agent can't find cover he will just crouch and shoot.
I'm sure at this point you can get the picture of how it works one of the toughest things I noticed is getting people to understand this process of how trees should be created. Once you figure it out you are in good shape and can start building great AI behaviors:)
HTN Planning
First things first this section might be a lot shorter than you think. Why You might ask? Well I just told you about 90% of the info about HTN Planners because the difference between HTN's and Behaviors are very minimal. World state is the key difference between the two, typically an HTN will consult the world state when going through it's tree. The other difference is having preconditions and effects for the actions which actually fulfills the planner portion of the HTN.World State
World state is basically a representation of the game world it can contain things like the amount of enemies left, interesting objects in the world, maybe certain structures or buildings, or more commonly if certain events take place, like an alarm going off or the lights going out. In a HTN planner the agents will look at this information and change their behavior based on what happened. For example perhaps the lights do go out in a map the world state has changed this may require the agent to go over a light switch and turn the lights back on. Once that agent turns the lights back on now the world state changed again because the room has light in it once again. What this eventually boils down to is a behavior tree, but now instead of just consulting the agents own internal information it now also looks at the state of the world.Preconditions and effects
This is common syntax that you might find when doing any work involving planners at all, but the concept is simple every action has a certain amount of preconditions that need to be true before it can take effect or update the action. In turn the result of completing the action will then have some kind of effect on the world state. This is actually similar to selector nodes except it can consult multiple variables for one action, it effects the world state, and if your clever Like Jeff Orkin you can A* search through actions. Keep in mind however actions don't have to modify the world state it's typically more common for them to but Killzone 2 & 3 wrote an HTN and it never modified the world state!Planning
Since this is similar to a behavior tree you might be asking are the created the same how do you build a HTN Planner. Ironic it's very similar you still define what sequence of actions you make and build your behaviors based on how you did them for a behavior tree except now you have a sub planner running the system. Let's go back to our example of healing. We will just be looking at the action for healing and not the whole tree but you can consult the detailed tree above to see where this fits in.
The point of this example is to show that the planner knows about a bunch of actions and that those actions can result in many different things depend on information available to the agent. For example in one of the paths the agent is unable to find a health pack because the precondition wasn't met in the find health option. This then lead to the agent cowering in fear instead of finding health.
Like I mentioned before this is just a portion from the behavior tree I created above in an HTN you may have this for shoot, melee, combat, or even going to cover, so this keeps the structure of the tree but the freedom of a planner to determine small sets of actions for smaller behaviors.
Conclusion
These architectures are really great at managing behaviors and are very common currently in the industry so if you are looking for an AI job it would be very beneficial to know this information. They keep the AI agent well structure and allow designers to have control and influence of the AI, but it also give the AI more flexibility and freedom to carefully plan out actions. Hopefully this has enlightened your knowledge of behavior tree and HTN planners, or taught you something entirely new if you didn't know any of this information before.As always if you have any feedback, questions, or comments feel free to post a comment or e-mail me at justinmaio01@gmail.com. Thanks for reading :D
No comments:
Post a Comment