<< Brief thoughts on value systems Back to index... Testing priorities >>

Minor Gripe

2019-11-18 -- An approach to NPC knowledge in persistent MMOs

Chris Ertel


I used to dabble in amateur game development, and one of the most interesting bits to me was trying to figure out how to make believable, interesting, and alive worlds.

There’re a whole bunch of interesting resources on trying to render large virtual worlds and procedurally generate them–but while the environments are increasingly high-fidelity and cool, the denizens of those environments aren’t really seeming to get more interesting.

Now, I recognize that there have been some really amazing advances in game NPC AI. There was amazing use of STRIPSplanners in F.E.A.R., for example. Left 4 Dead made some amazing strides both in ally NPC AI and also in dynamic story-beat/encounter generation.

That said, I struggle to find a case of NPC AI that seems to hold up well in a large, shared world. A good chunk of that is, I think, that in my ideal MMORPG (or arguably any computer RPG (cRPG), but that’s a different write-up) the world itself responds to players and rewards and punishes behavior that is concordant or disruptive in the game logic–if the AI can’t notice this behavior and act on it, it becomes hard to take it similarly.

Another aspect of this is that the lot of most NPCs in these games is to stay around just long enough to provide players something to shoot at and murder…they’re pop-up targets and little else. One of the oldest tricks (engaged in by both F.E.A.R. and the original Half-Life) is to simply crank up the hitpoints of an AI opponent to make it last longer (and thus seem smarter), and to add some barks (speech emotes) to give the player an impression of thinking or communication. All of this when the actual workings are not terribly geared towards intelligence, artificial or otherwise.

So, if I want large interactive worlds with interactive populations that are more than just noisy, durable targets, I think we should branch out more.

Towards supporting more immersive environments

One of the key limitations we run into is that the number of modes that a player can inhabit in order to interact with a game environment is not large. While I defer to folks with more of a formal background in ludic studies to probably have a better insight on this, let us suppose that the immersion of a game is a function of how large the space is of actions that a player can take with some measurable, observable impact on the game state.

The card game War has effectively no choices afforded to the players, nor does Chutes and Ladders (though it does have some fascination for the statistically-minded). Farther along, we run into games that have a high dimensionality of a discretized space like Go or Chess, where even though the board itself is small the gigantic branch factors of both games mean that decisions exist and can be studied in detail.

Of perhaps most interest to cRPGs, we have games like Doom or Quake that are continuous in space and so afford lots of “decisions” to players and their avatars, but which have a very basic set of actual ways of interacting with the world: picking up items, activating switches and doors, and shooting enemies.

Even games like Morrowind or STALKER: Shadow of Chernobyl, advanced as they are, tend not to have too many ways of actually interacting with inhabitants. Even games with excellent writing and detailed faction systems like Tyranny or Fallout New Vegas tend to run into eventual limits.

I posit that the one of the biggest reasons for these limits is that, having implemented and introduced NPCs that are theoretically people and sentient, the games fail to give players the opportunity to actually interact and change the internal state / knowledge of those same characters beyond some simple things like “Player has completed quest X”, “Player has attacked me”, “Player is a member of the Horde”, etc.

In real life, we meet people and can form impressions of them, can learn about the world or lie to them, and so forth. Our actions are propagated via word-of-mouth to other people and follow us around to some extent or another. I think that if there was some mechanism for players in a cRPG to engage on that level, it’d lead to some interesting and immersive possibilities.

Two types of knowledge for game NPCs

What sort of stuff would we want NPCs/the world to have access to in order to make decisions and choose interaction posture with players? I imagine the ability to “know” some set of facts, things like:

In addition to this sort of “historical” knowledge, there is also the idea of “functional” knowledge:

The distinction being that historical knowledge is based on in-game events, whereas the functional knowledge is based on a (almost certainly human-created epistemology, but perhaps added to over time) set of facts about how the game world functions.

The utility of this sort of arrangement is that we can start to maybe offer the chance to support things like more organic dialog, as the knoweledgebase of a given NPC allows them to start to answer questions like:

“Does Nate have any money? Did Nate at one time have money?” “Is Grant an Orc?” “Does Chris live in Brooklyn?”

Being able to have these conversations with, say, an NPC barkeep would both save a great deal of time in the construction of a world and additionally open up the chance for players to naturally explore the setting using questioning instead of pre-selected dialog choices.

This all probably seems a bit far-fetched, but if we represent this information in a triplestore then we might be able to let NPCs query it using something like backtracking during conversations. Even neater, it might be possible to use this knowledge to run planners to generate strategic actions for the NPCs when dealing with players or other NPCs/factions. This opens up a whole new realm of procedural content and immersive gaming.

Beyond global knowledge: local state

