next »

[gimymblert]

I'm looking for a procedural way to fake dynamics NPC with local procedurality, complete with travel, genealogy, etc.

It's a thought experiment at that point, maybe I'll find some use in the future, current project don't allow it

Ie Local mean if you evaluate a tile for generation you wouldn't need to look neighbor, or past state, to find the correct state, just solving with (x,y,z,t) with the global parameters.

For example let's look at how to do it to geography first. Let say you have a planet and it had x number of civilization randomly place on its surface. For each tiles you can solve its current event by computing the distance of the tiles to civilization weighted by time, so if the weight is below a certain threshold the tile is wild and have no civilization influences. By computing all the weights and using the filter and parameter of each civilization you can determine the exact events on a tile at moment t.

For example, let's you have a tile under influence from civilization A and condition are solved into a fortified town, Civilization B is war like and its influence grew on that tile, the formula solve it by creating an increasing siege to full war over time. Another example is a tile is wild, a Civilization influence grew on that tile, so you see explorer spawning on the tile then settlers, etc ... over time. It had the benefit that you have not only the illusion of dynamism but also time travel and dimension hopping come for free. The main concept was to convert cause relation into correlation.

But how that would translate to dynamic npc that travel, meet peoples, have adventures with them, without any need to bookkeeping?

The trick is to find a function from which we can infer those things. The difficulty is that generation is tile local and character, through travelling, are not, and also having relationship make it supposedly non local. So the function must take as input a tile in a certain time and infer a character that is non local :/ kind of defeat the point ? Well that's what I'm investigating, what if we ties character to a procedural list generated at a bigger hierarchical level and use time to index that least based on character and tile parameter? Another idea is not index character but parameters and those parameter index the character (ie instead of character owning parameter you have parameters owning characters) which make it easier to link tile state to character.

Another trick would be to separate time into frequencies, with lower frequencies state informing higher frequencies. Also character are kind of predictable, they need to sleep, eat and have some sort of occupations, all of that daily, they also age predictably in a fixed sequence, which give pattern for procedural solving. As environment impact character we can also infer his behavior and presence in a tile, and relation can be deduce from "collision" of character generation in the same tile (almost because we should be able to infer relationship without solving the tile, so relation is the hardest to solve with local procedurality).

I wonder if any people have idea to ameliorate the concept, the great thing with procedural generation is to see it as an implicit storage and virtual memory access.

[gimymblert]

I guess this is too hi level

[starsrift]

While it can also be viewed as a funny response, I think you are actually thinking too low-level.

In coding, you do not have to first invent the universe in order to make an apple pie from scratch.
More immediately and practically, this kind of granularity is throwing CPU cycles where nobody will ever notice them - when some RNG tossed into properly weighted reference tables will produce the same result.

[SirNiko]

What kind of a game would this be for?

In line with what Starsrift said, you're usually better off faking this sort of thing than trying to deeply simulate it. A simulation may result in unrealistic outcomes because of limitations of your inputs, or the player's method of interacting with the world (spoiling the simulation by interfering with it). Rather than calculating when and how many times an NPC will move between cities, you might go with a percentage chance that an NPC the player meets will be a relative of somebody they met in another town, or that the player meets an NPC on the road. Animal Crossing just periodically made NPCs move in and out of town, for example, without bothering with any sort of complicated mechanism for simulating migration patterns. The player can fill in the narrative holes if the broad behavior seems believable.

This is also true because an accurate simulation may just not be at all interesting from the perspective of a player.

You might consider constructing something that uses real people (other players) to guide the travelers. MMOs like Ultima Online and World of Warcraft already incorporate possibilities of players encountering familiar players in transit. Perhaps a game designed to make intercity travel more rare and risky would be interesting and result in outcomes like the ones you want to observe. EVE Online features a huge world/universe where many players are encouraged to remain local to home bases they must defend, so over time you see shifting boundaries and instances of players who change alliances and relocate to other parts of the universe. Maybe that simulates some of the behavior you want in your concept?

[gimymblert]

Well the entire idea is precisely to avoid simulation, it's about faking it while having consistent data generation that look like it was simulated and coherent.

