Sign in to follow this  

Storing and processing data with temporal footprinting in a large world

Recommended Posts

irreversible    2860
The main purpose for memory in this case is interaction with the player: I want my NPCs to be able to "remember" important events and important characters (eg other NPCs) without explicit programming or scripting. I don't want to create an extensive neural network or learning system that collates data and adapts to it: rather, I want to roughly shape an NPC's response based on the player's behavior even if the effect is remote (eg via another NPC) [i]while seeming to be very precise about it[/i].

Here's a pretty messy basic data collection setup I've written, that uses roughly the following scheme:

Environmental space X (can be anything from a building to a pasture to a cupboard to a cave to whatnot; an environment is attached to an owner, if applicable)
Attached to X is Object Y (most objects/items are attached to an environment to generate a relationship; an item can be attached to several environments; a discrepancy between an environments owner and an objects owner spells conflict)
Attached to the X-Y relationship is a Predicate - current count/good count (each environment-item relationship comes with an estimate called "good count", which determines how many of Y should ideally be present in X and a functional "current count", which tells how many objects are actually present; a negative discrepancy in the count or presence of a nonzero count of object Z that does not belong to environment X spells conflict; what this conflict is in particular, can be determined by examining X, Y and Z's ownership info and basic history)

This simple scheme allows for pretty nice flexibility with close to zero memory overhead - the only real limitation is the speed of data collection when a chain of interconnected environments and objects becomes large and nested. This, in a nutshell, is my scheme for extracting information from the surroundings in realtime. By attributing each environment and object with an ownership reference and history, it's easy to generate a fair bit of "knowledge" (awareness, really) for an NPC.

Now, the problem is that I'm looking at several hundred to several thousand NPC's, the very vast majority of whom I would like to be "automated" - as in, I do not wish to have to inject them with any specific information at all; I simply want them to be "aware" of their immediate surroundings. Things, however, get hairy when I try to attribute real memories to them. For instance, when the player screws an NPC over, I don't want to simply adjust a slider that determines the NPC's disposition towards the player - I want the NPC to be able to express the specific cause [i]why [/i]his disposition is being adjusted. As such, I don't need to have a very deep memory hierarchy per NPC - possibly only 10 most recent events tops -, plus most NPCs can, instead of being provided with personalized memory, be connected to all of their intrinsic groups' collective consciousnesses (a group is an generic hierarchical term that can describe a city dweller, an NPC's citizenship, clan, tribe, or whatnot - the precise boundaries of a group are not important; what is important is that groups encapsulate NPCs and limit and/or expand their knowledge to not include that of certain other groups).

Nevertheless, even though not too many NPCs can be expected to develop individual memory patterns, I'd like to push this as far as possible. As such, the main problem I'm struggling with now is structuring and storing information about a generic memory event.

Let's assume NPC A gives the player a task to kill NPC B who responds by bribing the player to kill NPC A's wife instead (I know, gruesome, but definitely strong enough to cause some serious and unforgettable damage to NPC A). Now, how NPC A responds to this is largely irrelevant - that's a matter of decision-making based on facts. What matters is how this turn of events (said facts) might be stored and later be reused by, let's say, bestowing them on NPC A's son (NPC C), who then might have the capacity of declaring revenge on the player for killing his mother. Even if the memory itself is only used for a verbal response and deep inside there's a locked slider that will cause NPC C's disposition to be forever hostile towards the player, the event itself should be stored and reproducible somehow.

Right now I'm using a simplistic makeshift database system, although at one point I will probably be migrating to SQL. Keeping such a format in mind, can anyone suggest any further reading or and actual solution to this problem? My main aim is to keep the memory events flexible and reducible to rather simple constructs while maintaining as much detail about them as possible to later communicate the nature of the events back to the player. I haven't seen this being done effectively in pretty much any game and my knowledge of AI programming is very limited, so I'm not really hoping for much, but if anyone can suggest some leads to latch on to, I'd appreciate it a lot!

Share this post

Link to post
Share on other sites
irreversible    2860
[quote name='ApochPiQ' timestamp='1310874656' post='4836245']
I don't think you need a per-NPC-instance KR here; I think you could do it with a global KR that NPCs can query using filters to specify the limits of their awareness.

Aha - I'm assuming KR stands for Knowledge Representation? And basically what you're suggesting is storing all events that affect the game world globally and later reconstructing specific memories them using shared properties/relationships?

Giving the related Wiki article a quick spin I'm not sure where exactly to look on from here (eg which system to favor in my case - the semantic system combined with a decision tree/desire quantification looks pretty nice, but I can also see it building up size pretty darn fast). I skimmed through the MultiNet documentation and it's actually pretty compelling for generic information storage such as generating navigation information and making directional/behavioral decisions on the fly. However, I'm not really convinced yet as to how efficient database memory management and automatic filter generation will be when the amount of data ramps up. I suppose some predefined filters (eg group-limited knowledge) can help a huge deal here, though.

If anyone has any further suggestions from this point on, I'd, once again, appreciate it a bunch! :)

Share this post

Link to post
Share on other sites
haegarr    7372
[quote name='irreversible' timestamp='1310870929' post='4836228']
The main purpose for memory in this case is interaction with the player: I want my NPCs to be able to "remember" important events and important characters (eg other NPCs) without explicit programming or scripting. I don't want to create an extensive neural network or learning system that collates data and adapts to it: rather, I want to roughly shape an NPC's response based on the player's behavior even if the effect is remote (eg via another NPC) [i]while seeming to be very precise about it[/i].[/quote]
This reminds me of the article "A Dynamic Reputation System Based on Event Knowledge" in AI Game Programming Wisdom, volume 1. The system described therein collects events (that are recognized by at least 1 NPC called the witness) in a global list. NPCs refer to each instance in that list from which the particular NPC has knowledge. The events are tagged with a action type (e.g. meeting, attack, ...), an intensity value (e.g. a ), to which individual and/or group of individuals (e.g. bandits, villagers, ...) the event happened, at what moment in time, ... IIRC then the NPCs forget event over time. An event is removed from the global list if no more NPCs refers to it.

However, I have not understood really how the part cited above is related to the "object Y in environment X" thing of the OP. Of course, a general knowledge about ownership can be modeled that way, but events are more often than not related to actions instead of objects, IMHO. I think I'm missing something...

My recently made thoughts about how NPC may recognize (not memorizing yet) the environment are as follows: [i]Receptors[/i] can be attached to NPCs (as part of the component based entity modeling of game objects). Receptors may be distinguished as for the touch, visual, aural, or even olfactory senses if one wants to do so. Corresponding to the used types of receptors, [i]stimuli[/i] can be placed in the world. A stimulus is basically a bounding volume tagged by the type of receptor necessary to notice the stimulus. Up to here the recognition mechanism is well known; I remember I've read an article (in gamasutra?) where viewing cones are used to check for intersection with visibility sphere to simulate a kind of visual sense. However, now a collection of [i]sensations[/i] are attached to the stimulus. Such a sensation is meant to be similar to the event data described above: They define what the NPC may recognize and at which impressiveness.

Let's assume that the PC fights an Orc (because of his biased opinion about this peaceful race ;). During this fight a visual stimulus may be placed where the fight happens, and the sensation of the stimulus would be that the PC is aggressive against an Orc. Now the PC was able to kill the Orc. The former stimulus is replaced by another one that carries the sensations "Orc", "corpse", and "violence", for example. After a while the corpse starts to stink, so an olfactory stimulus with time increasing intensity is added. After some time the corpse is rotted and all stimuli are removed.

The stimuli are to be processed to have an effect, of course. One way would be to be stored as a global event with a local reference in the memory of he NPC as described above. Another way would be to process it in the NPC's mind. This could be done similar to the known ways as in interactive story telling or considering NPCs with personalty and/or mood.

I know that such a mechanism may be too heavy, dependent on the complexity of the world. For now it is just an idea how to let NPCs recognize the environment...

Share this post

Link to post
Share on other sites
IADaveMark    3731
The database approach is best. If your database has a table that simply stores knowledge of events, your structure would be:
[list][*]OwnerID (who owns this knowledge?)[*]EventType (from an enumerated list of interactions - likely in another table)[*]SourceID (who did the action?)[*]TargetID (who received the action?)[*]OccuranceTime (When did this happen? We can also age things out of the database this way)[*]Severity (did I have 1st-hand knowledge? Was it on me? Near me? Rumor?)[/list]
So, if A punched B, B would add a record:
[list][*]B[*]Punch[*]A[*]B (self!)[*]now()[*]Direct[/list]
If C is a friend of B and witnessed the punch, he could also add a record but with:
If D hears about the event from B, he would add a record:
Now, if we ever wanted to find out what B, C, or D thought about A, we could simply query the DB for:
[list][*][b, c, or d] depending on whose mind we are in[*]*[*]A --or--[*]A[*]*[*]*[/list]
We can then assign utility values to all these sorts of interactions using things like:

Direct means more than indirect versions
To me means more than to a friend which means more than to a stranger
Reverse that for an action against an enemy, etc.
Recent actions mean more than more distant ones.

For more reading on generating opinions from actions, see Adam Russell's entry in AI Game Programming Wisdom 3 on Opinion Systems (from his work on Fable).

Share this post

Link to post
Share on other sites
wodinoneeye    1689
Much depends on how complex your world is and the interrelations bewteen your NPCs (and players) .

The system may record events/results of actions between entities but then each induividual
entity (NPC) may have a different way of reacting when you pull that stored/accumulated 'relation'
for a interaction with another.
(ie- is he a coward who will thry to backstab instead of confront, or too affraid of trying to ge even
with an opponent who is much to strong so instead stiffs them for their change or badmouths them behind
the others back). Spectrums of several different 'tendencies' as attributes to each NPC can be used
to vary them significantly

What alternatives for actions will your NPCs have ? I would expect this is part of the general AI system a bit
more than precanned customization scripts for all the NPCs. Generalized solutions and situational problem
identification (and routine tasks and roles ) would allow you to parameterize your multitude of NPCs and maximize
reuse of the same behavioral logic. Events that effect groups/individual/roles would have to be evaluated
and a vector of different interpretations of the effect would likely to exist (an act seen as bad by one group would
be seen as good by their enemies/rivals while another interpretation is judging an act to be a disturbance of normalcy).

Hierachical effects can override the judgements (and the reactions that come) -- when a town is under siege and a
larger enemy is threatening the community, petty rivalries are often forgotten . So a prioritization scheme
probably with some kind of quantum system will come into play .

Unfortunately you are getting into the area of simulated behavior where social structures and human variance
start exploding the logic complexities. The data stored is only one problem, the constant re-interpretation
can be a larger reource drain.

Share this post

Link to post
Share on other sites
irreversible    2860
Thank you for the ample and very well-structured responses, guys - this is precisely what I was looking for! haegarr - it seems I was thinking of exactly the same system you're describing, albeit I just tried to come up with the most feasible one.

As for ownership and relating an object to a particular environment - that's actually another thing I just tried to formulate in the most meaningful way. What I'm after with that is compacting information and avoiding a) data duplication and b) instanced objects in the world (database). Consider a barn environment. The building itself might be highly regular and simple, but let's also assume it contains some objects that an NPC might, in his or her own right, deem implicit when describing the barn. Let's say these objects are (1) a shovel, (2) a rake, (3) 2 pitchforks and (4) a chicken.

