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:
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!