next »

[gimymblert]

So I'm laying out the basis for procedural generation of persistent and unique NPC across their entire life, many generation and space (travel).

But right now I'm stuck on plausible genealogy. Let assume that there is infinite ancestry and infinite descendant.

Now genealogy would be simple if we had a periodic symmetric tree (as the same number of children for all ancestor), ie all children are born at the same time. If we know the time of the first generation as an arbitrary number we know it's an offset that grow exponentially at each generation. For example assuming a binary tree, we know at arbitrary generation x that total birth was x² so every indexes in that interval belong to the same generation (and to find the total number of person who live once I'm sure there is a mathematical formula to found out). This is key we don't need to know the history to infer the population's size.

Let say you have a family line. You have a mother, she hit her fertility maturity's range and give birth to a random number of child at random time. So the genealogy have a random number of branch at random time from the root ... Less easy to infer generation locally.

Let's simplify the problem to a single line (a path in the tree from 1 ancestor to 1 descendant) and assuming that all NPC are women that spontaneously give birth (men don't give birth so they don't generate branch directly, they are dead end, so we can safely ignore this point).

We have a random series where each new point is the birth of a new npc, let assume you have an input t that is use to "query" the function such as it return if the character is born or not. The problem is that all descendant's birth time depend on the sum of all the previous interval between each birth + its new random interval, which is non local ... The same problem apply for the random branch, how do we know which "branch indexes" to not visit y generation down because it was never generated?

The think is there a plausible solution to this that would give at least the illusion of randomness? In a query without history?

One solution could be that we can use something like how elite generate galaxy, ie we partition time into regular "time zone" inside of which we generate a random number to get the starting point. No clue about turning that into a tree ...


EDIT: What I'm trying to determine is for a given time t, all the branches (list of indexes) that exist (character birth) without having the history of state (building the whole tree).

I have demonstrate it's possible with a symmetric ordered tree periodic on t (ie all generation happen at given interval, character indexes are predictable because of ordered tree).

I'm trying to determine if there is a pseudo random way to have a non symmetric tree with (apparently) non periodic branch and still query all the existing branch at time t.

OR if there is a better way to create the illusion of tree without the hassle to predict the tree random recurrence.

EDIT2 The point was to avoid simulation like we do in generating landscape with perlin noise, hence why I'm investigating random interval in a tree (where each branch have a differing growth rate).