In a regular gaming world these are five objects that need database entries, which expand to five tables of regular objects being filled with information. My idea was to avoid that and attach most objects in the game world to specific environments by means of a counter and only create database entries for them when they are removed from their native settings. This provides three benefits: a clear memory saving, a clear instancing saving and (relevant to this thread) implied information about ownership (or a lack of ownership) without needing any further information aside from generic descriptor objects.

For instance:

NPC John Smith
Owns a barn
That has an implicit inventory with 0/2 pitchforks

This means I don't need to relate any information of a missing pitchfork (or any pitchfork) to John Smith at all to know that he desperately needs one in case he's a farmer. Furthermore, I don't need to relate any information about a pitchfork's possible locations or John Smith's personal belongings to know where I cannot and where I can find pitchforks (they're not in John Smith's barn, but I can find them in most other barns). By adding an object to multiple environments, I get a list: "you can find a pitchfork in a barn, a hardware store or in a stack of hay" and all of a sudden I've added an object to the game without any need of instancing it.

This works in reverse, too. Consider the very same case:

NPC John Smith
Owns a barn
That has an implicit inventory with 2/2 pitchforks and 1/0 termites

In-game I don't need any logic to tell me that the termites don't belong there. Furthermore, with termites being generic objects, I don't need to instance them at all to reference them.

This scheme should work for all generic objects as well as a good number of unique/specific objects that have a particular environment that they belong to. In general I just thought this'd be a neat way to organize things and keep down overheads, nothing much more :)

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this