Having a barkeep that can talk semi-intelligently about happenings in town is neat. But, the real benefits of this approach start to happen when we change from a global knowledge store to knowledge stores that are NPC-specific. Not too get too navelgazy, but one could argue that all of the interesting interactions between people are the result of attempts to reconcile partitions in the representation of global state–we are the universe seeking to understand itself.

At any rate, imagine that we have an NPC Brooklynite Recurser. There is the materialized knowledge store of facts that they know and have access to during conversation with players and planning. But, this is horrendously inefficient as the number of NPCs grow, and so we look at ways of solving this.

The traditional way of solving this in, say, Unix processes is that you share memory pages for things like system libraries. So, what if our NPC “shares” the knowledge stores of other groups of NPCS?

There’s the “common knowledge” that all NPCs share and that is basically without question. This would be world constants like “fire is hot”, “gold has base value 10”, and so on. Then, there’s the location/setting-specific things like “Dragons live on the F-train” that the NPC would get from being a Brooklynite. Then, there’s the faction-specific information that the NPC has from being a Recurser of things like “The best bahn mi is at Hanco’s.” Finally, there’s the NPC-specific knowledge that is first-hand experienced…”Nate gave me a bahn mi”.

This lets us more efficiently represent knowledge across NPCs, but also opens the door to something else: knowledge transfer.

Beyond global knowledge: knowledge transfer

Wouldn’t it be neat if two NPCs could share knowledge? We can do that, by having some action that transfers a fact from the individual store of one NPC to another. But why stop there? Why not, if conversation happens and multiple NPCs are present and emitting facts that share some topicality (say, the player asks about food and the NPC each start blathering about their specific food facts) they each get a copy of those facts (if they’re paying attention)?

At some point, especially if they many of them are in the same faction or partition, we start to see a sort of “tribal knowledge” naturally forming. From an implementation standpoint, we don’t even have to simulate the transfer of knowledge through conversations or what have you–what if we periodically surveyed the individual knowledge stores of members in a partition and, if a sufficient number of them know a fact, we just promote that fact to the partition/faction knowledge store? Applied upwards, this would allow for the ability of “common knowledge” for all NPCs.

This opens up the fascinating possibility of player’s deeds and actions becoming common knowledge among simulated populations. If a player does nice things for enough members of a faction, eventually that faction just “knows” that the player is friendly. If enough factions think a player is friendly, then the “world” knows that the player is friendly. This sort of hierarchical modeling of knowledge provides us with some value.

But, what about facts that are contradictory? What happens when our player does something unfriendly to a member of that faction? How is that resolved?

Beyond global knowledge: knowledge veracity

Instead of just some simple “fact”, let’s also add the concept of weights to facts. 0 means no belief, 1 means complete belief. Taking our earlier example, suppose that the player decides to talk to a rival faction NPC and claims that they are friendly. The rival NPC, perhaps belonging to…I don’t know…Y-Combinator, does not believe that the player is friendly. They believe this not based on their “personal experience”, but rather on the “tribal knowledge” of their faction. If the player acts friendly towards them and maybe does something nice, that belief gets weakened. One method for this might be by just scaling down belief weight, another more interesting (to me anyways) way would be by inserting a new fact into their individual knowledge store.

This leads to a chance to model cognitive dissonance, which is cool. The NPC knows that Recursers are not friendly because their faction knowledge base claims this, but also that they have personal experience of a player being nice to them. This leads to some neat ideas:

While neat from a simulation perspective, from a gameplay perspective this also opens up an entire new opportunity for the players: there is now an emergent mechanic for compromising NPCs of rival factions, for changing those factions, and possibly even for recruiting members of those factions into their own faction.

This also lets players engage in another sort of people problem. If they witness an act or fact and attempt to report it (say, claiming that the Y-Combinator NPC stole a bahn mi), they may have to convince or otherwise handle a skeptical faction. Alternatively, if they decide to do something against type themselves (doing a nice thing to an NPC, assassinating an NPC, etc.) they may be able to leverage the tribal knowledge of factions to get away with it (if they are generally believed to be good) or face resistance in getting appreciation (if they are generally believed to be shady).

Is it possible that an NPC will just straight up disbelieve a fact that has been presented to them? Depending on the situation, maybe that results in heckling the presenter or maybe it triggers some “crisis” in the NPC (in, say, a Lovecraft-themed setting).

Again, we’ve opened up a whole new dimension of play.


I think there’s a lot of cool exploration to be done in this area. While knowledge store and planner techniques have trouble in meatspace due to the complexity of the real world and its uncertainty, I think that if applied in a game or a simulation they could lead to some impressive and organic play.

Tags: ai gamedev

<< Brief thoughts on value systems Back to index... Testing priorities >>