NPC ACE - NPC Advanced Control Engine

http://www.tesnexus.com/downloads/file.php?id=20878 - File "QQuix Conceptual - NPC ACE - Anvil Docks - Beta 0_1"

I've just finished this 'engine' to control NPCs and plan to release it later this month.
The engine itself is fully developed, but I still need a few weeks to complete the mod where I am using it.

I had the need for this engine while planning my The Evolving Society engine and decided to develop it as a stand-alone building block to be used later in the main project, but this time I decided to release the scripts in a playable mod (instead of proof-of-concept mod).
The engine is designed to have an exclusive, complete control over a group of NPCs. I suppose it can be adapted to control vanilla NPCs, but I did not put too much thought on this.

Follows a description of the engine. Hope it may be helpful to someone or, at least, raise some interesting discussions.


Main objectives
? Allow for new kinds of activities, beyond the standard AI packages (Find, Wander, Travel, etc)
? Allow for activities involving more than one NPC (Buy&Sell, dating, etc)
? Provide more elaborated ways to organize activities (as opposed to the standard AI package selection criteria)
? Have things happening when the PC is not around (NPCs are not in a loaded cell)

Initial comments
? Most of the following text describes the present implementation of this engine. Variations are (hopefully) easy to create, based on the initial code.
? All concepts presented here are public resources. Feel free to use them in total or in part, without asking for permission. Same goes for the code, when released



THE ACTIVITY SELECTION SYSTEM

Each NPC has a list of daily activities he may want to perform.

Each activity may be performed multiple times every day and has a minimum and maximum number of times it can be selected per day.

The list of activities has some similarities with an AI package list, but has a completely different selection algorithm.

An example may help here:
A city guard activity list might look like this
? Sleep for 7 hours - at least once a day - Max: once a day
? Patrol for 2 hours - Min: 3 times a day - Max: 5 times a day
? Drink at the bar for half an hour - Min: 0 - Max 3
? Chat at the bar for 1 hour - Min 1 - Max 2
? Wander around town for 20 minutes - Min 1 - Max 3
? Dinner with family for 1 hour - Min: 1 Max: 1

Every time an NPC finishes an activity, he picks a new one from the list, based on the result of the activity selection algorithm.

The selection algorithm is composed of a number of advisor/voter functions. Each function anolyses each activity and rates it based on a specific criteria.

The final selection is based on the combination of the 'opinions' of all the advisors.

Each activity also has a few attributes to be used by these functions, like location, ideal time of day, etc.

Implemented functions:

? Daily activities
Objective: make sure the NPC performs each activity a number of times within the Min and Max counts.
Votes high for activities that are below Min, low/negative for activities at Max and medium (interpolated) for other cases.

? Flow
Objective: prevent too many NPCs going to the same place at the same time.
Each activity has a Location attribute specifying where it takes place (Bar, Home, Town, etc). If here are very few NPCs at the Bar, this function will vote high for "Drink at the bar" and "Chat at the bar" and vice versa. Being mostly concerned with public areas, this function votes neutral for activities that takes place in private (like sleeping)

? Time of day
Objective: make things happen at the 'proper' time.
Votes low or high based on the activity and time of day. E.g. votes high for Diner at evening and Sleeping at night.

? Sequence
Objective: prevent selecting the same activity twice in a row and/or force a sequence
Votes negative for the activity that have just finished. Or votes to increase the chanco of some activities been selected in a sequence. E.g. drink at the bar, go home for dinner, go chat a bit with friends, go back home to sleep.

? Location
Objective: prevent the next activity being at the same location as the previous.
If two activities occur at the same location, like "Drink at the bar" and "Chat at the bar", you may want to prevent them from being chosen back to back. May be used to force it, instead of preventing it.

Many other voters may be created to fulfill specific needs. For example, I have an NPC that is supposed to do something at the bar at 6:00 PM. As the time approaches, there is an additional function that votes dramatically high for any activity at the bar and votes negative for everyone else. But only for that particular NPC, of course.

The votes are actually statistical chances of each activity being selected. All votes are combined and normalized, so all positive votes add up to 100% and negative votes add up to -100%.

Voters may also be weighed, giving different 'importance' to each criteria

At the end, the guard list may look like this:

? Sleep - (-50%)
? Patrol - 55%
? Drink at the bar - 20%
? Chat at the bar - 15%)
? Wander - 10%
? Dinner - (-50%)

Then an activity is selected base on the positive odds. In the above example, there is a 55% chance of Patrol being selected as the next activity.

