Behavior Trees

One of the readers here (at least I hope you're still reading ;) ) hinted me quite a while ago about "Behavior Trees". No, that is not a tree where you learn your dog how to behave by punishing every time he lifts his paw. Although you could program such a scenario within a Behavior Tree. Like State-Machines, it's sort of a modelling method + programming guidance. Yet, quite difference than State-Machines. It wasn't until now I learned more about Behavior Trees -or "BT's" for short-, but I didn't forget about your advice, Sander!

I won't be telling how to code them in full defail, as there is enough detailed stuff out there:

http://guineashots.com/2014/09/24/implementing-a-behavior-tree-part-1/

I'll just show a simple but practical example, and have a chat about it. If you heard about BLT sandwiches, but never about BT's (like me), this may trigger you into reading the link I just posted. No pesky difficult algorithms, but fun stuff! All righty.

Artificial Fuzz

Let me begin explaining some pitfalls when trying to program A.I. in an ordinary, “on the fly” way. The way you would probably try the first 10 times, concluding things turned into a big mess as the IF's and BUT's stacked up. A.I. is complicated, even when your foes aren't supposed to be rocket scientists. A.I. is mostly about decision making, and executing those decisions in a “human way” (or Alien way, Horse way, whatever the character). Clear enough, but when to decide what? Depends on a lot of input signals and context.

Usually it starts pretty simple. A guy with a shotgun. He should shoot when he sees you, reload when out of ammo, and die when he gots hit. No fancy state machines or whatsoever required, right? Yeah, in that case... but this makes a boring enemy. How about walking? How about smoking cigarettes if there is nobody in sight? How about NOT cheating by killing you instantly as soon as he spots you? How about gently saying "AARH @SS F#CK SON OF A B!TCH!" when getting shot in the groin?

And we can keep on going. Getting hit by a BB-gun or flamethrower should result into different “behaviour”, and also picking positions to move over depends on a lot of context. When trying to attack, a foe should try find a partially covered spot with sight on the target. When trying to reload, a fully covered spot suits better, unless it's too far away maybe. And when trying to take a dump, a room with a toilet is probably an excellent good idea.

And now I'm only talking about simple shooter combatants. Imagine you're making The Sims. Or pedestrians that should act realistically (read not randomly crossing roads & ran over by a truck) in a GTA world. AI usually goes wrong -also in AAA titles- when a NPC (Non-Playable-Character) makes weird choices based on bad parameters, or keeps persistently trying to accomplish an impossible or totally unimportant goal. You must have seen guys running into a wall endlessly, or foes refusing to stop taking that dump even when a T-Rex is knocking on the door.

Priorities...

BT's (Behavior Trees) won't fix these issues by nature, but being a modelling method, sort of, you can at least clearly visualize the whole decision-making process - and see where they took a wrong turn, or ended up clueless. And more importantly, it's fairly easy to re-route the logic, or add branches/additional choices or conditions. In contrary to common code, that turns into a gigantic mess quickly as the exceptional cases, IF's and BUT's pile up relentlessly.

One more problem with regular code, is the actual execution. It takes a moment to prone, walk from A to B, to reload a weapon, or to take that dump (I'm sorry, can't resist). Timing man! Sequential code just tries to run everything ASAP by default, so you have to smear your execution over multiple cycles. Using (lot's of) timer variables, signal flags, waiters, and so on. Waiting X seconds before performing the next action isn't hard to code, but again the magnitude of things can become a problem quickly. Dozens of timers, eventually shared amongst multiple actions to make things worse. It's too easy to make mistakes, do 2 things at the same time, or screw up sequences with bad timing. Making your guy act as if he gets electrocuted all the time.

Usually you would make a list with tasks, and execute them one by one. But, now the real difficulty comes: our situation is Dynamic. As a computer foe, life is never certain. One moment you’re carrying cement bags, the next moment you’re fighting giant scorptions. Some tasks need to overrule other, but then again be careful not to mess up. You still need to walk –no run- over to the Player before you can slap him. 

Behavior Trees

BT's are there to help. Throw away all that messy A.I. code, and start modelling buddy. And no, I’m not talking about doodling some behaviour patterns on paper to code them later. The model(file) will actually replace the code! Doesn’t mean you don’t have to code anything anymore, but it will be limited to running the BT plus making small “building blocks” to construct that BT. I’ll explain.

Model made with this online tool: http://behavior3js.guineashots.com/editor/#

Look at that picture, and tell yourself what happens here. It’s sort of a decision flow, starting at the left (although if you google BT's, they often to top-down). Probably you already figured, but basically it checks if it's hungry or tired, and if so, it executes a sequence of actions. Being placed higher, hungry gets priority over being tired. For starters, we can separate a BT in four types of nodes:

·         Composites (see the blue ones)

Elementary blocks to control the flow. They can run actions parallel or in a sequence, prioritize, or pick a random sub-node to execute. Composites do not actually actuate your NPC, but regulate the flow.

·         Conditions (see the green ones)

Basically the IF’s. Targer reached? Hunger more than 50%? Do we have the SkullKey item? Is Jack an asshole? That kind of questions. These (leaf)nodes are used to help prioritizing, or to interrupt a sequence at some point.

·         Actions (see the orange ones)

These (leaf)nodes actually actuate your NPC. Move over to X. Rotate, jump, salto-kick. Play a sound, do an animation, squeeze a fart.

·         Decorators (not visible in picture)

Used in combination with Conditions. Inverters (IF NOT x) or Delays to suspend actions.

Node that I just explained the very basic blocks. It’s up to you to add extra Composites, Conditions, Actions or Decorators, eventually with a list of parameters. For example, an action like “FindFridge” may require a maximum radius or zone, so we don’t loot the neighbors fridge. Now this where you programming skills shine; your engine/game/program has to offer a box of Lego bricks. A Shooter game would typically offer movement, aim, shoot and cover nodes, while The Sims is more about, ehm, looting fridges and making out in the bubble bath.

So, when implementing BT's, there are basically three components to deal with:

1.       The BT itself

Using a modeller program or even better –your own build-in editor-, producing BT files. Could be saved as XML for example.

2.       Set of Nodes provided by your engine

As explained above, you’ll need to code each type of node. In the end, you still need code to animate that robot, or to find a path through your maze.

3.       Engine that has to load BT & Run BT’s

Load a BT, and let your NPC’s make use of it. That involved logic that traverses the tree every cycle (sometimes referred as "Ticks"), executing the nodes that come accorss. Since a lot of actions may also rely on variable data, BT's are often accomponied by "Blackboards"; a (per entity, or global) storage space for custom values.

Johny Five routines

Now that BT is too simple, as usual with demo-models. A real game BT would have a lot more branches and nodes. So many, that you’re still having a hard time to comprehend. But that’s ok. Unless you’re a Jellyfish, you won’t able to model your own brain on a single paper, now would you? Still, using BT’s has a bunch of advantages.

First of all, the blocks you make are robust. Unlike on the fly/messy A.I. coding where you quickly end up taking dozens of scenario’s into account, smudging the “core business”, these Condition and Action nodes are really focussed on a single, simple task. A node that says “fart” just does that. Nothing more nothing less. It doesn’t check if your girlfriend is around, or if you had beans for diner. No! You –the A.I. designer- should do that prior to the action “Fart”, with other elementary nodes. That makes it fairly easy to code robust, proven, nodes. A simple node doesn’t do much, it’s all in making combo’s with others.

Although, nothing stops you from making more advanced nodes of course. Navigation and picking targets is a good example. It all sounds pretty simple, but there is a lot of logic behind that stroll from A to B. Why pick B? Can we reach it? What’s the shortest or best-quality route? And once the Nav-System has been set up, we still have to actually move our ass. Animate, rotate, climb stairs, and so on. We could spread that over many different micro-nodes, so we have FULL control over the entire procedure. But… it would be tedious. Instead we could compress all that action into a single, or fewer nodes, and use some additional parameters. For example, when picking a target, we could define parameters like “maximum distance”, or “what kind of target are we looking for?”. A fridge? A bed? Toilet? Human flesh maybe? And when we call “MoveToTarget”, we could define a speed, or pattern. Should we rush, sneak, or just chill out, not caring about a thing? Again, your engine decides what kind of parameters there are.

Long story short, lesser advanced blocks makes it easier and quicker to model behaviour, but limits your freedom. It’s up to you. Bear in mind though that Behavior Trees aren’t just limited to gunslingers and Johny-Five. Behavior Trees lend themselves well for robots, animated machinery, or puzzles. Check this door:

Yeah, even doors have a "Behavior". Of course we could hard-code all that stuff into the engine, but there will always be an exception. Especially if you're making weird puzzles, or want artists to use your engine to make their own stuff. And talking about artists, your art is to provide a toolset that is flexible, yet not too complicated. So, if well done, Behavior Trees allow non-programmers to create crazy scenario's without having to dive into the bits and bytes.

One last node I should make, is that you're not restricted to use a single HUGE BT. Of course different characters can load different BT files, but you could also chop it up into smaller modules. For example, a "Idle", "Walking", "Combat - weapons" and "Combat - fists" module. Monsters may use the same melee combat melee than people, but lack the Weapon module, and have different "Idle" behaviour. Where humans smoke cigarettes, chatter, scratch balls and take a dump, monsters eat flesh, fight each other, scratch balls, and also take dumps but without moving to a bathroom first. Apologies. Likely, a "combat" module can be split further into sections like weapon handling, finding cover, throwing grenades, and so on.

Seat-2D2 demo

Well, let's finish showing another model. Geared towards Engine22 this time. Disclaimer – I must admit I just started, so don’t expect rock solid awesomeness here. But as you can see in the little movie, it works J Without programming ANYTHING. Well, except for all the lower level engine stuff + a toolset of nodes to pick of course, but I mean nothing was programmed to make that “seat” chase me & make R2D2 sounds.

All these "PlaySound", "Rotate" and "Move" nodes have been implemented in Engine22, each with a bunch of parameters eventually.

So, what happened here? Every cycle the seat checks if it can see me(“Player”), by shooting a ray towards me. If the ray is interrupted or out of range, the seat will fall back to idle behavior, which results into either waiting, making noise, or moving short distances into a random direction. If it sees me –with a slight time delay, meaning it needs to see me at least a few seconds in a row- it will rotate towards me, then move forward, eventually correcting its angle a bit more as it slides. It keeps a minimum distance of 2 meters of me. It wants to move to me, not INSIDE me. And then it makes a cute sound.

Results? Here you go. Although Engine22 still lacks a tool to create and debug / visualize these trees (I imported the file export from http://behavior3js.guineashots.com/editor/# ) it was quite easy to make this. It required a brain-reset to jump over from traditional programming to modeling, but once you're at it, it's fun to do.

As you may notice, the graphics aren't exactly what they used to be, compared to previous video's. That is partially because Engine22 has been re-programmed (thus a lot of shaders / effects / content is missing), and partially because these rooms simply didn't get a lot of love yet. Instead of pimping the graphics, I really try to focus more on making an actual playable game this time - hence the "working" player-physics and "A.I." you just saw. Of course, chasing seats won't make a thrilling game, but it's a start! 

And-yes-of-course, we will improve these rooms. But that requires artists, and last five years I learned it's very hard to find or keep artists if you're still far away from anything solid - a playable thing. Unfortunately, making a more robust engine, editors for the artist, pathfinding routines, or better physics to avoid falling through floors isn't the kind of stuff that generates awesome screenshots to show here. Which explains the lack of material lately here. But trust me, a lot of coding is going on. Hope you understand!