Today is time for part five of the occasional series, ‘a Tour of Epitaph’. Today I wanted to talk a bit about out combat AI system, mainly because it came up a while ago and I had forgotten so much about how it works that all I could say when people said things was ‘It does that? That’s pretty cool’. So, partially as a tour and partially as a reminder for me, that is today’s topic.

AI in combat is a make or break issue for games with significant amounts of fighting. It is what turns a game from Operation Wolf[1] into Half Life – while never going to be something that can create endless variety and enjoyment, a good AI system will prolong the life of a combat game longer than the mechanics strictly justify. An AI system will never match a skilled player, but add in enough variety or mechanics, enough risks to a player of accomplishment, and an AI capable of making use of those mechanics, and you’ve got yourself a package on which you can variate constantly to achieve player challenge. If you update the AI engine, you create new playing experiences that can keep everything fresh.

Long ago, before I did my PhD in accessibility, I was a research assistant working in the field of artificial intelligence – specifically I was building a bi-modal search system combing genetic algorithms[2] with next ascent hill climbing[3] to explore intractably large search spaces. I have a long time fascination with topics in AI, and this fed into my doctoral work through the development of an accessibility engine based on reinforcement learning via user feedback. I’ve got a reasonably good grounding in the way in which these techniques work and how they can be applied, is what I’m saying, and as such I have thought quite a lot on how to make the best AI system for Epitaph.

AI in MUDs offer a number of very specific challenges that limit just how effective standard routines can be:

* Processing time per unit is restricted and must be rationed
* Time over which an agent can learn is limited
* Pooling learning is ineffective because of the number of players with which an NPC will interact

It’s different for a single player game where optimisations can limit the number of calculations required ‘off camera’ – we may have hundreds of cameras at any one time. We may (potentially) have dozens or hundreds of players who are interacting with the game, and our CPU and memory limits can’t be ignored. So, we can’t simply throw processing at the problem. You will undoubtedly notice that the ‘AI’ in large scale games like WoW is so primitive as to be laughable – the resource costing of anything else is an important reason for that.

NPCs in the game have a very short ‘useful’ lifetime on the whole – they’re either wandering around, not interacting with players, or they’re in combat and about to be dead (or victorious) very soon. We can’t realistically have an NPC learn ‘on the job’ because that job will be over in seconds[4]. There are various techniques that can make an NPC adapt to the actions of a player, but generally they require time to learn and we don’t have that.

One way around that is to have ‘micro lessons’ which get fed into a single learning engine. NPCs might feed in the single most important thing they ‘learned’ – ‘when I lie down and cry as my first action, I died 3 seconds later’, or ‘when I went into a defensive stance I died in 32 seconds’, and this can serve as the basis for evolving behaviour as time goes by. The problem there is that it is an intensely gameable system. ‘Okay guys, let’s all stand with our backs to the NPC so that they think just lunging and clawing is the most effective strategy’, and then a week later ‘NOW TURN AND KILL’.

The combination of limited resources, limited learning time, and the ineffectiveness of pooled learning have a number of consequences for the way in which our NPCs can realistically demonstrate actual artificial intelligence[5].

So, what do do? Well, the simple answer – let’s not worry about them being actually intelligent and insteadworry about them being fun to fight.

So was born the behaviour system – a simple, modular vehicle for installing combat behaviours into NPCs. For this, I wanted to accomplish several goals:

* Behaviour completely independent of the code – no hard-coded assumption.
* Combat behaviours that could be fluid and change as the situation demanded
* Combat behaviours that were *contextual* – only actions that made sense in the context of the current scenario would be performed
* Had to limit code repetition
* Had to be able to hook into existing game events

We inherited an NPC AI system, of a sort, from the DW lib – the Smart Fighter system encompassed a lot of functionality that would make an NPC challenging to fight. They executed specials, ran away from spells, cast rituals – a whole shebang of things. However, it was built entirely around a conception of combat that was inextricable from its context. It was very much a ‘Discworld AI system’. So, that was no good – even if I had recast it all for Epitaph, it would have just meant the next game built on the Epitaph engine would have to do the same. The first deliverable of the system then was that it would be a framework into which specific actions could be inserted via config files[6]. The behaviour system would define how config details were to be interpreted, but would make no assumptions that were not part of the core functionality of what is now the Epiphany lib. Thus, it can’t assume specials will work in a particular way, it can’t assume that one kind of attack is good in one kind of situation – none of that can be part of the engine, that has to be handled in config files.