The context is galaxy wide simulation of npc, so traditional method wont work as there is many order of magnitude that make it impossible.

You can't store all the data or simulate it, it would choke at the first village and a village is just part of a country that is part of continent that is part of a planet that is part of a solar system that is part of a galaxy, the magnitude of order make it impossible.

The idea is that solving this problem will give plenty tool to refine the usual statistical method that use distinction between generic nameless character and unique character with persistence, I would use.

Let's narrow the problem down:

A npc is composed of its Identifiers, looks, condition, preference, know how, social status and habit. All of those can be easily generated locally. We can know a NPC reactions based on generated parameter and state at a tile (fight or flight in a war torn tile for example).

**What's non local is travel and relationship**, relationship depend on travel but is a cause, therefore we must find correlated formula to the too.

- Travel can be seen as a function of the type f(x,y,t) we can define if a tile intersect the function at t. Habit of npc is highly cyclical as they follow pattern daily, with slight modification depending on internal state or displacement through travel.

- Relation can be seen as converging function to a single parameter in a specific space so that evaluating that parameter at t return a procedural list we can index, parameter of the relation can be define locally in their own space (strength and type of relation can be inferred from character's attributes), therefore it's correlated, we can give the illusion of action by generating the social act when they intersect to give illusion of causality.

Oh ... looks like I answered half the proposition, now it looks like a less opaque.

[Pfotegeist]

I have a low level solution. Seeing how I can't think of any math involved.

Normal distribution curve answer all living population problems.

Past history for a single NPC can be randomized. A tree of possible life outcomes that represents a normal curve somehow, while oversimplifying reality, is probably suitable. it'd take no time to process.

It would take a while for such a tree of life to be designed.

Outward appearance can easily be based on social economic status.


As long as the player has a limit to the number of unique NPCs they know about, then you won't need to store too many random characters in memory.



is it alright if I drop in a random insight here?

theoretical
If you were to generate a tree of life procedurally

A life path that immediately lead to crime would greatly tilt the odds in favor that everyone you meet is criminal. For example, everyone who went to Blasnarl University or grow up in the Huud get stuck in a dead-end job headhunted by a hacker syndicate. This scenario would mean your most intelligent population inevitably join up, but any tourists would be affected very little.

You could probably pick out seeds based on how interesting the outcome would be. Severe problems with the balance in population would be interpreted as really big problems. Procedural quests.     

[valrus]

I've wondered about this, too, for a unlikely-to-actually-be-make idea I've been kicking around.  I don't really want to simulate actual people traveling in groups, etc., but to provide an illusion that people's knowledge, skills, and preferences come from life experience.

So if we want aspects of NPCs to be based on past experience (especially non-local experience like travel and companions), we could start with particular motivations for travel (education, work, pilgrimage, etc).

So, education.  Everyone has some profession, and some of those professions require training that can't always be satisfied locally.  Not every site can educate every specialist; there might be only 25 sites in the galaxy where you can get a degree in Software Archaeology, and those 25 sites have different capacities, meaning that some people might actually have had to travel far to learn it.  From populations, enrollment size, and locality, you can figure out the likelihood for each site X that people of profession Z were educated at site Y, and that students of site Y in profession Z are currently at site X, etc.

So for each site in the galaxy, you could choose an arbitrary person with a particular occupation and age, and ask for the probability distributions that they were in school in a particular period, and that they were in school at a particular place.  Choosing any value for these gives the person a little bit of history: that they've been in a particular place at a particular time, that they've been to intermediate places in the travel route at particular times, etc.  And from, that, certain traits (like they probably have some proficiency in the language of that place, or participated in a notable event that happened there).

So for the question "Who does this person know?", we can use the same probabilities to "find" (that is, generate) other individuals.  Specifically, those individuals they met according to incidents during their educational travel.  Keeping the education site and period fixed, you get the probability distributions that an arbitrary student currently lives at a particular place, and is a certain age.  Now you have a relationship (friend, lover, enemy) between two individuals that might, currently, be far-flung, but this relationship may have caused certain effects in the present.  (For example, you might speak the language of your old lover, or you might retain a hatred the cultural group of your enemy.)

A series of such calculations (birth, education, military service, religious pilgrimage, etc.) could simulate a lived life.  So querying an arbitrary person at a particular site gives you a list of facts like age, skills, languages, preferences, etc., but also little plausible stories that explain those facts (they can speak decent Centauri Spanish because they got their doctorate in software archaeology from the University of Proxima Centauri B, but are prejudiced against Neosamoans because of an incident where their birth sister died during the New Samoa revolt) and links to important other people in their life. 

Anyway, what facts and stories are relevant and interesting depends on the game, of course.  In my game, things like literacy, language proficiency, and cultural prejudice would be important to the gameplay, in another game, it might be something entirely different.

[adrix89]

"If a tree falls down in the middle of a forest and nobody is around does it make a sound?"

In the case of video games the answer is no. The world is generated around the player,at least for single player games.

Simulating anything that does not affect the player directly is useless.
What does that mean?
It means the NPC have to matter to the player, if they don't they re like leaves in the wind, they come and they go, to the garbage collector.
With that it becomes obvious what you should do. Assign an order of importance to the NPC.
If they are important you can generate their history and current context easily on the fly.

Have a quest manager that gives purpose to NPCs in relation to the player. Make NPC goals be either cooperative or conflicting to the player's own quest goal. Then simulate NPCs pursuing those goals, they will eventually connect to the player in the end and the player can still react to the events as they happen.

To get an idea think of the chase of Sephiroth from Final Fantasy 7.
They find clues and see the devastation he brings and the party tries to stop him.
If that game actually simulated Sephiroth as a character the players would have some options.
Will they pursue him? Will they make it in time?
Do they salvage the situation in the places he has struck? Do they ignore it in favor of the pursuit?
Do they try to prevent a disaster in another location? do they search for more clues on how to defeat him?

This is what I call a important NPC. Everything else is not worth the memory and CPU cycles.

[BorisTheBrave]

There's a fairly hard dividing line with what you could do with a stateless efficient procedural function, and what you cannot.

Generate an infinite random world of NPCs, each with a unique name, profession, lifespan, and pattern of moving around the world? Fine, can do. Want them to causally interact with each other, or the exogenous world (e.g. the player) - nope, you'd actually need to store and track them.

It sounds like instead you want it to interact with the world, be cheap and local to evaluate, and are willing to sacrifice on simulation quality to get it.

What comes to mind is the cars in Sim City 2000. For each tile, it showed an animation of cars moving if the simulation said there was trafic in that area. The animation tiles were set up so that if you placed two next to each other, it looked like cars were driving off of one square and onto the other. If you troubled to follow a "single car" long enough it would drive out of the trafic area and vanish. But without scrutiny it looked like you had hundreds of cars in your city.

[Pfotegeist]

I'm only considering a possibility for one NPC at a time. Like if you scan someone in Watchdogs, you get a very brief history and that personal information is stored for a time until they have gone away.

Valrus described the conditional tree better than I think I will.

Ie Local mean if you evaluate a tile for generation you wouldn't need to look neighbor, or past state, to find the correct state, just solving with (x,y,z,t) with the global parameters.

This makes the idea functional, and it sounds like a big challenge.

If you want to know what someone was doing 5 minutes ago it'd be a matter of stepping backwards through an action tree (if this were an ai). Which sounds complicated.
If you want to know what someone was doing 5 years ago it'd require stepping through something more like the conditional tree. Flavor text and statistics.

If you wanted just about any arbitrary moment in time generated on the spot, it might be possible. Think of breaking the conditional tree down to locations visited, the average experiences at a given age could be reality. The past 5 minutes and next 5 minutes would need to be determined so that a local scenario is in play. It might be impossible to determine how you got from this location to where we began, 5 years from now, if we just pulled this instance from a hat.

There would be issues if you wanted characters who lived for thousands of years, and the average (alien?) lived only to 100. You already have a very limited number of things that could be done, you'd need to start micro-managing these outliers.

[JWK5]

[valrus]

That's a good idea on the regional accents/personal mannerisms/etc. 

At some point I hope to make a library to automate a lot of the tasks of procedural language generation, allowing you to "localize" all text: put in a bunch of English text, and it comes out with images of the written form, audio files of the spoken form, and a Romanized version as a text file.  But one thing I hadn't thought about was retranslation back into English. 

Since the transformation is lossy (structurally and semantically), taking the intermediate sentence trees and outputting them as English would get you distinctive "ESL"-type dialogue, some quite syntactically and semantically poor.  (Missing determiners, getting gender wrong, collapsing important distinctions between words, etc.)  This could add a lot of flavor to dialogue, simulating NPCs with only limited command of your own language, or simulating what you're "hearing" when you only have a limited command of the local language.  This would be on a sliding scale, so you could do anything from a faint accent (a near-fluent speaker who sometimes forgets "the" and "a") to completely garbled speech.

[gimymblert]

@Pfotegeist

Good idea with the tree of life! I don't know about teh curve and what you mean about that though µ...

On the tree it is possible to uniquely index character based on their generation, therefore to know their descendant, and ancestor as well, from a single locak variable without having to unroll all the history!

Let's condider a simple case:
- let assume people self repliacate (or are all women)
- don't have more than 2 children (can be n number but let's start with too)
- generation happen at the same time (not necessary but help to visualize)
we have a binary tree so we have root ancestor A that lead to branch A(B C) wich lead to B(DE) C(FG) >> A(B(DE)C(FG))  .... lisp is king!
There is a definite order in which you can index each member of the tree that look like something like n = 2^t so for x number of branch you would have n = x^t ... haven't check the actual math but it should be something similar  

