An Introduction to the Memetic AI Toolkit

Goals and Motivations

I built this framework to be used in a long running multi-player online campaign. It is designed to construct resilliant NPCs who survive for weeks or months at a time - not minutes or hours. Its purpose is to be the cornerstone of a very dynamic environment. Here are some of the starting ideas that motiviated the creation of this toolkit:

The intelligent behavior of all creatures can be built from building blocks.
Behaviors should be scheduled, activated, or prioritized during the course of the game.
Behaviors should be dyanmically built, shared or destroyed during the course of the game.
A resilliant scheduling system should allow for diverent behaviors to reassert themselves whenever possible and fall back to base or normal routines, automatically.
Internal routines like looking around, examining internal state, should be possible without interrupting the normal behaviors.
Behaviors should be generated in response to general situations, internal and external stimuli.
Behaviors should be proposed and compete; only the best course of action should be followed.
Creatures should be able to communicate internally and via channels to pass a variety of data - basic inter-creature-communication.
It should be interesting, practical, direct; a close approximation to an a-life toolkit...

To accomplish these goals, I needed a vocabulary to described the system. It had to make sense and should be easy to use in an average conversation. (Programming with a good metaphor causes things to be implemented because they seem natural, predictable, and cohesive with the desgn goals.) Overall, a good design is a must - the implementation of Memetic AI had to be modular, extensible, and abstracted in a way that is easy to code and use.

Memes

When a bear walks through the woods, what goes through its mind? This is the sort of question I ask myself when I'm designing a memetic behavior. Does it stop to eat berries, mark its territory, assess the other creatures or take a nap at night? Surely the bear considers many such behaviours and chooses one course of action. But how do you encode this in a general, reuseable way? You build a behavioral model.

How do you build a behavior model in Neverwinter Nights? You use memes, generators, and events...

By now you should understand that a meme is a fancy word for a predefined behavior. From a programmer's perspective, you might say that a meme "encapsulates a behavioral subroutine". The simplest meme may perform a single action like "say something" or "walk somewhere". While more complex memes may implement: "flank and attack", "walk the Amber Trade Route", or even "socialize".

Using Memetic AI, every NPC may hold a number of memes waiting to get their chance to become active. When a new meme is created, reprioritized or finishes, another may get its chance to execute. NPCs are always acting according to their memes; stopping when every meme has run its course.

Now compare this to the default system provided by Neverwinter Nights:

The Neverwinter Nights' system enqueues each action performing step after step until something critical occurs, like combat. Their scripts then call ClearAllActions(), immediately losing any queued behavior. The trouble with this is should be obvious - all state is lost. Bioware has made a few provisions for walking by calling WalkWaypoints() but in general it's a rather rigid, hardcoded AI.

Priorities and Modifiers

Every meme has a priority: very high, high, medium, low or none. Within the priority band, every meme has a modifier from +100 to -100. Only one meme is allowed to be active a time and this is choosen automaticaly based on the priority. Those memes with no priority are ignored, considered to be dormant. As a meme becomes active, its code has control of the standard NPC action queue. It can reliably make calls to ActionDoCommand(), controlling the NPC immediately.

Prioritized Memes in Action

Once a meme is created, its priority may be changed at any time. The highest priority is always executed. At this time, if a set of memes have the same priority and modifier, the first one with the priority will be executed followed by the next one, and so forth until there are no more memes of that priority.

Instance Lifecycle

But a memes' life can be much more than a single command. In fact some memes may not make sense if they are interrupted; cutting their lives short makes sense. Others never intend on stopping their behavior and repeat endlesslesly, regardless of interruption. Finally, some memes are proposed, but never created unless they are high enough to execute. These behaviors are described when a memeis constructed, by using meme flags:

MEME_PERSISTANT: This meme shouldn't be destroyed when it's done; rerun it over and over again.

MEME_RESUMEABLE: This meme can be interrupted and should resume whenever possible.

MEME_IMMEDIATE: This meme will immeditaely execute without interrupting any ongoing behaivors.

MEME_INSTANT: This meme will only execute if it has the highest priority -- can it go in the next instant.

Whatever their purpose, all memes have an opportunity to execute code throughout their lifecycle. Each meme consists of a set of scripts. The script name is composed of the meme name and a suffix that corresponds the the timing. For example, if we have a meme called "i_walk" you may see the following meme instance scripts:

i_walk_ini: This is called before the meme is started. This gives a meme an opportunity to initializes data and clean up its internal data structures. A developer might choose to reuse a single behavior. To support this, the initialization routine must clear stale data and assume this meme was previously executed.