There is also the possibility of forcing a new activity on an NPC, bypassing the described selection system. One activity on one NPC may need to force an activity on another NPC. For example, if the guard selects "Dinner with family", the process may force a similar activity on other members of the family, so they all arrive at the dinner table about the same time.

This algorithm creates a (kind of) more realistic decision process for NPCs, so they do not act as robots. They will, instead, decide differently each day (within imposed limits).



STAGES

Each activity is composed of one or more stages

An example up front may help: Let's use the "Chat at the bar for 1 hour" activity and break it down into its stages:

Stage 1 - Go to bar - the NPC will head for the bar (20 minutes)
Stage 2 - Select partner - NPC selects one of the presents to chat with (0 minutes)
Stage 3 - Go to partner - NPC approaches the selected partner (5 minutes)
Stage 4 - Chat - NPC starts conversation with partner (60 minutes)

When an activity is selected, the stages are played in sequence, one after the other. When the last stage finishes, the activity is done and a new activity will be selected as described earlier.

Duration:
The duration is actually an attribute of the Stage (and not of the Activity, as implied earlier)

Each Stage has a specified duration and a deviation value. If the Chat stage has a 60 minute duration and a 10 minute deviation, the engine will randomly pick a duration between 50 and 70 minutes. The deviation value may be zero.

The resulting duration plays a major role in the engine.

For this development, I self-imposed a challenge to create a NO-gamemode engine and implement an event-driven approach. The duration attribute allows the engine to 'forget about the NPC' during that period. When the time is up, a timer sub-engine (described later) generates an event that causes the engine to reevaluate the situation and react accordingly.

Let's anolyze the "Go to Bar" stage:

When the stage starts, the engine adds a Travel package to the NPC.

If the NPC arrives at the destination before the time expires, the OnPackageEnd block will generate an event that will finish the stage and the NPC goes to the next stage.

Otherwise, what happens when the duration expires (20 minutes, in this example) depends on the location of the NPC and player at the moment. Meaning, whether the NPC is in high level processing or not.

There are some possibilities:
(The description below is an example of how to react when time expires on a GoTo kind of stage. Other types will/may have different reactions, of course)

1 - Player and NPC are in the bar - Do nothing - give the stage some additional time to complete the action
2 - Player is in the bar and NPC is not - Force the NPC into the bar by making it activate the door to the bar, so he arrives normally (although a little late, maybe)
3 - Player and NPC are in the same area outside the bar (e.g, the PC is just outside the bar and the NPC is coming down the street) - Do nothing - give the stage some additional time to complete the action.
4 - Player is somewhere else - just move the NPC to the final destination, consider the stage completed and move on to the next stage.

This 4th scenario allows for the "virtual life" described later.



EVENTS

Each stage is event driven and reacts to them accordingly.

The Timer event generated by the timer sub-engine has already been mentioned. Other common, implemented events are:
- Start
- End
- Suspend
- Resume
- ActorAtMark
- A few others quite specific to the mod I am using for development

START
When a Stage starts, the engine triggers the stage code with a Start event.
This is used to initialize the stage with whatever is necessary. Typically selecting and adding an AI Package or adding a token to the NPC

END
The last event before finishing the stage. Not that useful.

SUSPEND
Happens the PC leaves the cell (generated by scripted doors). Useful to stop any heavy processing that may be going on.

RESUME
Happens the PC enters the cell (generated by scripted doors).
Under many circumstances the Start event does nothing if the player is not in the same cell. It just marks the Stage as "Start delayed". In this case, the Resume event either triggers the actions that would have been triggered by the Start event or, depending on how far we are in the duration, pretends the stage has already finished.
Also useful for repositioning NPCs when the player enters an interior cell, as the game engine has a nasty habit of positioning NPCs at odd places on occasion.

ActorAtMark
Typically generated by the OnPackacheEnd block activated when an AI packages completes

At the end of the event processing, it returns a value with one of the following alternatives:

- Not finished yet. Give me X additional minutes
- Stage finished
- Abort this activity and select a new one (e.g. if the NPC does not find a partner to chat with at the bar)
- Abort this activity and do not select a new one (used when a new activity has already been forced on the NPC)



THE TIMER SUB-ENGINE

Every stage has a time limit, either the initial duration or additional time set by event processing.

The Timer sub-engine is responsible for generating a Timer event at that particular moment.

All controls are based on a timestamp representing the time elapsed since the game started (gamedayspassed * 24 + gamehour).

When a duration is set or changed, the NPC is added to a queue ordered by timestamp, so the first one in the queue is always the smallest value / earliest timestamp.