Of course we need to look at the formation of couple aka relationship (we will see that below) but we know that only women (half the branch statistically) gave birth (generate branch) so that make it simpler in some sort even though I haven't think that through correctly, at least it point us in a credible direction. Other things to look for is uneven number of generation by branch and dynasty dying out, I believe it can be done through a kind of procedural masking that randomly cut branch and it's easy to not visit the index by jumping ahead whole indexes. I also believe that order and time of birth is also less of an issue since we have predictable index and branch don't have much influence between each other aside from potential relationship, which mean we need another time formula to sync branch that grow a differing "speed" (ie have generational distance between their algorithmic generation)

@Valrus
I don't think we should think of npc as a starting unit in themselves but as a result of multiple filtered influence (correlation other causes) else it became a simulation and solving became a hard problem. A way to look at it is npc as a consequence of multiple higher order structure. For example we have a planet which generate a population parameter which generate civilization from it which generate town which generate NPC,the NPC inherit from these structure their attributes. As such we must find a way in which rich interaction can be inferred from. Fr example if you generate a npc from a family it automatically inherit relationship with other member of that family which are generate by the family seed, you don't need to store that there is a relationship just need to procedurally query the seed of the family. As such we can see npc as intersection of multiple higher order structures. That allow for limitless NPC.

However You point at some interesting stuff I didn't thought about, what if travel routes was part of those higher order structure! if we know travel routes we can potentially deduce npc positions as they will use it! because teh main query isn't NPC but the place the player is. That's cool!


