AI Arborist: Proper Cultivation and Care for Your Behavior Trees

[Music] right yeah my name is Micah Vakula and I work for a remedy entertainment as a lady I programmer and in this session together with Bobby and Ben let's talk about her experiences working with behaviour trees and in my part I'm gonna be talking a little bit about a quick touch upon this blackboard and database which is used together with behavior trees in almost in all the implementations then the most of the talk that I'm gonna give is about decorators then a little bit about splitting the trees and then also about coordination using behavior trees so some of the challenge areas that I've faced using multiple different implementations in different games have been always the same thing it sounds like a simple stuff but it still comes up time after time it's the generalization and granularity of tasks so to the pro in in like pre-production production and then of course between game projects as well so you would like to of course build eventually this library of reusable building blocks of decorators and nodes that you could use then you know in future games as well and then also there seems to be this question especially from designers working with this this implementation is is that how do you deal with interruptions and transitions in the behavior trees but before I go to all these nodes and decorators a quick glance at this databases so most often what people have in construction with behavior trees is some kind of a blackboard implementation and also this kind of sensory systems that the sensors will basically reflect the data from the game world from all over the memory and then store it inside a database a compressed format and the behavioral tree is only reading through this database you can read and write there so it's still a good idea to keep in mind that the simpler this implementation of the database is and the data format and the more compact it is the easier it's gonna be to implement all of your nodes and decorators especially for conditions it also makes the debugging easier which is pretty obvious but if have a very condensed and a nice implementation you can just basically list out of all the properties that this NPC knows of and then finally of course it performs better because if you have a very compressed set of data that you're accessing it's going to be much better than accessing the memory all over the place so one example and I'm using this kind of method in this presentation how you could implement the database would be to have it one single dictionary protract entity or a known entity for each of the end pieces and this dictionary is just lists of properties key value pairs that this NPC knows of of each of these tracked entities so in this example for example we have entry for self the agent itself and in this example it would have only one property primary target set to enemy a1 which happens to be the other entry another dictionary in your database that has one property which is visible is true and you can reference these entries in the database in your decorators and nodes just by using a string path so for example self dot primary target means that you take a look at the self entity and and you read the primary target property this happens to point out to enemy or one so now you read from enemy or one the visible the value of the visible property okay let's move on and go finally to the actual behavior tree stuff the nodes and decorators so a very quick recap you obviously we have a tree is consists of root node control flow nodes which are the selectors sequence nodes parallel nodes and then your execution nodes or tasks what you also have in many implementations is some kind of decorator nodes so you may implement your conditions as decorator nodes and in this example you would have for example two conditions for this sequence so the above one the abort condition would have to be met before it can select the child behavior sequence also the child not the first child node of the sequence must be able to succeed because if it would fail the sequence would of course also be aborted so both of these conditions have to be met before the sequence can be activated so if this happens now the sequence is activated it would proceed to the first tasks the middle one there and if the abort condition I would turn to be false of course it would abort the sequence and exit this whole branch but if the other one the condition the first child of the sequence would turn later to be false it would have no effect whatsoever so this would be the control activation and deactivation decorators then you have modified termination status decorators which would be something like always succeed so this always just succeeds when its child is completed even if the child fails it will report itself as success to the parent so in this example it would make the first task as optional in sequence regardless of the task failing or succeeding the sequence will proceed to the final task and then you can have something like these add-on functionalities for example if the last task would now fail it could set a property so these decorators are very nice for doing cool down or retry mechanisms without having to implement it inside the task itself so all these are kind of a nice and and very useful I'm sure that you you guys are using them with your behavior trees but there's also another way to think about them which would be instead of decorator nodes know the decorators and there's a nice examples of me ESCO ceiling ski did this for the unreal force behavior trees so it basically means that the decorators are part of the nodes themselves they are not actually nodes at all so this will create in my mind more compact visual representation of your behavior trees and it also allows more options to simplify your nodes you know easier way so the common types again would be that you have the activation and deactivation controlling decorators inside the node but now in this case you can easily see that this sequence they are within the sequence both of the abort and and the irregular condition you can have the termination status modifiers again it's much easier to see that now this task always succeeds you can have parallel execution by having updatable decorators unreal I believe ghosts and services and the final you can have the same add-on functionality that if this task the the right one fail it sets a cool down property to ten seconds in this example so comparing these two approaches at least myself I prefer the left one because it makes it much more condensed and especially when dealing with big behavior trees when they tend to actually grow up you would like to of course be able to read those trees especially if they're authored by multiple people in an easier way so that's one of the kind of the major things that I personally like with this kind of an approach so a few more examples what you can like how you can try to build your library of this reusable building box with decorators and and more general purpose nodes it's an example of a retry mechanism so you can have this selector that will first try to of course activate the press button behavior it would be a general-purpose behavior where the NPC is trying to press a button maybe it even has the animation control inside this behavior let's assume that it would now fail so for some reason pressing this button didn't succeed so we add this general purpose decorator that says well if I fail set last try property to be the time stamp of now also we have a condition that checks that if time seems this probability is more than 10 seconds then you're allowed to select the node so if you now fail it would take at least 10 seconds before you can reset the node so the selector will happily select the next behavior which is play animation and we can now also add this general purpose loop decorator also very common in many implementations where instead of having to play animation to contain a a selection of I want to loop this animation or maybe an option inside the animation resource itself you can bring it forth in the behavior tree itself and say when whenever this task succeeds it will start over again and won't report to its parent that it has completed so in this example it would make this play animation that you simply play forever but of course since the selector is monitoring the higher priority branch the press button eventually it can be reelected because the time stamp will be more than ten seconds old and it will retry the press button so again you don't have to implement this retry mechanism into any of these behaviors but use a a general purpose set of decorators and behaviors an example of look at so you can have two types of parallel execution things now with this update decorator's so a parallel node will execute a move to which will move to a next Waypoint at the same time there's a look at behavior which would try to look at a location of primary point of interest if it is set and then you can have an updatable decorator that is separated from the luca so the luca doesn't figure out like what it should look it simply just looks at a point that has been set in the database so the scan point of interest will be scanning around the agent and setting this primary point of interest if it finds something interesting and now the look at would of course pick it up and start looking at that point in this example the available decorator could also be of course input into this look at node itself then we have debugging so we can also use these decorators very easily to help you debugging behavior trees so you can have tag decorators so it's a simple decorator where you can give any string in this case in combat or in patrol and you don't have to care as a designer or a programmer how did these nodes get selected to be able to can be complex like above these these behaviors you don't have to care like where this is or if somebody really factors the tree somehow you don't have to care also you not have to care what happens inside these nodes whenever two node is active this tag would be active and there can be a simple way to basic query which tags are active at this moment and you can display them for example on top of the character's head showing the guy is now in combat or in patrol this could of course also be used outside of debugging and maybe control the the game plane in some way same thing you could do with message decorators instead of tagging something you can basically have a message decorator that sends a message on activation of the node on the activation of the node and possibly even sends every update some kind of message alert your debugging systems or possibly to the gameplay systems as well and finally of course breakpoint decorators which act in the same way so if the node gets activated and perhaps there's a condition if the condition is met then the game will for example pause and zoom to this actor so it can be very helpful if you have multiple actors running around to have this condition that you can flag I want to monitor these particular NPCs and any of them happen to select this one node you will pause the game and zoom to that place and see okay now the guy is about to perform this action so with all these examples what I wanted to sort of bring forth is that building a library of reusable tasks actually is more like balancing out how to extract options from your tasks into decorators and kind of balancing the library of decorators and nodes together and of course it wouldn't matter in which way you implement them but but I personally prefer these these decorators to be the property of nodes themselves a little bit about interruptions so we could have a case like this there's a selector that has a higher priority behavior jump to safety if there's a grenade within 5 meters of the NPC let's assume that there is no grenade yet so the selector would pick a sequence and it's sequence the first thing that it tries to do is a heroic super slow world to cover let's say that takes 15 seconds it looks very awesome and it's going to take the character outside of the navmesh and do all kinds of funny things and it's going to be very difficult to interrupt it in a meaningful and good-looking way well he is now in halfway through this vault animation let's say that the grenade lands next to it so what the behavior tree will do it doesn't really care it simply selects a jump to safety and deactivates this other one what to do so of course I don't think it's a problem of the behavior tree person I think that that's exactly what should happen so the task that is gets interrupted may of course do some cleanup perhaps it wants to tell the animation system to stop playing this animation maybe it doesn't so the second dinner it can do is also the jump to safety that gets selected it doesn't have to fail if it cannot perform immediately this jump to safety so perhaps you want to just wait out that the body is able to perform the action that you want here what I'm trying to say is that it's really not oftentimes a problem of the behavior trees to deal with these interruptions even though there's a lot of this question of the questions of what should be done but sometimes you might still have the case that you want to commit to an action and you do not want to interrupt this in the behavior tree itself so you could also of course add an uninterruptible decorator into your node and this would be quite simple to implement so don't think it insist that if there's an uninterruptible node it will freeze all the the condition monitoring on top of the tree like throughout the parent apparent hierarchy of this tree you can chain also those uninterruptible so if there's a child node to this uninterruptible of course that would then set the parenting hierarchy to be uninterruptible but personally i wouldn't really use this i would try to avoid them at all costs because eventually you could get the tree getting stuck and weird issues that the guys performing very long sequences and and not reacting to anything so splitting the trees that's the next thing this is like a workflow thing and I also think it's it's something that people do very often so you can have two types of ways to split your trees as a property of behavior trees of course like any sub tree can be always considered as its own tree so what you can do is have reference nodes so this would be design time nodes where you can just extract a part of the behavior tree and save it to a separate resource and then you set in the parenting tree that contains this tree a reference node and you refer this this behavior it's a pretty standard node to have in in your in behavioral implementations so this is design time it merges during export or load so it reduces the perceived complexity of the tree not really the actual complexity of the tree and the main benefit is of course that it allows you to edit these these behavior trees by multiple people at the same time without having to worry about the merge conflicts and you shouldn't go like crazy about this and start immediately doing them you should basically build this one tree and whenever it seems like logical you should then take a piece of the tree and save it to another resource effectively when refactoring your trees as you go there's also these other types of nodes which is allows the dynamic attachment of behavioral trees so it's just a placeholder know that saying well if there's nothing attached at this node at runtime the node always fails it cannot be activated and you can from somewhere in code you can attach a behavioral tree here and then it would just do the same thing as this statically attached tree then it would appear as part of the tree so what you can do with this dynamic trees is smart objects for example so instead of having fixed pipeline smart objects where you have for example of actions or animations to perform when you try to use these things you could simply have them as containers for behavior trees and maybe a small piece of a database that's embedded with the smart object so it's essentially a instructions of how to use this smart object you could also have items and weapons so instead of having everything put into the character themselves you could have the combat part of the tree actually be embedded into the weapon itself this would allow you especially in the prototyping phase to build a single NPC and depending the weapon you can change how it actually behaves maybe later on you still want to cut all the behavior trees inside the character but this way you can dynamically say if I give this guy a pistol maybe he wants to use cover and he wants to fight quite close by and if you give him a shotgun maybe he's not using cover in the same way maybe he wants to perform a different set of actions instead and then you can do more than just the smart objects in your level scripting so for example for spawning again instead of having fixed pipeline spawning animations that the guy rushes through the door in some kind of awesome way you just put a behavioral tree that overrides your your master tree at a very high level when the guy is spawning maybe it has some kind of sequence similar sequence to rush through this this door or have some is using like moved behaviors but it can also do things like if the enemy happens to be very close by maybe I don't want to commit into this long animation and expose myself but instead just take a shortcut and start shooting back immediately so this would be such a simplex example so this smart object could be as simple as just a list of animations as you would have in your fixed pipeline smart objects and then you could attach it into this child tree node and the node itself can be also very simple so you can have the cooldown mechanism implemented again with these decorators general-purpose decorators and for weapons of course you don't want to detach the tree if this child tree is not active but for smart objects when you have finished using the smart object you can add this decorator that says when this node terminates it detaches the smart object and then finally there's this thing that the whole trees are oftentimes used and mostly used only to control your characters but they could also be used to to do coordination between NPCs so what you could have is a volume for a room like a box whatever a shape of a volume and you can add a behavior tree to this volume as well and a database to go with it and this behavior tree of course would not have moved behaviors because the volume is not moving much or controlling the body in any way but you would basically have a custom set of nodes and decorators that you could build up which would be updating goals and objectives influence naps with updatable decorators assigning roles and communicating with NPCs either by writing bitter individual memory or just writing to its own memory and opportunistically these NPCs could be reading from this database and altering their own actions so some wrap-up I personally think that the way that unreal has for example implemented the decorators it's a great way it simplifies the the complexity at least the perceived complexity and it allows an easier way in my mind to implement this kind of a reusable building blocks for your behavior trees and for your games you shouldn't be limited to a single static tree use a lot of this dynamic and static reference notes and finally be able trees are not character specific also they are not the only mechanism to control your characters and I think Bobby will touch upon this subject a little bit more now I want there's of course read more so a game dev has a lot of articles about this and the only four is very well documented as well as angry and behave so body your turn [Music] all right so for my part it's gonna be a little bit more of a best practices talk we're gonna talk about some problems with behavior trees we're also going to discuss some of the solutions nothing I'm gonna really discuss today here is gonna be revolutionary in terms of you know reinventing the wheel or anything oh yeah I'm not gonna do anything crazy what I'm gonna do is I'm going to provide some observations and suggestions people have touching this in the past but I want to go a bit more deep and I want to kind of hope that I can prevent some pain for people in the room and also kind of kick off some discussions it's kind of a intro to this I just was cus my perspective on engineering I don't believe in silver bullets I believe that every technique every approach we have has pros and cons and in games especially we tend to lose our perspective a lot and we tend to brute-force our solutions it's our job to sort of look at the tools we have and understand them deeply and understand where they work where they don't the pros and the cons also in games we have this mentality of sort of milestone driven goal driven in future driven approaches where sometimes we'll lose sight of the bigger picture chasing a small goal in my experience the better the tooling we have the better the workflows the more iterations we can do the better the end result is and so to have good tools you need to understand where the flaws are so if y I dive into the behavior tree stuff I'm going to discuss a little bit of visualization ident to kind of think of trees in a different way to most kind of the traditional approaches you saw in Micah's display and angry on to 904 is sort of this kind of vertical approach where we both have the priority as well as the sequence order of nodes running horizontally so you'll see that both priority high to low is left-right as well as actions left to right I prefer to visualize trees and more of a kind of reading approach in my kind of preferred way of visualization I kind of have the priority going from top to bottom so when we branch we kind of branch vertically and then the actions are running left to right sort of like a sequence or a timeline that helps me reason about behavior just a little bit better because I'm like okay well I've made this choice and now I'm gonna make this choice then I'll make the third choice okay I've made the choice now I kind of go left to right to go do it so I'm gonna start off discussing some of the problems behavior trees are inherently bad at two things those interruptions and transitions and behavior prioritization now I know a lot of you gonna pull out pitchforks and torches and yes you've shipped games would be heavy trees and everything worked out fine and you know you got everything done and you can but just hear me out so currently the most sort of common approach to behavior that our seniors she is event-driven that basically means that as we kind of traverse the tree at every single point we register these monitor nodes till we hit a behavior that we run these monitor nodes get updated every frame and the deeper we are in the tree the kind of more monitors we need to kind of check the higher priority behaviors and one of these monitors ends up triggering it will end up causing the tree to sort of abort reset and kind of go into that behavior they triggered and this is happening to the conditions that are being set for these monitors and the entries this leads us to our first big problem in that estatic prioritization of the trees so imagine I'm currently in fighting how do I go to investigating well you know the only way to transition from a high low priorities is to either abort to complete that behavior to abort we usually need to then start sprinkling the special case conditions in these behaviors so if I was fighting and I lose sight of my target I need to now write a bunch of conditions in there saying well if I lose sight of the target fail this behavior then the behavior Qi will reset and then I can jump into a lower priority behavior this kind of ends up polluting the tree especially the holo behaviors with low priority ones it's kind of implicitly because you're trying to cater for the transition lower down by canceling a high level thing which greatly ends up increasing in complexity the tree and then there's another even worse problem which is that we often need to change the priorities of our kind of high level States based on the context of the situation to highlight this I'm actually gonna have some audience participation I'm going to show you an AI design I'm gonna give you a few seconds to kind of look at it and tell me if you understand this you guys get this do you see what it's doing is everybody kind of no no yes people will get this okay so I'm gonna ask some questions if somebody can answer you just shout out in the room when can a super attack occur there we go what happens after I do a super attack cool and from attack patta - what can I do okay simple right what about this the same diagram the same AR system it's a little bit harder to read and this is inherent to behavior trees because a behavior trees are directed acyclic graphs it means they have no loops they don't have cycles that AI design and AI designs in general are cyclic even the most basic combat behavior cycles between things like fight from cover right from position oh wait no go back to cover we're constantly cycling these behaviors and what we're trying to do is we're trying to model cyclic behavior with the acyclic data structure and yes it can be done doesn't mean we should so how do we do this modeling of the cyclic behavior a lot of you in the room are probably doing this without realizing it we end up doing preconditions to get the required results so for example we'll have stuff in our knowledge saying hey did I just do a charge attack yes okay cool then I can do this through another set of conditions somewhere else unfortunately this requires us to sort of track this kind of stuff in the ancient knowledge and it kind of pollutes it with execution and control flow data for the tree inside of the agent knowledge which is supposed to be kind of the agents personal state about himself it also greatly increases complexity which ends up hurting robustness understand ability and obviously performance since we have these monster trees we have to evaluate worst of all is that we're creating these implicit transitions in dependencies between the sub trees and the agent data now anybody doing computer science you know it should be beaten into your thumb pointed translate like implicit dependencies in depends in general are not good things and these days like a personal metric of mindful code quality is more like how easy is it that code I'll look at a piece of code and say if I wanted to leave this thing how many areas to have to touch if it simply just copy paste delete and everything works then that is good code quality if I have to delete that touch this change this undo this hook remove this pointer here we've got problems so I'm gonna ask you like how easy would it be to for example if you need to delete one of these behaviors well I'm going to delete all the preconditions in potentially super attack inside of charge attack I'm gonna have to find every place that I've hooked into this to kind of fake the cyclic flow in turn a cyclic structure and so over time this works but all the solutions especially later you get into a production end up looking like this well you've beaten this square peg into a round hole with a lot of force to the point where now you can't even get it out she tried another we've discussed kind of the transitions and the interruptions in this kind of priority we also have another thing is that often when we do these transitions additionally we have to signal the to the player that hey I actually switch state so normally we kind of simplest case we play an animation and sound but sometimes gets more complex and we have to do things like oh I turn to target I gotta pull out my gun I got a you know do a bar maybe wait a second or if we're doing like a boss fight in a brawl oh we need to do something like taunt the player wait for a bit that kind of thing that is purely kind of like a visual state it's not decision-making it's nothing it's just saying okay you know let the play know what's happening and he can react it and these reactions in 20 havior unfortunately end up again being shoved into the tree and we end up with situations like this so this is a subset of the previous example where you'll see now we have little trees inside of the other trees saying oh if I'm transitioning from this state do this thing from transition from the state do this thing and even worse now we have a lower priority behavior handling high priority behavior so now we've got spaghetti everywhere we just don't know it everything's linked to everything everything's handing everything every flag in the tree you you change one setting here and you don't know what truth is where now I guess a lot of you in the order to basically saying like okay well the heavy tree is awful right you know that you're supposed to tell me how to use them not how bad they are so behavior trees are actually kind of good but they're good in a different sort of way like if you look at the wave pity definition for behavior says it it's a mathematical model of planned execution I think that's super important something we've kind of forgotten it's a plan execution model and that sort of implies that there's a plan you know not that the behavior tree is the plan that it's just executing somebody else's plan behavior trees are really really good at describing a complex sequence of actions to perform so I'm going to show you a simple behavior now and I'm gonna ask you again a question and hopefully you guys will shout out on me what does this behavior do as soon as somebody knows to shout out and dave is wrong Tony okay and when do we look for a new position for example kind of if we don't have a good position you'll see that this little branch in there but yes for the most part this is a very simple approach for doing a fight from position not a cover just in the open I'm shooting as soon as I maybe don't have a good position based on line aside or whatever I find a new position and when I'm stuck in a good position I'm shooting the plane he aims in me I'm like okay cool let's move let's give him a bit of a challenge of padding gameplay or something so a lot of people kind of think of behavior trees as decision-making if we look at like a standard rustle no big the behavior tree is kind of fit in the decision-making that's where the people have lumped them in to personally I think of behavior trees is more of a control layer in between actuation and decision-making you know we can still make some decisions in the trees but those decisions shouldn't change our overall AI goal or AI state there's simply decisions to execute our decision if we've said okay you're fighting from cover the behavior tree can make sense in saying hey I should pop up now or I should dodge the left or I should do a reload but they should never say you know what I actually think it's better for me to to go outside a cover right now even though this is the cover behavior for example in the previous example we made the decision or if I don't have a line of sight I find a position with line of sight so if we work kind of under this conception of these simpler execution trees we need a sort of a high grandeur narrative actions we need actions that are like more like move look at reload fire I've seen implementation if you have shoes with the action is a little bit more coarse they're like fight from position four I can cover that degree of things where you're using a behavior Qi sort of like a decision tree for the most part so simpler and smaller trees obviously each one executing just a single goal and we also need to make some decisions in the tree as I mentioned so for example we'll decide whether we have a good position or not now if we move to the simple execution oriented approach we have several benefits obviously they're easy to build because you're solving a very small problem in isolation they're easy to understand in debug in like less than 15 seconds you guys could sort of understand what was going on and that's what you want to do if you have a new hire coming into your codebase you don't want to be like scratching his head for three days trying to it's also easy to identify the working data set if you want to paralyze your agent updates or something it's good to know exactly what data using so you can kind of isolate that out so you don't have any kind of race conditions or anything like that or overriding of data they're all so easy to test independently again if you know your data you can build a test harness and just have that behavior in tested saying does my fight from position behavior work well let's just test that don't run the whole way I don't write anything just run that behavior and test together and they perform better cutting out I think now obviously gonna say well how do you author these things what are the rules well my general rule of thumb is I basically say to myself okay I've made this decision I want to go to cover and I want to fight from cover what are the steps I need to do to execute that that's generally how I I kind of think I like simplistic approaches maybe I'm but slow in my old age you know like but I kind of like things that are simply to understand simply to build simply to reason about especially like a few months later when I come back something I don't know be like what did I do here or what idiot wrote this allows me you know so again I guess a lot of people are saying well first you said that bad then they're not now you're saying don't use for decision making but I can make some decisions it's like what should I actually do well we're spoiled for choice we have a lot of techniques available to us we have state jeans we have planners we have utility systems these days there's a revival of neural networks machine learning that kind of stuff we have a lot of these options out you don't have to pick one you can pick multiple you know choose what I've kind of found to be an elegant approach to solving this problem for me at least is something I like to call a hierarchical finite state machine behavior tree hybrid or helpful symbol to her for short rolls rolls off the tongue help us some butter hearts so I guess a lot of you are asking me like state machines you know didn't we go through this already you know there's problem problems you know that kind of thing and there's a whole bunch of you're probably going like I've seen this movie I know how this ends but jamia so state machines are excellent for describing states and transitions they're easy to visualize there is two or three easy to understand they're horrible for defining sequence of actions absolutely horrible behavior trees are excellent for describing sequence of actions and they can do parallel execution of actions but they're awful for describing transitions and the cyclic behaviors both of these techniques are relatively well proven they're well understood the super low risk you know there's very high reward but alone both of them have different problems and what we're trying to do is kind of combine them together to kind of build something that's greater than some of the parts we want to kind of accentuate the pros of one and the pros of the other and try to minimize the cons by just avoiding them at all so I'll give you an example of this based on this simple combat investigation a AI system if we look at this diagram it's kind of the same as before except it's a little bit more clear we can say okay I'll combat behaviors can alternate between these three we know that from each one we can go to the next and alternate back depending on what's necessary we can say okay we can go from idle to combat but if you want to go back to idle we have to go through an investigation because maybe our game loop is set up to say fight when I lose a target I investigate if I can't find him I'll go back to idle if I was alerted in my idle like I heard a noise then it's okay to go back to relaxed idle it's sort of very clear that you can look at this and say yeah I get what this is doing you know cool also if you click one of these transitions you can then set up a set of conditions there saying hey if these conditions are met I do but I just placed simple reaction behavior or hey if this different set of conditions is then H do something more complex it gives you the flexibility that kind of do specific transitions and again it's very simple to understand and now again if we go back to my code quality metric if I want to delete investigate what do I do I select investigating I hit delete all the transitions go with it all the logic for the special cases go with it everything's clear it's like it never existed and I had to be a very kind of elegant solution for that now I don't want you to miss the point here don't get me wrong the this approach obviously isn't perfect pros and cons everywhere there are some tricks with this approach that you need to know like regarding how you do hierarchies and entry states and that kind of thing if you want more details about this ping me I'm available sweet whatever but my point isn't about the state machines I could have just as easily used a planner or some other technique for example these sort of execution behavior trees are grateful used with their like a HTM planner where the tasks themselves are the trees my point and that I'm trying to get to this talk is that behavior trees are not an ideal technique for decision-making we are abusing them and do that abuse with scary new people from these things I've had situation we have come to a company and looked at a behavior with 40,000 nose and been like you know and then it's like a week later I know maybe one tiny portion of it like we are making things a necessary complicated for ourselves and we're sort of drowning in some complexity when you get to a point where you want to do a simple combat behavior and it takes you three weeks of breaking stuff and kind of trying to figure out a way to crowbar in we have problems so what I'm trying to get at is fundamentally is understand what you're building with whether its behavior choose any other approach behavior ease especially is that these sort of cyclic problems are not very well discussed or known that's something to keep in mind so in conclusion I'm just gonna give you some do's and don'ts just basically wrapping up what I just talked about it's simply behavior trees are excellent at describing individual behaviors hence the name I guess behavior trees so use them for that keep them as small and as simple as possible and combine them with other Meek's to get the most out of them also things that are bad is as I said interruption transitions the cyclic problem and please start building large monolithic trees that have multiple responsibilities you know don't have this massive tree with the static prioritization of combat over investigation over this over that imagine trying to build a boss battle in a behavior tree it's gonna be a nightmare so you wouldn't do that you'd probably use the state machine for that and that's what I'm trying to get at is kind of understand the tools that you're using and more than anything else is stop using behavior choice for your decision-making logic use them where they work so Ben is now gonna kick in with something a little bit more interesting and complex hello everyone my name is Ben Weber and I'm on the science team at twitch today I'm going to be talking about a lot of my experience with behavior trees during my graduate study at UC Santa Cruz so here's the topics I'll be covering for my section of this talk a lot of my experience was with the reactive planning language and there's a lot of different features of that language that are useful when you're authoring behavior trees so on I give some ideas and inspiration for some patterns you can use from that also as you start to author more complex trees you start to see patterns being used over and over again I actually didn't follow Bobby's advice made one big monolithic tree had I seen this talk before I might and things differently but I'll give some ideas for how I handle that complexity and then third I'll talk about some extensions to behavior trees so Bobby talked about finite state machines being used in collaboration with behavior trees I'll talk about some learning mechanisms I used with behavior trees so a lot of my experience with behavior trees is actually with the able reactive planning language and this was a language that was used to author the autonomous characters in facade so a reactive planning language is like an HTM where you basically execute as you're planning and it has a number of primitives that are similar to behavior trees so you can kind of talk about it in a similar way there's selectors there's parallel and sequential nodes they just have different terms so I'll try to map those to the common terms here in this one of the no types that's really useful when authoring agents that need to handle a lot of goals and do kind of current concurrent action pursuit is Shpongle and this is an o-type where you basically create a new goal to pursue but it's a separate threat of execution from the current node scoped at the node that it's created from it's basically a selector node but it's pursued concurrently from the current execution flow and if that node goes away the parent node is removed then that goal goes away as well so it's way of doing concurrent goal pursuit that's scoped within a particular task so on providing example of how that's used within a bot that I've produced another example is working memory modifiers so mica already talked about these decorator patterns where you can read and write from the blackboard I'll talk about how that's used in the system that I produced and then a third node type is success test and this is a type of node where you basically can combine it with a weight step to suspend the execution of your tree so if there's a seven conditions that you want to become true before you proceed you can use this node type to do so so you basically continue to perform an action until a set of conditions is met so I use this tool that actually runs asynchronous from the decision cycle thread and it creates issues whenever you need to actually execute actions in the game this probably isn't their problem if you're using a behavior tree library but I did have some issues with things like task scheduling and resource contention where you need to make sure that if you have concurrent goal pursuit that you're like setting state or locking behaviors so that you don't have multiple goals that are trying to use the same unit or cause multiple threads of execution to happen for one character at the same time also I had a performance issue with kind of dynamic behavior expansion where you can actually pass parameters to your selector nodes so a lot of what you can do there expand the tree is done at runtime which isn't really too big of a performance issue but in the initial days of behavior trees I think that was more of a concern so a lot of my experience with behavior trees was authoring a bot for StarCraft so this was called ice thought and this was done back in 2010 and it was based on this reactive planning language and what I wanted to do was have something that could play at the level of like flasher where you could do hundreds of actions per minute you could do really cool text switches you can learn from demonstrations and have this evolving meta game so I tried to author this huge monolithic behavior tree that could handle all those situations so some of the design patterns I came up with as I expanded this tree where things like Damon behaviors where this is a fiction of the agent that's done concurrently with other tasks being performed and its way of handling kind of low priority actions that need to continuously be pursued there's this concept of managers where the AI is built into different subsystems so when you have something complex you have a lot of different actions to take different competencies to manage it's good a split Haber to coordinate between these different managers I used some message passing patterns and that's similar to some of the decorator patterns well show examples of this and then behavior locking is another version of message passing where one manager will prevent another one from doing an action and finally unit subtasks which is basically using the unit for a short amount of time and then giving it back to the manager that owns it so I'll talk through different examples of this and actually provide some able code and talk about how that works so Damon behaviors are basically a way of handling a set of actions that need to be pursued concurrently so I use this in my system to basically make sure that units that need ammunition produced are basically always topping those up if they have them and this is implemented with the spawn goal behavior which then calls a selector node that pursues a goal kind of persistently so it basically spawns the selector node it has no decorator that says while true continue pursuing this sub goal so in the case of this ammunition example it basically spawns a goal to always be topping up there for the agent so how this is realized in AI spot is through this daemon behavior for restocking units so here's some Abel code Abel is translated to Java code and then compiled into byte code for runtime so it's not a data structure or tree it's actually a language that gets compiled which has some side effects but it was what I used at the time so first there's two behaviors in this example there's initial tree which is the root behavior which is parallel and then there's a second behavior called restock units which is another parallel behavior each of these has two steps the route behavior basically says create a Shpongle to restock units and then go set up the managers we'll talk about in a second and then the second behavior is basically continuing to pursue these different behaviors so with persistent means continue to pursue this and sub well it's equivalent to selector so you're basically continuing to look at training new interceptors or new scarabs for your carriers or Reavers in your starcraft bot so the per units that are empty in terms of ammunition when you start them so you need to actually produce units for them to be useful so to decompose Starcraft gameplay into something more manageable I use this concept of managers which is basically different subsystems and this is something that was pretty common with Starcraft BOTS that were authored for the AI competition where people would make like a tactics manager that handles combat a strategy manager for handling the build order things like resource manager tactics and reconnaissance and so on so here's some examples of some of the managers that I used in my system you have things like the income manager which is responsible for managing the worker units for gathering resources you have a construction manager which is responsible for actually producing units when there's a request the tactics manager handles actually forming squads and then detailed like micromanagement dancing use brown things like that and then there's a scouting manager which is responsible or reconnaissance so it actually takes a worker unit and goes around the map and later on in the game it handles other units there's also this high-level strategy manager which actually doesn't perform any actions itself it coordinates with the other managers to actually execute those actions so it selects the build order but it doesn't go about actually telling the units what to produce that's done through some message passing examples so here's an example of one of the managers in I spot this is a subset of the behaviors that get called for the inca manager so at the top you have behaviors like pump probes where this is again using that persistent keyword where it's continuing to run this selector node for pumping probes which means keep producing worker units while set of preconditions is met so you would have different instances of pump probe behaviors with different sets of preconditions but basically this is saying try to produce probes if those behaviors are ready to be activated there's also things like putting workers on gas taking workers off gas which helps manage the income ratio of between minerals and gas for the unit there's other behaviors where it actually has to coordinate with some of the other managers so for processing an expansion request the manager doesn't actually decide when to expand that's done from the strategy manager but the income manager is responsible for transferring workers to that new unit to dispatching the construction requests and things like that and what's great about this is you can actually kind of D couple these managers a bit and make sure that the strategy manager handles things like it's now time to attack time to expand and the income manager is responsible for more the tactical actions within that so to achieve coordination between these different managers we need to have some message passing or coordination between them here's how this is done enable you basically have these sequential behaviors that I show basically what a message producer is and a message consumer the message producer has one step which is a mental act and enable this is in line Java code where you basically say grab your working memory or your blackboard and create a new object called a message working memory element and put that on the blackboard system so it's basically just saying grab a reference to this add an element to the blackboard and then the second behavior here is actually consuming that dispatching a sub goal to complete that task and then removing it from memory so there's two steps here first there is a precondition not really considered a step which looks for something on working memory so if there is a message working memory element on the blackboard it binds that to the message parameter it then calls a sub goal with that message so in able you can actually call selectors with parameters and then once that's completed the at the end will clean that up and remove it from the blackboard so it's a way of actually having different managers communicate with each other and you can create all sorts of different objects different parameters so I talked about an example where you actually need agents to coordinate so you might have the strategy manager say it's now time to produce a gateway it creates a working memory element that says produce a gateway and the construction manager will go process that request but you also have situations where you want another manager to not perform an action so I call this kind of behavior locking where in StarCraft you might want to remove work from gas and focus on minerals so here's an example of where we're actually using the success test know type and the way this reads is basically first you're gonna bind an assimilator parameter if there is a simulator working memory element in memory and the not condition here says do not succeed if there's one of these on the blackboard so it's a negation term that you can use so basically the way this is going to work is if there is a similar simulator ready it's going to proceed but if there's not one yet or if there's this element working memory that says don't proceed it's going to suspend execution of that behavior so it's a way of actually blocking other managers from executing so it's essentially a fancy decorator but this suspending of execution is a great way to execute authors or I mean to author behaviors because you can do with sequence of steps which is useful when you have things that have a lot of preconditions so this is used in an example when you're doing things like expanding and you want to focus all your mineral or all your workers on minerals versus gas and you can basically have another the strategy manner to decide to perform that high-level strategy and then have the Inca manager handle the actual tactics of that and then one more pattern I use is this idea of unit subtasks so this is where you're actually using a unit for a few seconds or a duration and then returning it to its original tasks so an example of where this is useful in StarCraft is if you have a unit that's been kind of harassed by an enemy worker unit you want to basically counter-attack and then return to mining so this is where you want to spawn a goal to handle the harassment and then return it to the mining tasks so this is used in a few different ways in eyespot one is for micromanagement tasks so you group units into squads but then you want to be able to do tactical behavior where you have you know it's danced around and then returned to action I already mentioned kind of this worker defense case and then also another example is like construction so you actually claim a unit you go produce a building and then you return it to the inca manager so this is an authoring pattern used whenever you have kind of overlapping between managers that have to share units so here's an example of what this looks like with able code this is for a dragoon dance behavior where basically if dragoon is you can damage you want to back off and then re-engage the enemy because it makes your units more effective in combat so here's another example of where the success test is being used this will bind the unit parameter to a dragoon if there is on the black board where it says that damage is true so it's recently taken damage and it's not currently in a flee condition so basically this behavior is kind of executing until this set of conditions is met when that set of conditions is met then a mental actives use to basically say set the status of this unit to flee and then spawn will is used to actually handle this subset of behavior so this is actually introducing more state into the tree but we're actually spawning a separate threat of execution to handle this micromanagement tasks so there'd be a number of different behaviors to handle like the actual placement of the unit how to engage and re-engage with the unit and then once that behavior is completed it would change that flag again back to basically it's not fleeing it's now in attack mode and that would clean up this behavior so it's a way of saying like handle this set of behavior and then return the unit whenever it's available to be claimed so here's an overview of the agent in action it is one big monolithic tree basically have to start you have these different managers this is basically expanding as new behaviors are being executed in the game so at the start you have things like the construction manager and income manager that are just pumping probes wipe warping in pylons creating some gateways and then once the agent progresses further into the game the tactics manager will start forming squads you'll have the reconnaissance manager actually grab units and go Scout the opponent and later in the game once you have a big enough force like the strategy manager will create timing attack working memory element which basically tells the agent to create a squad to go engage the enemy units so this will proceed a bit so I'm units will be produced and then it will start to engage the enemy and then as behaviors are executing you basically see a turn blue which means that the trees being expanded now the you know it's kind of scouting in the middle there and here we go so now the agents actually engaging the enemy and you'll see that once these units starts to take a lot of damage they'll basically bow off and then reengage the enemy so that's an example of using that unit subtask behavior so the agent uses just these different managers to do different subsets of the behavior and execution of the agent it's doing all the decision-making within the strategy manager which is itself implemented as the behavior tree but it's a nice way of decoupling those dependencies between the managers so what I've shown so far is basically a scripted agent where the build order and decision-making was done through the strategy manager and what I wanted to look at was how can we actually learn from demonstration from professional players so that was part of the big inspiration for this agent and the way achieve this was through a few different patterns so here's kind of an overview of agent architecture where you have a set of learning components which feed off of data from replays they then interface with either the agents blackboard which is called the working memory or with the behavior library and active behavior tree so the most direct way of basically interfacing with external systems is basically reading and writing to the blackboard so if you just open that up to other components to read and write to you can do things like the particle system I use where it basically tracks where it thinks enemy units are and then the agent can use those estimated locations to determine where to attack basically writing to the blackboard was the most direct way of extending the another way of extending behavior trees is actually having an external component generate the behaviors to execute so instead of authoring everything you can basically have a set of replays that populate some of the behaviors to perform so here's an example of what this might look like you basically have a replay file and then on the right you have a behavior that would get generated so this was actually done by a project at Georgia Tech called Darmok where they actually called a case based planning and you basically feed it replays it creates a behavior library and then executes those at run time I did something similar but I actually did it by basically placing new elements in working memory one at a time kind of as a build order sequence but I think it's great to show this example here because it shows some of the types of work that can be done and it's interesting to see that you can create behaviors at runtime from examples and then a third way to basically extend behavior trees is by having other components augment the state of the tree so adding new nodes or renew moving nodes so this is a basically way of having an external components say here's a goal I want to pursue so I use this in two ways in my system the first way was for basically I had a system that detected whenever the opponent was doing something outside of your expectations when this happened a discrepancy was fired and then a new spawn goal was used to basically say pursue this new text which I also used it for this mixed initiative model I built where you basically say like it was a GUI where you basically say select which build order to do and that created a spawn goal for the system to pursue a new behavior to execute so basically it's a way of having external components tell the agent what to do and it's useful for removing some of the decision-making logic from the agent so instead of having the behavior tree decide when to attack having the tree decide what the build order can be you can have external components do that and if you've set your agent up with this manager subsystem and message passing between them you can basically swap out one of those managers with an external component so it's a great way of adding some extensibility to the tree and there's also some features of Abel that I didn't really interact with that are useful to note so joint goals and behaviors are basically an approach you can use to have multiple able agents actually agree to perform an action and coordinator so as Roxanne just mentioned in her talk dialogue was something that was challenging to actually execute because he had a lot of autonomous agents and they actually need to agree on a test to perform with Abel this was actually a primitive built into the language so it made it easy to author interactions like we're grace and trip argue about their trip to Italy or things like that another feature is meta behaviors where you can actually introspect and change the layout of the tree or change say the priority of steps in the tree at runtime and it's a really powerful authoring tool but it's also kind of dangerous because it's opening up the tree to a lot of potential issues with orphan goals and things like that so you need to be careful when you kind of change things at runtime but it's a powerful tool and then more of a kind of academic project that was done was this idea of partial programming where you under specify your preconditions for behavior and then the proper preconditions to use are learned at runtime so you basically specify a reward function and then a policy is developed as the agent runs in order to figure out when to perform those different actions so this would be complicated to do with something the skill of StarCraft but if you have a much more refined environment it's a really cool approach to use so I hope you've learned a lot about behavior tree today we talked about node decorators we've talked about some best practices and some extension to behavior trees they're a powerful tool for authoring and can be applied to a variety of different situations thanks No you

Channel: GDC

Views: 53,529

Keywords: gdc, talk, panel, game, games, gaming, development, hd, design, game programming, programming

Id: Qq_xX1JCreI

Length: 58min 30sec (3510 seconds)

Published: Thu May 23 2019