In my previous article I’ve suggested a few scripting statements that could be used to specify interactions between actors and the board. In this post I am investigating a solution to bind these statements to the action graph in my underlying API.

Implementing interactions

If you followed the previous articles, you already know how ‘pseudo-scripted’ statements get into the action graph. First an object tree representing the script is created. I have added the following classes to support this:

• InteractionDef – Defines an interaction as associating an EventDef with several responses.
• EventDef – Base class for interaction events
  • ActorEventDef – Occurs when an occur performs a specified action.
  • EnvironmentEventDef – Occurs when an actor occupies/enters a given tile
  • CollisionEventDef – Occurs when an actor collides with an actor or prop.
• ActorResponseDef – A passive reaction (typically rendered as an actor animation)
• CapacityModifierDef – Used to capture disabling/enabling a capacity
• RoleModifierDef – Used to capture disabling/enabling a role
• PropertyModifierDef – Used to capture an increase/decrease to a property

The class hierarchy  could be a little more structured. Also, it seems that we may easily compress the same hierarchy later by considering similar node types. However, this is enough to render the current set of scripting statements provided by the Script class.

The next step is to feed those into the Interpreter class that will actually setup the action graph. I decided to provide ad-hoc classes to render interactions to the action graph. Compared to the design I earlier produced to model actor decisions, classes for interaction are more specialized – many of these nodes just can’t be put anywhere in the graph. This is more a change in the design than something that is specific to the problem being solved, so I guess I would take an opportunity to clean the overall design of the action graph API a little later on – it seems that using more particular types helps keep the action graph small and simplifies some of the design while offering straightforward optimization hooks. On the other hand, large, structured nodes offer less opportunities for reuse.

The class hiearchy for this looks like this:

• AffectMap – a list of affect bindings, i.e. event/response pairs (subclass of Action)
• AffectBinding – a list of event/response pairs
• AffectCondition – specialized subclasses implement interaction events
• Affect – specialized subclasses realize actor responses.

All reflex maps (see previous articles) should be processed before affect maps. Notwithstanding, it’s OK to use several reflex maps, either for each actor or for the same actor.

Unlike with ReflexMap, I decided to hold an Actor instance directly in the map and pass it to binding, condition and affect method calls, this prevents these ‘support classes’ from implementing Action, but saves memory (no need to store Actor pointers in each node) and  seems, overall, a better choice.

With this, my original draft for a behavior programming API and pseudo scripting interface is complete. Next time I’ll write a small test suite for this and hopefully I’ll then find time to discuss the overall design.

Recently, I started designing a game engine with a few simple goals in mind:

1. My game engine is concerned with managing a virtual world model. It is not an animation engine or a sequence/transition manager.
2. Although I developed a rough and ready animation API, the model must be separate from that API. This is so that I can later rewrite view using a 3D engine or whatever else.

I’ve been muddling a little bit with behavior programming. After ‘going dark’ for a few days I’ve decided to share my experience as I believe this could illuminate some design points.

Behavior programming – a draft API

A few important classes from the draft API:

• Condition – a condition is an object that returns a boolean value, so it has a (BOOL)check method.
• Action – an action is an object with a (void)apply method.
• ReflexMap – an action mapping a trigger (a Condition) to a response (an Action). When apply is invoked, the reflex map iterates the current action, if any. If no action is currently selected, ReflexMap iterates its list of triggers. The first satisfied trigger condition causes it’s response to become current.

As you can see, the API is based on objectified functions. This is a choice, maybe I’ll get a chance to explain why another time.

An example

Here is sample code used to program simple behavior for a guarding dog:

Actor* dog=[[Actor alloc]initWithX:0 y:0 z:0 tag:@"dog"];
//
Condition* outer=[[OnApproach alloc]initWithSource:dog target:@"human" range:60.0f];
Condition* inner=[[OnApproach alloc]initWithSource:dog target:@"human" range:30.0f];
Condition* close=[[OnApproach alloc]initWithSource:dog target:@"human" range:10.0f];
//
XAction* bark=[[ActorGesture alloc]initWithActor:dog action:BARK];
XAction* bite=[[ActorGesture alloc]initWithActor:dog action:BITE];
XAction* chase=[[MoveTo alloc]initMovingActor:dog to:nil];
//
ReflexMap* reflexes=[[ReflexMap alloc]init];
[reflexes add:bite on:close];
[reflexes add:chase on:inner];
[reflexes add:bark on:outer];

The @”foo” bits just represent strings (in case you’re not too familiar with Objective C). I use those strings as tags, so the @”human” tag allows OnApproach to only target human intruders (not rabbits, leprechauns and so forth…)