The nature of the config files too imply an understanding of a particular context – rather than requiring behaviour files to be fully comprehensive (including routines for melee/ranged and unarmed fighting) they can be more focused – an AI module may focus only on ranged combat for example, and when that is no longer sensible (a gun broke or the NPC ran out of ammo) it then switches into a behaviour that is more appropriate (melee or unarmed combat). This works tremendously well in my experience, leading to great narrative combats such as an old woman blasting with her shotgun, backing away as you attempt to approach, reloading, blasting again and then throwing her shotgun to the ground and drawing her machete when the ammo runs out. However, the fact that she has a shotgun doesn’t guarantee any of this – at some point she may simply get in close and start beating someone with the butt of it even if she has ammo left. That’s all intentional – no matter how effective the strategy an NPC may employ, predictability is the bane of exciting game play.

Contextual actions are at the core of the system, and they work through chains of pre-requisites. At each stage of combat, the NPC works its way through each possible action checking the prerequisites. These may be things like ‘do I have a ranged weapon? Is it loaded?’ or ‘do I know the kick command? Is it on cooldown? Am I in a position to kick?’. Assuming all prerequisites are met, the action (or chain of actions) is added as a possibility for the next round of combat and one is chosen at random.

Having all of this coded into behaviours is fine, but it creates a maintenance problem in that particular kinds of actions (what do I do when I’m on fire, for example) are going to be very common and requiring them to be implemented into the behaviour means potentially a lot of code duplication. So, to get around that the system supports behaviour modules that can be set up – ‘this behaviour gets the following fixed modules’, ensuring complex functionality can be shared between behaviours whilst also limiting the code repetition.

Finally, in order for the behaviour to be genuinely interesting it had to be able to respond to all kinds of things happening – drawing a weapon when considered, becoming especially observant when a door opens, burning the body when they’ve killed something – all of that requires an event driven lib (which we have) and hooks in all of those events to execute actions. We don’t have them *all* hooked up yet, but the framework is there to make that easy to do at all times.

It is, I think, a pretty great system that is only going to become better as more behaviours are added. It does have some drawbacks though, and the biggest one is the barrier to entry in development. It’s built around function pointers from balls to brains, and if you can’t think your way through lists of nested function pointers you’re not going to be able to make an interesting behaviour.

Let’s look at a simple example of a behaviour – this is for a ‘frightened’ NPC:

::item “frightened”::
::->minimum_time_between_specials:: 30
::->energy_in_reserve:: 500
::->preferred_position:: POSITION_STATE_SCRUM
::->duration:: 60
::->combat_actions_modules:: ({
“basic attacks”
})
::->combat_actions:: ([
])
::->on_consider:: ([
(: !sizeof ($1->query_current_weapons()) :) : (: $1->draw_weapons() :),
(: sizeof ($1->query_current_weapons()) :) :(: $1->do_command (“attack ” + file_name ($2)) :),
])
::->applied_state:: ([
(: 1 :) : ({
(: $1->init_command (“: eyes the corpse.”, 1) :),
(: $1->init_command (“‘ Oh… my… fucking… God!”, 2) :),
}),
(: 1 :) : (: $1->init_command (“tactics stance defensive”, 3) :),
])
::->remove_stealth:: ([
(: sizeof ($1->query_current_weapons()) :) : (: $1->do_command (“attack ” + file_name ($2)) :),
])
::->targeted_modules:: ({
“dodge firearms”
})
::->ongoing:: ([
(: 1 :) : (: $1->do_command (“shout Help! I need help!”) :),
(: 1 :) : (: $1->do_command (“lsay We’re in danger! Help! Help!”) :),
])
::->event_triggers:: ([
“observed corpse of my race” : 10,
“observed corpse of zombie” : 5,
“startled” : 1,
])
::->extra_look:: “$C$$pronoun$ looks very frightened.\n”

