The making of Leaf - Part 2

The making of LEAF Part 2 - Fulfilling the needs

This week, I'm going to cover the starting point for fulfilling the needs we identified in part 1. Specifically, we're going to look at the Behavior Tree structure that will form the starting point for developing the AI interactions.

Preamble:

Before I cover the AI here, I want to talk about my approach to the game "LEAF" as it is something that might interest other developers. For a while now I've been convinced that in order for an indie developer to really achieve anything, they have to work smarter rather than harder. One of the things I've picked up from other developers (including my old mate Mark) is that a "tools first" approach to development is really the only way to succeed for an indie. What I mean is that developing the tools to make the game production smoother and faster is a very good investment in time. So right now I've got a bunch of tools in development. I will use the tools to speed up game production, whilst also improving the tools themselves. Eventually, they will form part of the added value for my sales, so it really is a big win. You'll see the Behavior Tree editor tool later in this post, which is the tool users will use to create thier own AI's (if they wish).

Part 2

So, last time we had a look at Maslov's heirarchy of needs and a method of encoding that in a data structure. This time we will continue on that theme and start actually implementing the AI to fulfill those needs.

Before that, I want to look at the storage of the needs. In particular, I want to think about the various bits of data associated with each individual villager in the game. For each villager, we have a bunch of data related to what its needs are (the needs structures discussed already). It also needs information about what it knows or remembers (memory) such as which groups it belongs to, who it cares about etc. Clearly we need some data structure to keep all this information. In games AI, this is usually called a "Blackboard" and is essentially a modifiable, persistant collection of data associated with the AI for an agent. In this case our villagers each have a blackboard for thier individual memory, however it may also prove useful to incorporate a "global" memory for all agents (a shared blackboard).

We need to allow access to this blackboard data from the AI if we are going to get any useful behavior going. I'll talk a bit about the specifics of the blackboard at some later date, but lets just assume for now we have a single class with a whole heck load of get/set methods to get various named data items.

So, onto the meat of this blog. The behavior tree!

Behavior tree's are a really useful alternative to the typical finite state machine (FSM) or heirarchical finite state machine (HFSM). I wont go into exactly what BT's are, as you can read up about them at http://www.aigamedev.com/ if you really care. What I want to talk about are specific implementation issues for the villager BT's.

So what do we need to model in the behavior tree in order for the villagers to work?

The first thing, is that there are certain needs that can be simply filled by performing a sequence of actions. Examples would be eating, sleeping, drinking etc. Lets take a look at a the pseudocode for a typical subsection of a behavior tree that would work for eating.

Eating BT:


PrioritySelector:
Sequence:
Find(food);
Goto(food);
PlayAnimation(eating);
Use(food);

As you can see, the simplest behaviors can basically play a sequence of actions, actions being atomic elements where it doesnt make sense to break down the behavior anymore. Actions are executed in sequence (hence the sequence) one after another. If any of the actions fails (for instance the find fails because there is no food available) then the whole sequence fails.

This kind of sequence can form the basis of our simple starter AI. In that we can encode a few simple behaviors that fullfil the basic needs of eating, sleeping, excreting, drinking etc.

Here's how it works. At the root level of the tree, you have a "priority selector" which simply runs forever in a loop, checking its children for thier priority (how important it is that they are running). The priorities change as the AI's circumstances change, so for example if its fatigue level gets too high, the priority for the sleep sequence grows, or as the thirst increases the drinking sequence priority grows. So the Priority selector simply repeats forever, performing a priority check on all its child branches, choosing the highest priority branch to execute. It really is that simple.

Here's how the overall BT looks in the Behavior Tree editor:

The BehaviorTree editing tool, with the various sequences.

As you can probably tell, there is a very simple pattern to fulfilling these needs. Find something that satisfies the need, go to it, perform some function (animation + method) and end. Now we probably dont want to leave it there, as this is likely to get very dull very quickly, but its a good start. If we create a bunch of random agents and a bunch of random food, drink, toilets and beds, we should see some interesting behavior at least.

One thing we probably also want to incorporate at this early stage, is some form of idleness. So that we aren't constantly shuttling between eating and going to the toilet (although that does sound pretty realistic). So we need to add another sequence to the BT to allow for idleness. Here's some pseudocode:


Sequence:
ChooseRandomTime(min,max,time);
ChooseRandomAnimation(idleanimation);
PlayAnimation(idleanimation,time);


So here, we're saying "for a random amount of time, play this idle animation". Typically a looping sequence would play that shows us stamping our feet or looking around etc.

Further to that, we need something to stop our AI from standing there idle after its performed an action (such as using the toilet). So I've added in a "wander" sequence, which basically does a random wander by choosing a random position to move to and then going to it, whilst adding to a "fatique" value in the villagers blackboard to indicate it is getting tired (which eventually lets the idle animation sequence in). Essentially the wander sequence has higher priority than the idle sequence unless the villager has high fatigue, in which case it simply idles for a while.

Thats the initial "needs" sorted out. Of course to take these things further, we need to consider that if we cannot satisfy the need in an atomic way, such as there is a multi-step process to having food, like aquiring money, then purchasing food. Maybe we need to consider a planner and a dynamic branch in the tree to satisfy that. As it is, it is better to start with the smaller baby steps of getting a static "designer driven" tree up and running first.

So next time, we are going to look at how the tree actually executes and present the first of a series of example apps. This first one will show a bunch of agents walking around, idling, or trying to satisfy the current needs. I'll also have to think about how the agents represent thier needs graphically (which might mean creating some icons for said needs).

I also want to look at the less physical needs, which are probably going to play a bigger part in the gameplay. Things like love, entertainment, the urge to create etc.

Next time!!