As illustrated by this code, although the idea of defining rules using conditions and actions seems OK at first, the design isn’t. The problem is that a Condition (in this case OnApproach) can be fulfilled in various ways. When the condition is fulfilled, we need to pass data to the action to effect it correctly. So in this case onApproach is fulfilled with a given target, but MoveTo cannot bind the target detected by OnApproach. Let’s try to fix this.

Binding precondition output to postcondition input – 1: using arbitrary parameters

My first impression is that the OnApproach condition should be replaced by an event call processed by a listener, so we’d have something like:

on:(Actor*)actor approaches:(Actor*) agent{...}

The downside is that doing this will require that we re-implement the event handling function for every trigger/response pair. We don’t want to write a new class for that every time. We do need to bind the output of the trigger to the input of the matching action. We might then change change the Action and Condition classes:

@interface Condition
-(BOOL)check; // unchanged. we need to return a boolean value anyway.
-(NSArray*)result; // OnApproach will place a reference to the approaching actor in this array.
@end

@interface Action
-(void)apply:(NSArray*)param // allows injecting data into the triggered action.
@end

We still need to tell ReflexMap which parameters to inject into MoveTo. So we change a function in ReflexMap:

add:(Action*)action on:(Condition*)trigger;

Now becomes:

add:(Action*)action with:(int[])params on:(Condition*)trigger;

And our reflexes are then setup as follows:

int[] args={0}; // addresses the only output from OnApproach

[reflexes add:bite with:args on:close];
[reflexes add:chase with:args on:inner];
[reflexes add:bark with:args on:outer];

This solves the problem, but lacks clarity because conditions and actions now return/accept arrays of arbitrary length and content.

Binding precondition output to postcondition input – 2: sharing placeholders

The next idea is as follows: what if we could arrange that whatever target defined by OnApproach is addressable using MoveTo?
To do this requires modifying both OnApproach and MoveTo. On the bright side, we needn’t change the Action and Condition signatures:

1. I defined an ActorRef class. ActorRef owns an Actor property (I could use a pointer to pointer, but that would be a little confusing).
2. OnApproach defines targetRef as an ActorRef instance. When a target is detected, targetRef.actor is assigned.
3. MoveTo also defines a targetRef property. When MoveTo is initialized, we pass the ActorRef instance owned by our OnApproach condition.

We can now change the original example as follows (skipping the bits that didn’t change):

OnApproach* inner=[[OnApproach alloc]initWithSource:dog target:@"actor" range:30.0f];
XAction* chase=[[MoveToActor alloc]initMovingActor:dog to:inner.target];

This seems to solve our problem nicely:

• Type safety isn’t compromised.
• The core interfaces remain simple
• The binding process doesn’t involve ReflexMap
• The code used to define our test script is simple and readable, compared to solution (1).

OK, enough for today then. Next time I’ll look into a way to further simplify behavioral scripts, as they are still a little heavy.

At this point, I have defined several classes that contribute to generating action graphs. An action graph is invoked at every frame. Roughly speaking, the action graph checks preconditions in the game world and applies post-conditions. Action graphs, however, are a little more structured and powerful than this given special constructs.

• At the root of the action graph, the main Transition defines several actions to be applied at every frame.
• A ReflexMap is an action that selects between competing responses in the presence of several stimuli.
• A GearSelector is an action that maintains and effects a priority driven agenda. The GearSelector can enable/disable an action on the agenda, independently of whether the action is current or not. GearSelector allows mixing long and short term goals as it can pause a lower priority action until a higher priority action is complete.
• Finally, XAction allows sequencing actions and using alternatives if an action fails.

All this stuff is fine, however, there are significant features of the action graph that can become problems:

1. The action graph must provide nodes on a per instance basis. For example, if a type of actor is associated with a reflex map, we need to provide a separate reflex map for each actor of this type. This is because different actors are in a different context, so they do different things.
2. Conditions often provide the basis for event driven behavior; however, conditions in the current implementation just return a boolean value. Often, even if a condition targets a specific actor, it can be fulfilled in various ways. We then typically would like to bind the matching event parameters in an associate postcondition.

Overall, it would be worth looking at this stuff from a more object oriented point of view, however we probably also want to keep objectified conditions and actions, because this provides a lot of flexibility at runtime.

How can we efficiently model high level game behaviors that are mostly dependent on ‘what goes on in the head of a NPC (non player character)’? In this article, I’m discussing approaches and sketching a model. I am mostly concerned about specifying in-game behavior concisely and correctly. If you want to apply what follows to an actual game, you’ll need to consider processing overheads, and scale behavioral models accordingly.