@adrix89
You are absolutely right in every way!

The reason I left the player out of teh equation is as a simplification to focus on this particular first and develop the tools without being distracting by further constrain. However the aquarium effect (witnessing limitless history is compelling to some player) do affect the player experience (and linear story based game do exist as a market) and from a gameplay perspective the shift in context affect the way the player interact with the world too, like making the world a dangerous place or affecting scarcity of resource.

That said, I believe solving the problem this way can help making a more interactive version later, the player can store a profile with data that can be use as a modifier to seed generation relative to change he will make and that adapt the world to the player. Since everything is derive from a formula, it makes the world infinitely malleable. I believe what you envision can totally be done this way!

I think I have made some progress since last time, in fact I think teh key is that npc is the end result of parameters not the start, aka you don't start withe npc structure and fill its members, you start with a higher order structure, such as family, which give implicit relation to the generated npc as a member of family. That's how galaxy generation works, planet belong to solar system which belong to galaxy. However explaining this to you made me realize that the higher order structure I needed is a social circle! Thanks orbiting planets!

For travel it make sense now, if you generate the world such as you have planet >> civilisation >> population >> ... >> npc they can't travel between civilization because its the highest order they inherit from as member of population, however if population is higher than civilisation we can index civilisation as a paramater than can change through time, simulating traveling!