i_walk_go: This is called when the meme is started. Generally this is where the meme adds actions to be executed. Go scripts may be called multiple times, in the event that the action queue is lost.

i_walk_end: This is called when the meme has successfully completed its behavior. If the meme cycles endlessly, this is still called, but i_walk_go will be called immediately after this script is over.

i_walk_brk: This is called whenever another meme interrupts the i_walk behavior, before it ends. If the i_walk behavior is allow to resume, i_walk_go is eventually called. If not, the meme is immediately destroyed. This is not called if an immediate meme executes; the _go function is called to resume the behavior.

Using Meme Instances

You can create a meme and add it to an NPC at any time. But usually, it's not enough to create just a meme with a name. You'll need to create a meme and attach a number of variables on the meme object. Once its created, a call to the memetic function, Me, will start the system in motion.

So for a simple behavior you can call MeCreateMeme() and MeUpdateActions() from within the Neverwinter Night's OnSpawn callback function. This will initialize the creature to use Memetic AI and will start its behavior, accordingly.

Generator

By now you should understand that a meme is a fancy word for a predefined behavior. From a programmer's perspective, you might say that a meme "encapsulates a behavioral subroutine". The simplest meme may perform a single action like "say something" or "walk somewhere". While more complex memes may implement: "flank and attack", "walk the Amber Trade Route", or even "socialize".

Using Memetic AI, every NPC may hold a number of memes waiting to get their chance to become active. When a new meme is created, reprioritized or finishes, another may get its chance to execute. NPCs are always acting according to their memes; stopping when every meme has run its course.

Now compare this to the default system provided by Neverwinter Nights:

The Neverwinter Nights' system enqueues each action performing step after step until something critical occurs, like combat. Their scripts then call ClearAllActions(), immediately losing any queued behavior. The trouble with this is should be obvious - all state is lost. Bioware has made a few provisions for walking by calling WalkWaypoints() but in general it's a rather rigid, hardcoded AI.

Priorities and Modifiers

Every meme has a priority: very high, high, medium, low or none. Within the priority band, every meme has a modifier from +100 to -100. Only one meme is allowed to be active a time and this is choosen automaticaly based on the priority. Those memes with no priority are ignored, considered to be dormant. As a meme becomes active, its code has control of the standard NPC action queue. It can reliably make calls to ActionDoCommand(), controlling the NPC immediately.



Prioritized Memes in Action

Once a meme is created, its priority may be changed at any time. The highest priority is always executed. At this time, if a set of memes have the same priority and modifier, the first one with the priority will be executed followed by the next one, and so forth until there are no more memes of that priority.

Instance Lifecycle

But a memes' life can be much more than a single command. In fact some memes may not make sense if they are interrupted; cutting their lives short makes sense. Others never intend on stopping their behavior and repeat endlesslesly, regardless of interruption. Finally, some memes are proposed, but never created unless they are high enough to execute. These behaviors are described when a memeis constructed, by using meme flags:

MEME_PERSISTANT: This meme shouldn't be destroyed when it's done; rerun it over and over again.

MEME_RESUMEABLE: This meme can be interrupted and should resume whenever possible.

MEME_IMMEDIATE: This meme will immeditaely execute without interrupting any ongoing behaivors.

MEME_INSTANT: This meme will only execute if it has the highest priority -- can it go in the next instant.



Whatever their purpose, all memes have an opportunity to execute code throughout their lifecycle. Each meme consists of a set of scripts. The script name is composed of the meme name and a suffix that corresponds the the timing. For example, if we have a meme called "i_walk" you may see the following meme instance scripts:

i_walk_ini: This is called before the meme is started. This gives a meme an opportunity to initializes data and clean up its internal data structures. A developer might choose to reuse a single behavior. To support this, the initialization routine must clear stale data and assume this meme was previously executed.

i_walk_go: This is called when the meme is started. Generally this is where the meme adds actions to be executed. Go scripts may be called multiple times, in the event that the action queue is lost.

i_walk_end: This is called when the meme has successfully completed its behavior. If the meme cycles endlessly, this is still called, but i_walk_go will be called immediately after this script is over.

i_walk_brk: This is called whenever another meme interrupts the i_walk behavior, before it ends. If the i_walk behavior is allow to resume, i_walk_go is eventually called. If not, the meme is immediately destroyed. This is not called if an immediate meme executes; the _go function is called to resume the behavior.



Using Meme Instances

You can create a meme and add it to an NPC at any time. But usually, it's not enough to create just a meme with a name. You'll need to create a meme and attach a number of variables on the meme object. Once its created, a call to the memetic function, Me, will start the system in motion.