I started with three ideas in mind:

• Call a decision function at regular intervals. Whenever the function is invoked, the character checks their situation and issues an instruction regarding what to do next. I call this a ‘decision loop’ and this approach is common in many games that require simple behavior. The problem with a decision loop is that we need either doing a lot of book-keeping or reiterating many considerations every time. It’s not just memory or processing time. Practically, this approach is counter-intuitive to most people, and doesn’t scale up to complex behavior.
• We might layer several decision loops running at various speeds. The faster loops are used to take short term, tactical decisions. The slower loops are used to make decisions that are more on the long term. I find this idea quite attractive, but it would need to be developed to become practical – how do slow paced decision loops affect behavior? In a few trivial cases that might just involve carrying out a one-off action. In other cases, that could mean we need to make changes to faster loops. How do we translate ‘migrate to the south’ into the everyday behavior of a NPC?
• Have actors execute high level scripts or programs. The idea is to have a separate execution context for each actor. The script controlling each actor is structured like any program in C or whatnot and runs on a ‘lazy thread’, usually waiting for input describing the result of low level interactions in the game.
  Affording a separate thread dedicated to effecting an actor’s behavior could make it much easier to specify and implement such behavior. However, we may not be able to use whatever language the game is written in to specify behavioral scripts, or maybe not very directly. Also, it’s not too likely that we can allocate system/native threads to our actors (I’ll come back to these issues in a later post).

OK, I’m not trying to write ‘regular AIs’, just NPCs. So the main problem can be divided in two questions:

1. What is/are convenient ways to specify the behavior of NPCs.
2. What do such specifications entail – what kind of software do we need to write so that the NPCs will behave according to the specification?

An example

I take the example of a farmer. Every day, they get up, get dressed, go to the field. They work in the field until twelve and then meet their wife near the well for a snack. Afterwards they work some more and go to the pub at the village. Once they are drunk they go home, undress (if able to) and sleep (A).

This doesn’t cover all the many behaviors of a farmer. Some examples:

• They could find a pot of gold while digging and decide to become a banker (B)
• They could encounter an aggressive animal while working. Then probably they would run and / or defend themselves (C)
• It could be raining hard, so they would go back home (D)
• If it rained the day before, they would try to avoid a puddle if they spotted one (E)

Script (A) is simple and linear. Starting from low level actions (move, plough, get dressed, drink, buy, sit…) that can be rendered as animations in a game, we would need to build each part of the script. That may seem a lot of work, but if we break down each part, we’ll soon find that we can reuse subscripts not just for this particular character but also for other characters. Also, I would argue that even a moderately realistic effort in this direction could make many games a lot more fun – after all, so many games have static NPCs, or NPCs that can handle only very restricted situations (e.g: shooting).

If we’re specifying script A, I would argue that many languages would do, ‘assuming we could use them for that purpose’. In other words, we would feel comfortable writing a program, maybe in C, Python or Javascript (many languages would do) that describes ‘a farmer’s day’ using a main procedure and it’s sub-functions. That would be more intuitive and definitely faster than implementing a decision function that gets called every time and representing the situation explicitly.

But then, surely we wouldn’t want to mix B-E with script A. This stuff could happen at any time and would need to be taken care of in priority. So we probably need.

• Detection routines or notifications to trigger a response to unexpected occurrences.
• A mechanism used to override a ‘main script’.

The actual specification of B-E could use a mechanism similar to script A, so it seems we have all the ingredients to offer a workable model.

Our model

Here’s the proposed model:

1. The high level behavior of each character is defined by a set of scripts (To run these scripts, we may need a special interpreter).
2. Scripts are arranged by priority. A higher priority script can override a lower priority script if needed – for example, fighting for life is more important than avoiding a puddle, so a ‘puddle event’ is ignored in the middle of a fight.
3. A script can be attached to a condition that triggers the script. The script won’t actually take control of the actor unless it has suitable priority relative to the current script.
4. A script can be invoked externally as a side effect of something else going on. Again, invoking means ‘attempting’. Another character might attempt starting a conversation with an actor under attack. That won’t actually start the conversation script.
5. Once a script has completed, the interrupted script may resume, or maybe another, pending, higher priority script may start.
6. Under special circumstances, a script may replace another (for example, our farmer can become a banker). This would probably require tagging scripts – the farming script is ‘occupational’, banking goes in the same category.

Needless to say, this can be improved in many ways – for example we may need to define ‘yield points’ – points at which it is graceful or safe to override another script… and so forth.

Pending, I would be very curious to hear about APIs allowing to do this or something similar… So please don’t hesitate to reply to this post if you have any idea.