Determining if something random happen is what procedural generation do! The idea is to expend it to the time domain,more precisely to the interval (random birth) between generational birth. I look at L system, it's iteratif (ie next state depend heavily on previous state), I'm looking for something with the property of locality (you don't need to know the previous state (sand history of states) to determine a point at a given index (like function f(x) = x², you put x and you get an associated value), i'm trying to define for an input t if a character is born and at which indexes

[BorisTheBrave]

This is the same question as the last one.

You cannot define things as a stateful process, and hope to reduce it to something simpler afterwards. Start from something easy to generate, and build it into something you like the look of.

E.g. why not generate each generation randomly, but separately. Then randomly decide who are parents/children between generations.

[gimymblert]

Yes and no, it's a part of the same question, BUT I solve the other part (travel and all) and this is what remain. I explain the problem from the starting perspective, ie this is what it should looks like (a tree) even though we might get a pseudo method that might not be a tree but looks like one (as we do with landscape generation, smoke and mirror to give the illusion of fire, but first you need to exp)lain the fire).

Yes I was thinking something along the like of your solution, generate each generation, decide an offset for every index, group them by sibling, assign sibling to previous generation indexes within the interval of fertility. Have different growth tree with different generation rate... The problem is that each family line have a set growth rate for eternity, I try to mix that last point and see if I can dynamically shuffle the growth tree, any idea?

Also each generations have a bucket of "infertility" where character who won't have kid are listed separately.

edit: Now I have a better descriptor too, procedural persistence of infinite family line.

[gimymblert]

I think I should have describe it as "procedural persistence of infinite family line", the goal is to have a tool for world building and story generation, where the past and future are query from a formula rather than simulated. This last point open the scale to infinity as you remove dependence.

An incomplete method might be:

• To generate list for each generation and use the growth formula to define the size. SO n² growth have t1=1, t2=4, etc ...
• For each generation list we group character's indexes in sibling group.
• We (pseudo) randomly assign those sibling to fertile parents.
• We offset birth time within the fertility range of parents.

This Method Have the advantage of giving more flexibility as you can do weird stuff with the growth formula and not depend on a tree (let say you want a an infinitely stable population, family lines with cycle of growth and decrease, or weird family lines that decrease from infinity to nothing as time progress)

The main problem is that all generation are still kinda sync together, we can't have a family line that grew more rapidly during a certain time. We can have multiple family lines with different growth rate and formula, but each family line is stuck inside it's growth rate profile. I wonder If there is a last method to shuffle this one a bit

[gimymblert]

It's not the same problem but I put it there in case someone make use of it:

Travel of NPC in randomly generated map in an infinite world:

the NPC is generated as a last step not as a starting structure, place own npc instead of npc being at a place, it work because you a virtual indexes of npc (the population number) and you distribute the indexes to the region through a distribution algo, you do the same for attribute jobs, etc ... finally the npc is what is filtering down into the given "index".

So travel is matter of running additional filter on the population based on time, for example npc indexes will be distributed at work teh day and at home the night, let say a place is at state "war" it change the distribution at a region level, since you still have access to the generation at a given place you can compare the original distribution adn modified distribution and find who flew his house, based on other attributes you then create a plausible story to explain why. So instead of having events driving state, you use state to generate events that explain them (reverse causality!)

To know where the npc is at any moments precisely:

- We know place are generated hierarchically (region are split in cities, which are split in districts then in buildings then in rooms). It as a fractal tree like structure that make easy to compute things.
- Even within sibling there is a structure (entrance to hall, to living room, to bedroom).

We leverage this to compute path:

- From children to parent with length modified by transportation method
- We know by generation the size of each element, therefore we can infer the length of path by element

We can do this at the precision we want.

[BorisTheBrave]

The problem is that each family line have a set growth rate for eternity, I try to mix that last point and see if I can dynamically shuffle the growth tree, any idea?

I don't see how that's a problem at all. When generating the links between two generations, there's no obligation to enforce a fixed number of children for each parent. And the average growth rate between two generations is easily set by the number of people generated.


Unrelatedly, you need to spend more time on writing your posts. Your english is decent (though I sense you aren't a native english speaker), but your posts are often rambling messes where you don't clearly define what you want, use consistent terminology, and often change the question halfway through. I often have serious difficulty figuring out what the question is amist all these words. Following up with further edits or posts is also off-putting - if you haven't put the time into thinking about your problem before coming here, why should I put in the time for you?

My advice would try to structure your questions as first describing the setup of your game so far, then the particular problem you face, followed by a one line question of exactly what you are looking for. If you have any ideas of your own, leave them for a separate section - intermixing your ideas and your problem both makes it harder to understand, and constrains other users on what suggestions they can put forth.

[gimymblert]

I understand your concern, But i'm not sure how to improve because I think I did just that (but it's not enough).

- 1st line give the overall context, 2nd narrow the problem, within the context, to the goal to achieve.
- 2nd paragraph give an example of a simple solution that don't work to illustrate the problem.
- The third small paragraph highlight the difference with the real problem, to show why it don't work to contrast what the problem is (aka it's genealogy tree but non periodic).
- The fourth small paragraph is all about simplifying the problem by eliminating parameters with no impact.
- The fifth is here to discuss the fine point of the problem and direct to the problematic part.

In conclusion, I try to walk people from the general to the specific, exposing the parameter of the problem and directing them to the difficulty. The problem was not simple, it's about generating genealogy like we generate landscape, through a simple query that don't need context.

How Should I have done it?

[BorisTheBrave]

Here's my attempt based on what I've understood of your question.

I'm developing a game that procedurally generates entire worlds with NPCs where you can inspect any of the world in any time period.

As the world and timeline is huge it's not practical to start at the beginning and simulate forward - I seek procedural patterns that can quickly answer questions about a given location and time without storing a lot.

I'm having difficulty with finding an efficient method for generating family trees (genealogies) of the NPCs. For sake of simplicitly, lets just say that generations occur in lock-step and NPCs produce children without any need for a partner, so that family trees are just conventional tree structures. I want to be able to query the children and parent of an NPC so I can explore the relevant part of the family tree without loading everything.

My first attempt was to assume every NPC has a constant number, say x, of children. This makes it quite easy to work out the relationship between parents and children by numbering each NPC in a generation. You can find the parent by dividing by the NPC index by x. And conversely, find the range of children by multiplying by x and reading the next x NPCs.

But I'd like to find something that is more plausibly random looking than constant number of children.

I've omitted much from your original post that frankly I didn't follow fully, so perhaps you can critisize me on reading comprehension.

[gimymblert]

That's much better, that's the same things, with less information, but that does demonstrate your point, thanks that is helpful!