With all this set up, all the Timer sub-engine has to do is keep checking the first one in the queue an generate the Timer event when the game time reaches that value. This is the only GameMode block that runns all the time (on a quest)



VIRTUAL LIFE

As mentioned earlier, the engine allows for NPCs to have a Virtual Live when the player is not around, meaning, NPC will (virtually) do things while not loaded.

Of course, this is not importance for actions that do not have any further consequence in game, I mean, who cares if John Doe went to the bar for half an hour yesterday evening?

This feature is designed for actions that do change something that affects future events on the mod.

A few examples of things that may happen, even if the player is up in the mountain meditating for a few days:
- NPC production - if a lumberjack spends a day at the woods, a number of logs would be added to the game. Same thing for other crafts.
- Buying and selling - if an NPC decides to buy food, at the end he will have less money and more food
- Pirate attack - a pirate may decide to attack town. Guards will defend. The outcome is calculated and, when the player returns, he will see the results.



ALTERNATIVE EVENT CONTROL SUB-ENGINE

I must have developed half a dozen ways of controlling events during this development.

The engine described above is the result of merging and improving all that experience.

From all of them, there was one that I had a very high expectation, but the implementation did not come out as elegant as I wanted. I have dropped it, but kept it the code along with one single activity that uses it. A quick description:

It is an Event Control System where one script filed requests to be informed of events and to where event generators directed their events.

Using the "Go to Bar" example:
A script adds a Travel package to the NPC John Doe and tells the Event Control System: "When the event "ActorAtMark" referring to John Doe is created, activate the reference so-and-so with the argument so-and-so" or "When the event "ActorAtMark" referring to John Doe is created, execute the User Function so-and-so with the argument so-and-so"
The Event Control System is composed pretty much of lists of pending requests and, when the NPC script OnPackageEnd block raises the event "ActorAtMark", the Event Control System checks if there are any listeners for that event and executes whatever was requested.



TOKENS