Also analytical is harder to maintain, you have to track a lot of data, even lazily. With procedural generation the procedural space act as an infinite memory to query for none of the cost, and it's a memory that store index time too so none of the computation needed!

edit:
An example of correlation I found is that let say a character is an asshole as a parameter (attribute: likability) which generated by a given noise curve, another character can query the seed that generate the curve and have a modifier in time that is slightly offset in time and define his appreciation of the first character, as the character get more asshole the appreciation worsen by sampling the curve a bit late to mimick the character realizing what the other character is, if we can derive the derivative of that function we can use the tangent as additional data to further tweak the character appreciation, for example asshole is increasing the character is more and more disgust, but if it decrease the character appreciate the change positively.

[s0]

tangent but

However the aquarium effect (witnessing limitless history is compelling to some player) do affect the player experience (and linear story based game do exist as a market) and from a gameplay perspective the shift in context affect the way the player interact with the world too, like making the world a dangerous place or affecting scarcity of resource.

i think the idea of having lots of stuff going on in the game world and being able to dip in and out of it is great. i have a strong interest in games that aren't focused around the player's experience.

[Pfotegeist]

Gimym JIMBERT I think we went off with our own interpretations. But I guess something I said gave you an idea.

Here's my attempt at quickly describing how the normal curve could be used. First an introduction.


figure A. normal curve

I looked around for a good description.
http://onlinestatbook.com/2/normal_distribution/intro.html

"But how that would translate to dynamic npc that travel, meet peoples, have adventures with them, without any need to bookkeeping?"
This is what got me thinking about it.

The math is likely to be available as functions, the proper use is another issue. Instead of understanding the use, you can also rely on an interpretation of the normal curve.

Here's a possible scenario:
First your adventurer needs to go on the adventure. 16% of the time they are excited to go, 34% of the time they go, 34% of the time they don't go but considered to later, 16% of the time they forget about it.
Next your adventurer needs to join a party. 2.5% of the time the party has an epic hero and he loves it. 13.5% of the time the party is really good and he liked it. 34% of the time he liked the party. 34% of the time he didn't like the party. 16% of the time he hated it. 2.5% of the time the party has someone who goes renegade, steals things, and abandons so he loathes this party.

The power of this is for every adventurer you encounter there's a chance they had an experience like this. There'd be a huge variation.

This is only practical on a microscopic scale, however. This would be like describing what the adventurer ate for breakfast. It's relevant today, but not in a couple of years. It'd be very relevant if you could ask them what they ate for breakfast.

So on the macroscopic scale, you'd have scenarios that describe several years of someone's life, and they'd have any stat points and references to account for it. They are likely to only have one really good friend (but they could have many) and several acquaintances which they met multiple times while adventuring. I only had to extrapolate that from the microscopic scenario I thought of earlier.

I still can't exactly imagine a realistic lifetime situation. But I suppose you could loop through a predefined path the person enters multiple times after an initial birthing and pseudo-personality trait check.

Using the normal curve is less arbitrary if you need more exact numbers. Also it'd be more effective at giving a realistic outcome than a randomized simulation.

Now I'm worried what I described is a simulation. You'd be pressed to come up with how exact you want it though. There you have it 


Here's a practical use example. A new innovation needs 16% market penetration before it's adopted by the majority. So if you manage to break into the majority the rest buy it. Except the last 16%, they won't purchase it until a similar product is discontinued.

[gimymblert]

Yeah I knew about the bell curve, I didn't know how you thought it could be use for deciding travel or generation, but yeah to distribute parameter in a realistic fashion it make sense. However I'm going a bit further and try to identified deterministic unique NPC through time and space as if simulated instead of using the kind of probabilistic encounter distribution we would normally use (as if the npc could be at many place at the same time but only determine by the player presence in one place, like a bit of quantic coherence things). But the curve is still useful in the determination of that deterministic formula at generations passes.

[baconman]