So for a simple behavior you can call MeCreateMeme() and MeUpdateActions() from within the Neverwinter Night's OnSpawn callback function. This will initialize the creature to use Memetic AI and will start its behavior, accordingly.





At this point it should be clear that once a meme is created it has a good chance of executing. But it's rarely practical to predefine every behavior in the OnSpawn callback. It's much more practical to create memes on demand through the use of meme generators. Generators are activated in response to any of the standard Neverwinter Nights callbacks and usually call MeCreateMeme() to react to the situation.

A generator may have a priority and modifier much liike an instance of a meme. This priority is only used to determine priority of the meme it creates. Thus, if a generator has a high priority it will create high priority memes.

It's important to understand that a creature may have many generators.

All of these generators are run according to the external stimuli. In contrast, a creature may have many memes, but only one is ever active at a particular moment.

External Stimuli

All NPCs have standard callbacks to response to external stimuli. The memetic AI toolkit supplies replacement scripts which automatically call generators instead of hard-coded subroutines. Each generator script is executed with the generator name and the suffix which corresponds to the external stimulus. For example, if you had an amazingly complex "i_attack" meme generator, you may see the following eleven scripts:

g_attack_hbt: Heartbeat; called every four to six seconds depending on if there are players present.

g_attack_blk: Block; the creature has met a door, blocking its path.

g_attack_cbt: End of Combat; the creature was previously in combat and the round has ended.

g_attack_tlk: Talk; the creature has heard something or a player is trying to initiate a conversation.

g_attack_dmg: Damage; the creature has taken damage.

g_attack_dth: Death, the creature has died.

g_attack_inv: Inventory Disturbed; something has been added or removed from the inventory.

g_attack_see: Perceived; something new can be seen.

g_attack_van: Perceived; something has just vanished.

g_attack_hear: Perceived; something was just heard.

g_attack_ina: Perceived; something is now inaudible.

g_attack_atk: Attack; the creature has been attacked.

g_attack_rst: Rest; the creature has just finished resting.

g_attack_mgk: Cast Spell; the creature was the target of a spell.



Using Generators

Similar to memes, you can create a generator and add it to an NPC at any time. An active generator will immediately sensing its environment and reacting. With a handful of generators, an NPC can be built with a complexe, reactive behavior. Each generator may be configured to your liking. For example, a combat generator may have options to adjust who, what, when and how the NPC attacks. By adding multiple combat generators, multiple tactic memes may be created and compete to calculate the best course of action by the adjusting their priorities at the end of every combat round.





Unfortunately, writing a meme for every conceivable behavior gets a bit tedious and is quite impractical. Many times is simplest to chain several memes together into a single sequence.



Sequences have a priority, like any other meme. Its priority may be fixed or based on the memes it contains. When it has a priority higher than any other behaivor, it executes its memes in sequental order -- not based priority. When a sequence is interrupted by a higher priority meme, it has the option of resuming at its last position or at a meme within the sequence which has been marked as a sequence checkpoint.



Overall, sequences move us closer to our goal to allow builders to use memes as building blocks. As libraries of memes are developed, generators may spawn off complex sequences of behaviors and module builders will dynamically chain behaviors based on the player's involvement in the game.





The Memetic Toolkit uses an improved event system. Any script may send a signal or trigger an event within a memetic NPC. The event may do whatever it likes: evaluate the situation, create a meme, or even fire off other signals. In operating system terms, an event acts like a thread, independent of the NPC's normal activity.

Events are activated in response to triggers. Time triggers are a scheduling mechansim, saying when the event should activate. Signal triggers are a more immediate activation, possibly hear by many events within one or many NPCs.

Signal Triggers

Memetic signals can be broadcast internally or to a host of NPCs via a channel. The channel broadcast mechanism is unrelated to geography, it is a game-wide subscription system for any NPCs. Contrary to the standard NWN signal system, when an event is triggered by a memetic signale, it receives the signal id, the source of the signal, and integer, string or object data.

Time Triggers

Automatically activating an event at a specific time allows NPC to schedule recurring behavior. For example, to avoid using the heartbeat callback, an event with a recurring time trigger can be set up. As a result, you can adjust the frequency of a polling loop or perform internal maintenance, on demand.





Without a doubt, this is a lot of information to digest in one sitting. Please take some time to think about this architecture. It is now at a point where people can begin to build modular behaviors and assemble reusable NPCs. I hope I've given you enough information to feel more comfortable reading the APIs and experimenting with the sample modules. It is my firm belief that systems such as this one will be necessary for the future of online NPC AI.
www.memeticai.org