Tokens are used as a short term solution under specific circumstances when the NPC must be controlled on a frame-by-frame basis, like dancers and actors on stage (did I mention that there is a Vaudeville-like theater? Yeah . . I couldn't resist!!).

The code is what is called (I suppose) a State Machine: a gamemode block with "if state == A" + "elseif state == B" + "elseif state == C", etc, where each block does its stuff and sets the state to the next value.

I suppose it will be easier to understand looking at the code when it comes out later this month.



MISCELANEOUS NOTES ON THE CODE

? I am using extensively, all over the place, the concept I call an Array-Object. Not surprisingly, it is an array that represents an Object (at least as my non-professional understanding of Object Oriented concept). Some examples of things represented by AOs in this engine: Actors, dialogs, seats, tables, activities, a theater act.
? Most of the processing is done with User Functions. There are about 200 functions and less than 50 regular object/quest scripts
? I am also using stringmap arrays extensively, on purpose, just to see if there was a limit. Never had any problem.
? The beta release will keep a quite elaborated log system I have in place. Very useful for debugging.


I am sure parts of this text will prove not as clear as I intended. Please feel free to ask for clarification

I, seriously, cannot wait :ahhh:


This makes my implementation of Vector's disease engine look like the easter bunny next to kong. It does, however, set my mind at peace about co-save bloat Got any idea about the maximum number of arrays that could be referred to at a given time, by the engine ? I was wondering if there was an arbitrary limit to the number of referenced arrays in a co-save.

this looks fantastic. you should check the work Syclonix was doing with finders keepers and BRAINS, there might be something useful in there... and maybe NPCs with Jobs as well

Ah, intelligence meets artificial intelligence at last.
This looks incredible, and will open up so much uses.

Any idea how much the overall impact is on performance?

Lots to read but well worth the time. Looking awesome! :read:

This sounds....phenominal!!

WOW.... :bowdown:

I hope modders will decide to use this.

Finally RadiantAI has it was meant to be,

you had me sold at implemented features section.

FLOW and Location - picking based on amount of npcs currently at that location and if overcrowded by set factor (votes), they move to different location instead?

Sounds really impressive, I'll keep an eye on this

Well, my one concern is that NPCs will now be more intelligent than I am!

Seriously, has NPC AI just lurched 10 years forward?

This sounds unbelievably awesome.

I think I love you.

No, really.

"Generic awesomeness shout out!"

This sounds rather amazing, can't wait to see someone implement it nation-wide. The nation being Cyrodil of course.

Hey, thanks, you all!!! Quite encouraging words. Got the motivation boost I needed. Work will progress faster, now.



No, although the array structures are not exactly simple, their number is not very large. Around 500 arrays, I would guess.
But I once had, in 10 minutes of playing, a 6Mb co-save due to thousands of undestructed strings. Lol


Will check. NWJ project is dead, thou.


Not yet, really.
But that is exactly what I am planning to do the next couple of weeks: An actual (although quite simple) AI system where the NPCs will learn from their experience and their decision in the future will be affected by their past experience.
I plan to have NPCs interacting with each other and getting some level of satisfaction from each interaction. I hope that, with enough iterations, they will tend to form groups of interest or, maybe, even pairs.
But don't raise your expectations. It will be a very crude system just to start playing with this kind of stuff.


Next to none, I guess. Supposing an average stage duration of 15 game minutes (30 real seconds), controlling 100 NPCs at 30 FPS, you would process one NPC every 9 frames, which is really nothing. In another mod of mine, I have ran some heavy scripts every frame without noticeable impact.



The Flow advisor is concerned with balancing the population at each location.
The Location advisor is concerned with how frequently the NPC moves to a new location.

Consider a scenario with two bars (which is actually the case in my mod). Bar1 has 3 NPCs in it and Bar2 has 6.
The Flow advisor will vote 66% to "Drink at Bar1" (less crowded = higher vote) and 33% to "Drink at Bar2"
Suppose the NPC is at Bar1 and the Location advisor is designed to prevent the NPC from selecting two activities at the same location in a row. In this case the Location advisor will vote 100% to "Drink at Bar2" (the other one) and 0% to "Drink at Bar1" (where the NPC is).

So the combined, averaged votes would be: Bar1=(66+0)/2=33 Bar2=(33+100)/2=66, so there is a 33% chance the NPC will stay in Bar 1 and a 66% chance that he goes to Bar2.

Consider the advisors as little angels and devils whispering at the NPC ear: "Go here", "Go there", "Do this", "Do that", etc. The more of them pointing to the same direction, the higher the chances the NPC will choose that direction.

NWJ is dead, Used to be a member. I know it was shame, but, real life and family always comes first in case of Sarkandar that is what happened. He still lurks every once in a while, but, does not mod anymore..

Gotcha, just wanted to make sure that was how I read it..I can see it bringing new life to Npcs for sure, that are already lacking it. because beth downgraded radiant ai to be basic, not dynamic like what you are doing.

So do you plan on putting your engine to work in just one town, with basic ai routines like you posted eat/sleep/wander/travel etc ?

or just a few select npc in case of travel routine is picked.

That's really impressive work, but honestly I didn't expect anything less coming from You. :angel:

I mean, I might know all the technicals you're talking about from university already, but getting it all into actual use in the game is a revolutionary masterpiece.

Learning NPCs? Building groups of interest?... Next you will tell us they use "neural networks"! :rolleyes:
If nothing else, then this will make those actors really seem more "living" and better yet "thinking".

And the way you chose to implement it all, those "voters", ... really genius!


...on the disappointing side though... how long's the learning phase of an actor in combat with the player anyways?
I mean, "Yeah, right, next time I won't leave my back unprotected... uhm, wait, there IS no next time! I'm dead!"
But for those actors "not" dying learning will really be a long-missed ability!

Since this engine takes control of the NPC, it presumes (requires?) the NPC has no AI package, therefore it will work well with NPCs created to be controled by this engine. I would expect problems if applied to vanilla NPCs.
The mod I am using for development uses its own NPCs. There are about 20 NPCs and they do have some simple activities like wander, chat or drink.
But they also select and approach another NPC at the bar and offer to buy him/her a drink. If the offer is accepted, they go sit at a table and drink, chat, etc.

But my real goal is to use it in my The Evolving Society mod, where this engine will control all NPC in the island. I want the NPCs to better react to a dynamic environment: a few examples made up just now (the mod story is not decided yet)
- A worker decides to work late because the community is in need of whatever he produces
- An NPC could be a jack-of-all-trades and, each day, decide what he will produce, based on the needs of the community at the moment.
- The guards will go to the armory each morning and select which armor and weapon to use
- A worker has a low productivity because he is not happy with the way the player is handling things (maybe he wants a church and the player did not build one)
- A key worker stops working and gets drunk all day because his wife is cheating on him. The player gets a quest to solve the problem and get the guy back on his feet. Lol.
- Pirates attack: strong NPCs run to get a weapon and fight. Weak ones flee
Something like that



Believe it or not, it did occur to me, as I have read a lot about them looong time ago. But I am too lazy to dig up that knowledge.


The nice thing about them is that you can create a lot of them. As many as your mod need. You can have an advisor that votes for activities based on the NPC faction, or strength, or whether she is single or married, or age, etc
You could also have a weighted vote, where some adivisors are more important than others.
The more there are, the closer to our real life decision process, I guess.


Wouldn't it be fun if an actor (or the engine) could identify the player's combat style, learn from it and adapt his own?
I have no idea if this is possible at all, as I have zero experience with modding combat. So don't expect anything from me in this area.

Has this been tested to determine performance impact? I'm just wondering about so many variables running per actor that may contribute to high lag.



Once you get this competed have a talk with skycaptain from Deadly Reflex mod, I can just imagine what the 2 of you can do.

wow, just wow...

i think Duke Patrick did this in one of his mods. maybe "combat geometry"? i forget, but one might want to do a quick check on TESNexus

Heh.. I'm no longer concerned

I would think that wouldn't be much of a concern given the mod's implementation.

This is a concept I have thought about from time to time, but realised it?s an overkill - in Oblivion the game. I?ll try to explain some of the line of thought I have had about this...



First, there?s little different ways of combat interaction for the NPCs. The player attacks? Well, they should block. Well for this, there is a in-build percentual chance for them to block when player attacks. One could adjust this percent dynamically but...dunno.

The player blocks? Well they attack, or they don?t. What?s for them to learn? That the player usually blocks when they attack? Rather just one could set their "attack when target blocks" percent to 0.

And that?s it, pretty much. Very little need to learn, when the actions are already controlled by direct chance percents - so editing the combat style percent parameters would the sane solution.



Now, we take Deadly Reflex, for example, that adds more ways to interact than attack and block. But here making the NPCs to learn - as we understand it in real life - is kinda counter intuitive. I mean, we take the inputs (player actions), and apply NPC "leaning" - we get outputs, successes and failures, and/or direct NPC actions as a result of the engine either predicting the actions of not.

The outputs are the possible benefit we are after - if the NPC would learn the player play style, the intuitive result would be less succesful player actions, and possibly more succesful NPC actions.


To make the NPC "learn" these things, we would have define the "learning". If we make a script that tries to predict player actions, we fail - IMO - since the NPC is only as good as our script.
Rather, we want to define if the player is acting predictable, and punish him from that. So there?s little need to implement explicit AI to learn the player?s play style, by implementing overly complicated prediction engine.


Also, if we did - how would we "predict"? By using statistics, of course. So again, we would end up monitoring the player, and the engine would be as succesful as how statistically repetitive the player actions would be.



These are just my thoughts on the subject, of course, but I personally realised it?s so very easy not to see the forest from all the trees, so I thought I would post these thoughts.

DR6 implements the kind the kind of system I described here - it logs the player actions in combat, and weights the skill based success chances with the predictability of the action used. The motivation is to further encourage using all the different actions, but at the same time the end result is the same as we would get if we implemented a system that would attempt to predict the player actions and counter them.

The engine?s chance of success to predict correctly would be directly proportinal to the statistical predictability of the player?s actions, and the player would do better to use diverse tactics to confuse the engine.

sounds awesome, qquix!
looking forward to this and your full The Evolving Society mod.

Well I'll be.

First of all, this is, from what I've read, an absolutely brilliant use of OBSE's User Functions. The "voter" system you have implemented sounds like an excellent way to get the NPCs to act in a more realistic manner. All around this engine sounds like it is destined for greatness.

Over the years I've had this same idea (well, honestly who hasn't, considering the blithe nature of Oblivion's NPCs), but more on a writ-large (i.e vanilla NPCs) scale. These thoughts were mostly spurred on by my ever-increasing levels of control over Oblivion's guards (which, while somewhat complex, essentially boils down to "stop that" *whack* "do this" *whack* "no, don't do that" *whack*). The difference is that you have gone and done something about it.

I applaud your work, QQuix, and I wish you the best of luck. May all your mods work flawlessly on user systems and may all the bug reports be reproducible.

A question on how it works on a modding level. I assume the structure is something like: you input an actor and the activities you'd like (plus their parameters) into a StringMap (of sorts) and from there on the NPC will be guided by your engine? I know this is probably simplified alot and there's a good chance I'm mistyping the thoughts in my head.

But this way, in theory it would be possible to replace the vanilla AI of the actors (lets say for the IC) and replace them with a list of activities corresponding to their vanilla AI packages. I know you mention that it was not designed with vanilla NPCs in particular but as soon as you remove their AI packages they'd be the same as any mod-added NPCs that are adapted for your engine, right?

Also, in the OP you mentioned OnPackageStart/Done, does this mean the NPCs will (always) need to have a script attached to them? If so then the above might not be so simple (due to high incompatibility reasons).

-kyoma