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

The making of LEAF - Part 1 - Creating Villagers

Creating Character Motivations

The starting point for my implementation of AI characters in LEAF, is to think of the reasons why my AI characters are going to want to do anything interesting. This leads me to think about how I define thier motivations and how I encode them for use by the AI.

How do you define motivations? Well, my starting point was Abraham Maslow's "Heirarchy of needs".





I'll let you read up more about Maslow from his wikipedia entry http://en.wikipedia.org/wiki/Maslow, but suffice to say, I think he was about right in his description of human motivations (ok, from a naieve programmer rather than a pyschologist perspective at least). Luckily, we can apply a lot of what he describes in his heirarchy to our AI problem. Lets look over the heirarchy and learn what we can encode.

Physiological:

This seems like a rich set of needs to encode. I think we can dismiss breathing because of all the needs, it is the one that is automatic (mostly). So that leaves us with drinking, eating, sleeping, excreting. Interestingly one diagram I found had sex in this category too, but I think for this game, we arent going to use that as a basic physiological need.

Clearly those are pretty important to our existance as humans and as such should likely be modelled as part of our AI villagers. Lets continue:

Safety:

Now this is a tricky one. I think my view on this, is that security needs are required if there is conflict. In my design, I'm after something more gentle as gameplay, so I'm going to discount security initially. I may have to revisit this one if I later decide the game is too boring without more conflict.

Love/Belonging :

Now this is an interesting one in game terms. Thinking about the core gameplay I'm trying to get, where villagers have families, care about each other, it seems that THIS category is going to play a large part in the AI code. The typical breakdown is friendship, family, sex. But of course its about emotional connection. I think we have to at least model friendships, family, sex, perhaps even work/social groupings.

Esteem:

Respect, recognition. Again, this might actually be good motivation for our villagers to want to achieve things. Say become the village leader, or to create a better village. One to pay attention to, but I think initially it will be a struggle to come up with behaviors that support these.

Self-actualisation:

Well, this is the top of Maslow's pyramid of needs. He thought the needs where heirarchical, where as others have suggested that they arent. I must admit the heirarchy sounds interesting as a way of determining priority when different needs conflict. But modelling "personal growth and fullfillment" as one version of this heirarchy puts it, is probably out of scope for a game AI. Especially one about dumb comedy AI like this. There is one version of the heirarchy I found that has "Creativity" at this level. This does sound like a useful need to model, as it might offer some interesting opportunities for gameplay deeper into the game.

One thing to note from the literature, is that Maslow isnt suggesting everyone has this same heirarchy where we have strict ordering of needs. He acknowledges that different people place different importances on different levels of need, indeed some may forego phsysiological needs in order to gain respect for instance. It does suggest that perhaps we shouldnt treat these as a heirarchy.

So there we have it. We have the following needs identified:

Drink
Eat
Sleep
Excrete
Friendship
Family
Sex
Social
Work
Respect
Recognition
Creativity

So now comes the representation in code. Step back and ask yourself, what is it these "Needs" have to represent for the code to work?

• The current "value" for how satisfied this need is


• The "importance" the particular AI places on this needs (so we can have data driven "personality" types)


• The minimum threshold below which this need really needs attention


• The minimum threshold above which we feel this need is satisfied


• The rate of decay of this need (so for example, how fast does a satisfied need decay)

So we are going to represent these things in code. One thing I like to do in these circumstances, is to create a data type (as we have multiple values based around a single need). So I create an abstract "NEED" data type as a struct:

struct NEED
{
float currentvalue;
float importance;
float minthreshold;
float minsatisfied;
float rateofdecay;
};

The next thing is we need to do, is store the different needs somehow. Now we could do this using individual NEED type variables:

NEED needDrink;
NEED needEat;
NEED needSleep;
...

But I think this will become cumbersome and whats more we cant iterate over the needs easily. So what I prefer, is to create an array of NEED's and then index the need type with an enum:

enum
{

eDrink = 0,
eEat,
eSleep,
eExcrete,
...
eMaxNeed
}

And then simply implement the need array:

NEED needs[eMaxNeed];

So we access a need with:

float fValue = needs[eDrink].currentvalue;

Plus this way, we can iterate the needs data with a for loop and do things like plot the values in the user interface for the game.

So there we have it. The starting point for our agent's needs. We have some data. The next step, is to introduce a framework for the AI so that we can act on the data and satisfy the needs. Next time... "The Garden of Eden".

.Z.