# Procedural generation of plausible genealogy tree with time query without history [closed]

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?

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).

• I am not sure what is the problem? To determine if something random will happened? That is not possible by definition. You can only check be visiting the path(or checking result of random roll). Or you want to generate good starting point of simulation? Or you want change your random generation to something deterministic that look ok? You should probably ask one and clear question. – wondra Jan 16 '15 at 15:52
• Though your question sounds very confused, you might look into L-systems. They are used to generate something that look natural. – wondra Jan 16 '15 at 15:54
• 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 – user29244 Jan 16 '15 at 17:56
• Problem is, if your f(x) is something like f(x) = x * rand(x), you cannot "determine" the value. You need to evaluate the rand function, which is not deterministic. – wondra Jan 17 '15 at 15:09

Let assume that there is infinite ancestry and infinite descendant.

If we can dial that down a little bit (because infinite simulations are hard), we can take a pretty simple concrete approach, and generate them up front.

Choose some parameters, like, say

• a stable population
• of one million people
• over one million years
• 50% gender balance
• fertility ages 15-50.
• (We don't necessarily need to choose a lifespan; keeping the population stable will imply one.)

psuedocode:

Generate initial population, one million records, random ages.

For year = 0 to one million:
{
For each citizen:
{
Decide if they hook up, with whom, and reproduce
Add new birth records
Decide if they die (biased to keep population stable)
Add date of death to their record
}
}


If average age to reproduce is 33, and each female produces an average of 2 children (around age 33), then the number of records is:

1e6 * 1e6 / 33 = ~30 billion records


That's kind of a lot. Maybe 50,000 citizens over 10,000 years is enough? Then we have only:

5e4 * 1e4 / 33 = ~15 million records, quite tractable.


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

If your player is a traveler in time and space, we could generate this sparsely, only when they visit a particular time and place. Then we'll need to "stitch together" genealogical regions if they start visiting more of the nearby times or planets, with plausible genealogy.

Even if you show huge crowds, they only need to have a story if you meet them or click them...

• 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). – user29244 Jan 16 '15 at 18:54
• Sorry, didn't understand the rules. :-) – david van brink Jan 16 '15 at 22:18
• No problem, it seems people have hard time understanding the unusual premise, generally it also ask to think laterally like replacing cause with correlation or reversing the generation logic. For example for travelling, 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" – user29244 Jan 17 '15 at 4:57
• 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!) – user29244 Jan 17 '15 at 5:01
• Now I'm looking for a similar trick about generation where I fake randomness as much as possible, but since different branch evolve at different speed, I Have yet to find a consistent way where I can have instant stateless query without generating the past first (however a "sampling" through time, like a t+1 or t-1 is okay, as long all they are not dependent on further past "t"). I'm also looking to see if hierarchical organisation of time might help or transversal (sibling to sibling) hierarchical grouping help too. If you have any idea from this explanation ... :) – user29244 Jan 17 '15 at 5:06

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 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.

After the edits, if I get it right - you are overcomplicating things:
you need a single level of n-ary tree that, looks like it has all previous levels generated randomly, right? Well, why not take n-ary tree level, for simplicity binary tree.
Lets say you want 6th level, that is 32 elements if that is full binary tree. Now generate random 32-bit integer AND it with the 32-member array if true, there is a person, if false there is null member.

int[] array = new int[1 << level];
for(int i = 0, int r = rnd.next(), i < 32, i++)
{
if(r & (1 << i))
array[i] = new Person;
else
array[i] = null;
}


to further enhance randomness, you can use the idea of perlin noise - "overlay" several random numbers, each with different "locality".

int r_alpha = rnd.next();
for...
if(i % 32 == 0)
r_alpha = rnd.next();
if( (r | r_alpha) & (1 << i))
...


ofcourse, it will probably need to be more complicated than simple OR or AND(to simulate families, which should be probably aligned blocks of persons), but you will get a level of binary tree, PLUS you should be also able to compute next and previous levels if needed as you can tree it as array-stored binary tree(with computable index shift).

Edit:
Well, I do connect family here. That thing is a tree! You can query their parents - their "parents" are at virtual array index floor((i - 1)/2), siblings are at i-1 or i+1 (depending one whether it is left or right sibling), as well as you know children of current generation will be at 2i + 1 and 2i + 2. By virtual indices I mean indices for not-generated tree parts, and the array[0] is actually at virtual index of all_previous_levels_count = (1 << level) - 1;. I am sure you wont have any problems to exapand this binary tree example to 2-3 or n-ary tree. You can get the requested previous generation persons by querying siblings and determining whether their (grand) parents still live. As if there is a person, their parents must have existed at some point.

• Yes it's "overcomplicated" in that the requirement is to have procedural persistence of family line. Creating a character is trivial, creating infinite character too, even persistent. However Having the infinite family line would be a fantastic tools for story generation and world building! AS I understand it you generate the NPC there but don't connect the family line! Null character might generate a family line connection next generation ... However I thought up a "half bake" solution that don't have the growth desync :/ , thanks! – user29244 Jan 17 '15 at 20:29
• As I can see, you do not know whole n-ary tree theory, I tried to clarify it a bit with edit. – wondra Jan 17 '15 at 22:52
• @user29244 I just realized, you can query whether two people are related for n generations back without actually generating any of their ancestors! You just divide and floor their virtual id by requested 2^generation, if it is equal, they are related. – wondra Jan 17 '15 at 23:11
• It's just i'm sure what are the variable refer to in your code. Are you declaring one array per generation? then fill that array with random id? or is it the whole tree? it seems t=very inefficient if the array have null member, I'm not sure what concept this is supposed to expressed ... Im' just confused, I'm a designer first so maybe there is some code pattern I don't get here! – user29244 Jan 18 '15 at 3:15
• @user29244 Well, infact a bit of both - you physically generate only one part of huge(infinite) virtual tree, which is stored in linear array. For simplicity, it is one "physical" array per needed generation(=per tree level), with upside you dont need previous generation (though you can query/generate them on request, since they have computable indices from current generation). If you dont like null people (32/64bit pointer for each), you can create smaller array and hash it somehow, though it would be probably mess. – wondra Jan 18 '15 at 11:49