Some of the fields are pretty self explanatory – the first one that needs a proper introduction is ->combat_action_modules, and that relates to the module system I outlined above. In this case, what it says is ‘get all the behaviours defined in that module’, which looks (in part) like this:

::item “basic attacks”::
::->bits:: ([
(: $1->query_is_pinned () :) :
“struggle”,
(: 1 :) : “kick $target$”,
(: 1 :) : “headbutt $target$”,
(: $1->effects_matching (“damage.health.burning”) :) :
“extinguish self”,
(: !sizeof ($1->query_current_weapons()) :) : “punch $target$”,
(: $2->query_prone() :) : “stomp $target$”,
({
(: $1->query_known_command (“sweep”) :),
(: $1->query_prone() :),
}) : “sweep $target$”,
({
(: $1->query_known_command (“subdue”) :),
(: $1->query_prone() :),
}) : “subdue $target$”,
({
(: $1->query_known_command (“smash”) :),
(: sizeof ($1->query_current_weapons()) :),
(: $1->query_valid_attack_for_current_weapon (“blunt”) :),
}) : “smash $target$ with $weapon$”,
])

This creates a number of combat actions and installs them in the NPC, without us needing to define them in the base behaviour. If we need to change these, they change in the module and they change for all behaviours that make use of them.

->on_consider and ->remove_stealth are examples of event hooks – event_consider and event_remove_stealth trigger these actions. In this case, being frightened means that they are in a heightened state of aggression – if they are considered and have no weapons drawn, they’ll draw a weapon if they can. If they have a weapon out, they will attack. Similarly if you startle them by coming out of stealth beside them, they’ll launch into an attack.

->applied_state contains actions that are performed when the NPC moves into this behaviour – in this case it’s linked to ->event_triggers. Some behaviours are shifted into naturally based on meeting pre-requisites for the validity of the behaviour. Others are based on things that happen to the NPC – the event triggers show the chances that an NPC moves into this state upon certain game events (such as generally being startled, or seeing a new corpse).

->ongoing events occur every so often, and in this case add a certain peril to the NPC being around – shouting will attract the attention of zombies, as will loud says.

As you can see from all of this, function pointers are core – that’s true of a lot of the Epiphany lib[7], but it’s especially true in systems like this and our scenario system (a topic for a later blog). Any creator could create an achievement, or a quest, or a crafting pattern, or any number of other things. Adding in new behaviours is going to be something with which fewer developers feel comfortable. That’s problem one, but the relative rarity by which AI behaviour needs to be added or changed mitigates it a little.

A secondary problem with the system is it is not very flexible for real-time changes. FluffOS class limits mean that we have some issues in injecting behaviours *into* NPCs, and the heavy focus on function pointers means that once the thing is loaded up we can’t change all the behaviours without desting all the NPCs (because of function pointer ownership). It’s not a problem for *us* because we can dest all our NPCs on a whim on our development server (which is the only place this kind of development will be done), but for a MUD with a less flexible architecture, that is going to be an issue. Happily, it’s also an issue that is very easily solved when someone manages to crack the nut of class limits. For now, it doesn’t create any problems for us, so it’s an issue I can live with.

This system gives us the *appearance* of dynamic NPCs with adaptive behaviour, but the main difference between this and a real AI system is it’s all heuristic based. The NPCs are only as good as the behaviours that we define and they are never going to exhibit behaviour that is genuinely unexpected. Luckily, the system is flexible enough that we *can* define *very* good behaviours. Whether we actually manage to achieve that remains to be seen, but all the tools we need are right there.

Drakkos.

[1] No, apparently I *couldn’t* have picked a more recent example. That’s how old I am.
[2] A kind of search heuristic
[3] Another kind of search heuristic.
[4] I assume here that combat is not supposed to be an affair to which a packed lunch must be brought.
[5] I do have some ideas for using a genetic algorithm and NPC combat data as a kind of ‘special zombie generator’. Maybe I will talk about those in a later post.
[6] One day I will write a long devotional poem to Jeremy@Discworld for the data handler he wrote way back in the dawn of time.
[7] It’s almost certainly never going to be a ‘newbie friendly’ lib because of this.