You make every gameplay element a test of the player, and somehow have the game record relevant data of their reaction (ms to react, fight or flight, their current HP/status, how far from an edge are they before they hit jump; that sort of thing); then you use that controlled data as the commanding aspect of the NPC. You want to replicate the player's success AND failure rate; and THEN - here's the other meta - you want THIS to be ANOTHER LAYER of PLAYER RESPONSE TESTING.

Really, you don't need a LOT of data; maybe 10 records of each statistic you feel is valid for making the AI work... I'd suggest taking the first 13 "tests," disregarding the first three, and then that's all you need. Then the AI can just randomize one of those results, and there you go - valid response.


Total tangent: I was just thinking the other day... what if the strands of DNA are all seeds that factor together to make a prime number... and that all of us and our lives are actually procedurally generated from the get-go? O.o

[gimymblert]

I don't understand your post relative to the problem, not sure it adress the problem

Dna is a clearly a program

[saluk]

I do not see how the parameters of the npc function is that different from the parameters of your tiles with respect to where civilizations are located. "Travel" for instance can be modeled as an oscillation function over time, where the npcs parameters are generated according to the position on the curve that comes up for a specific "time" and "location" being input. As time progresses, those values will be returned at different locations in the world. Each tile can have a "list" of npcs: npc #1, npc #2, and so on. The order in the list becomes a parameter which modifies the seed, used in the equation, coming up with different npcs. EX: npc name = generate_name(seed=5*sin(time+tilex*100+tiley*1000)+npcvalue). You could model the x,y values in one equation, or have separate equations for each dimension, as long as you ensure all of the equations use the same periodicity.

The easiest would be if all npcs only travel between two cities, and all npcs travel the same amount. You would need to use multiple equations to model the npcs who travel a lot or quickly; at the same time as npcs who do not travel much or slowly, or npcs who never travel.

If you want travel to happen on more than just between two spots, it might be best to generate travel curves, and integrate between those on a tile, rather than trying to figure out how to stuff complicated oscilations in one or several linked formulas. Nearby cities would have frequent travel, distance cities infrequent.

I don't know if this is actually possible or makes sense to anyone else but it sounds good in my head!

For player interaction, you could modifiy the equations beforehand (kill npc#5? add an offset the the npc5 seed value so the functions generate someone else for those) or record the changes to be done with post processing (gave npc stan who was a beggar a job, every time npc stan is generated, change his class from beggar to that job)

There are limits, but a lot could be modeled this way I think.

[gimymblert]

Yes that's what I thought as that point, a npc is filtered down to a specific character based on hierarchical data (for example group or type define in higher hierarchy) and tile attribute (let's assume for example a tile can be evaluate as "romantic" or have a job attribute).

A closer to concreteness example is for example at high level the npc are abstract as population, at region level we have a distribution percent of that population, etc ... but if the state of the region has modifier which is for example "at war" it change the distribution, the difference between the original distribution and the modified distribution is "travel" so once you filter down to character you can compare the original distribution to the modified distribution to see if a character has travel, why and what is behavior will be against his own trait modifier ... you can have complex case such as a mother longing for her son which returned back to the war zone to help is home country just based on hierarchical filter.

But yeah I have see that you put list in quote, I'll just had this for any people following this thread, you don't have to have a "stored" list per see, the random generation would work like a random hash based on generated indexes. Let say you have a formula which take an indexes and return a character profile, you just need to generate per tile an indexes that will be filtered down to a unique character and unique behavior.

How do you know which unique character is which tile? well the population is filtered down by space first, before creating the character, through the distribution function, it is basically bound to a virtual index. Let say you have a population of 350 000 characters, the index goes through 1 to 350 000. If there is generation other time you input an offset like I told about in a previous post about tree.  You have each region with different percent of distribution, say 25% each for simplicity sake, the first region indexed filter will refer to each index from 1 to 25% of 350 000, the second will pick off at the offset of this first region and get the next 25% of the index, etc ... which is further filter by social group, jobs, traits, places, etc .... those filter can change other time with modifier (for example place my be fed y a daily loop).

However While procedural, the many template, like the mother longing is soon, need to be human designed ...

There is still the actual structure to be figure out for actual implementation, and some more "complexification" to have a workable and plausible generation (mating, marriage, and off beat generations (sibling not born at the same time, nor entire generation), gender distribution per family and life expectancy)