Procedurally generating one or more families/a small population?

[Icarium]

Hello fellow roguelikers!

One of my hobbies is toying around with making a couple of RL games, and in one of them I need to (or, would like to) procedurally generate one or more large families, but I'm having trouble figuring out a nice way to do it.

What I want to do is basically start with one or more ancestors, and build a (realistic) family tree from there.

For example, I start with Bob and Jane Smith who get married in 1850. Then I give them 1 or more children, and each of those children will get one of the following fates:
a) meet a spouse, but have no children
b) meet a spouse, have one or more children
c) forever alone
(there could of course be other possibilities, but I'm trying to keep it fairly simple for now)

if b) then repeat the same procedure with each child, until we get to present day (i.e. start of the game).

Oh, and to further complicate things: each person's spouse could be from one of the other procedurally generated families in town! Or it could be someone unrelated, e.g. an immigrant.



Or, in other words, what I'm trying to accomplish is to generate/simulate the population in a small town/village over a couple of hundred years. Dwarf Fortress & Toady One seems to be able to do this on a large scale, so I'm hopeful that it's possible for a hobby amateur programmer like me to do it on a very small scale....?!

I've tried a couple of simple approaches with recursive functions, but quickly got stuck in infinite loops... Also, keeping track of fathers, mothers, children, siblings and other relations quickly becomes a mess. (Btw, I'm programming in C, and using a ton of pointers for this.)

So I would really appreciate some input, thoughts and fresh ideas on this issue, if anyone has any! I feel like I've painted myself into a corner and can't find a way out. Maybe someone else is able to see a way out? I'm sure there are many different approaches to solving this problem, but right now I can't see them...

Thanks in advance for any input, ideas and thoughts!

[XLambda]

This is kind of hard to do if you don't have the right data structures. A tree would be the obvious solution, but doesn't work out 100% due to the fact that it should not only track bloodlines, but also marriages. I would give each node an additional pointer to a possible husband - it's technically a directed graph, but who cares if you use it the right way. Just model the children as child nodes of the mother (or father) only.

You can now easily run tests on such a structure to see whether a relation between two people is incest or in any other way undesirable. If you add a birth date to each node, you can check for age discrepancies and even kill people off if you iterate over years.

Now if you want to have several families, you'll need what is called a forest: a set of trees, one for each family. This makes it especially easy to introduce immigrants: just add a new tree with a single node to the forest.

So, in every cycle of your algorithm, you could check the leaves (the people who don't have children) and if they are married, give them a chance to get kids. If they aren't married, give them a chance to find a husband. Check all leaves for the criteria mentioned above and if you find one, let them marry (i.e. set the pointers). Don't forget to check whether they actually are old enough to marry or have kids! (Also, be careful not to let people marry themselves, or weird stuff like that.) Then you could run once over the whole forest and check whether anyone dies. If you let this run a set amount of years, it will terminate.

You can extend this easily. One of the problems with this is that all children are generated at once. If you want to change this, just maintain a list containing all married mothers and once per iteration do the birth chance thing.
Another interesting feature would be the addition of proper surnames. Again, this is really easy to do.

Now, this is a fairly unoptimized algorithm and it will take long to generate a realistically large population, but you don't necessarily want those, because millions of people are kind of hard to have in a roguelike.

I know that this is possibly a bit hard to understand. I'm not very C-savvy...

EDIT: Please note that you'll have to do a fair bit of experimenting with the nondeterministic parts of such a system. There is always a lot of potential for that kind of stuff to go horrifically wrong. Especially child birth rates. Also, if you have very strict incest constraints then the introduction of immigrants should be high, or your people will die out because they're all related.

[XLambda]

wrong button 

[Omnomnom]

I would split this into four parts/stages of work: Simulating, recording and querying, optimizing.

Simulation
Maintain a list of people in the town you are tracking. This is just a list. For each person (entry in the list) only store very basic info. I would just store their full name, gender and age and nothing else. Run the simulation forward a year at a time. Each year, for each person in the list, calculate whether they hook up with someone, have kids, or die or whatever. If they die, remove them from the list. If they marry someone outside the pool, or have kids then add the new spouse or kids to the list. Continue the simulation for however many years. There's no memory in this simulation, nothing is remembered about past years or generations, but that's intentional for demarcation and to keep it simple.

Recording
As the simulation progresses, each time a recordable event happens (marriage, death, birth, etc), create a record for it with relevant info (eg for a birth record who the parents were, for a marriage record who married) and add the record to a list. This list is much like a book being maintained in the village hall of all new births, deaths, marriages, etc. This is the memory part, whereas the simulation is the current state part.

Querying
Now say you want to know if two particular people, by name, are related. All the information to answer this is in the history list. I would write a function like bool AreRelated(name1, name2) which goes through the history list to answer the question. You can run such queries as the simulation progresses (eg find out if two people are related to determine if they can marry, ie to prevent incest).

Optimizing
You might think I am crazy above as I am saying run queries against a list when that would be very inefficient. A tree is obviously much more efficient. You could generate a tree for querying from the history list, but I wouldn't bother unless/until I found a performance problem. For one thing you rapidly get the game working this way and you find out where the performance bottlenecks are and they might be easily overcome without a complex data structure. eg perhaps the only performance problem will be working out a common ancestor of two people, in which case you only need a tree for querying that holds descendant/ancestor info and not marriage.

Just designing a catch-all tree that can be used for any possible query seems like it could take more time than all of the above combined. Then you have to spend a lot of time implementing the super tree. Then think of all the hours that are inevitably lost on bug hunting when something weird happens with some pointer...

And just think, you might find that from the player point of view the extra delay from querying a list rather than a super treelike structure is completely unnoticeable, in which case wouldn't you kick yourself for spending ages writing the super tree? Then again I am quite lazy. I gave it some thought but I have no idea how to design a tree structure that can hold marriage relationships and descendant/ancestor relationships, the problem made my head hurt so I avoided it.

[requerent]

I think your data structure is going to depend on a kinship system. The kinship system will govern what pieces of information you need to track to result in a believable system.

You simply cannot localize this idea to a single town. Marriages exist for a number of reasons throughout a variety of cultures. In most every pseudo-civilized culture, however, marriages are subject to a particular kinship schema- typically to create economic unions between villages (note, 'raiding' is an economic activity. An economic union can be an agreement not to raid one another).

Suppose we start on the Village level. Two villages unite- the kinship system within the culture will be a combination patrilocal or matrilocal and patrilineal or matrilineal. Locality describes what residence the couple moves into, lineality describes the passage of property and with which bloodline they trace their ancestry (this is basic anthropology). Then there is how often a village separates to make resource gathering more efficient.

Even up to modernity, before hi-speed travel, marriages continued to honor kinship systems throughout the world. The development of cities can be broken down into village-esque bloodlines, with the simple exclusion of territorial differences. From there, kinship systems were in full effect for a very long time. I'm not sure when kinship systems started becoming unfashionable, but it probably started with the French or the Americans.


Anyways- first think about what rules you want to have to govern marriages. If you're starting from the very beginning- you have to consider splitting factor (how often a married couple moves away to make their own village), how village alliances take place, etc. Then to make towns, you just have villages occupy the same places.

This might be taking it too far, but at the very least you need an algorithm that determines what the basis for coupling is.

[Snargleplax]

I think you should listen to Omnomnom.  If you're tying yourself up in knots and circularities trying to produce working data structures that resemble family trees, I can almost guarantee you're prematurely optimizing.  Use lists, keep it simple, get it working.  You may find that the "slow" approach is blazingly fast.  Tree implementations carry overhead, as well -- asymptotic complexity (big-O) isn't everything.  I'd wager the population sizes necessary to make your concept work are far smaller than anything you'd need to worry about doing O(n) scans on, unless you're doing many of them in a single frame.

If, once you've got it working this way, you discover a performance problem, you can narrow it down and implement targeted optimizations in an appropriate way.  Most likely this would involve adding pointers between list nodes, or some auxiliary index structure that points into the list.

If you do it this way, you're unlikely to get stuck trying to come up with a one-size-fits-all structure that can handle all your current and future needs.  Requerent points out the many different rule structures that can accompany marriage, inheritance, etc. (check out Crusader Kings 2 if you really want to get the flavor of this).  However, I don't think the answer is to try to figure everything out ahead of time -- it's just too easy to wind up changing your mind later.  Instead, recognize that this is a high-variability area and don't link it too closely with lower-variability concepts such as the simple fact of having a population of people.

Why should family relations be the primary indexing structure for them, anyway?  Sure, there are times when that's the important aspect, but aren't there other cases too where it doesn't matter?  If one village wars with another and you need to find troops for the militia, it's more about who can swing a sword than who can marry whom.  Or if you're figuring out who's going to die of old age this year, you care about sorting by age, which again has nothing to do with relatedness.  There are countless examples -- the point is not to couple your core data structure too tightly to a particular use case, because you'll go nuts adapting that specific structure into other specific needs.  Much better to just use a simple structure that can adapt easily as needed.

[requerent]

Multiple data structures for different purposes.

[Icarium]

I just want to say thanks a lot for all your replies!
They've given me a lot to think about!
Especially Omnomnom, Snargleplax and Xlambda! You have some great points and you've opened my formerly stuck mind, so I'll be re-reading your posts as soon as I have the time (lots of work coming up the next couple of weeks)

Also, requerent has a good point. Maybe I should explore different data structures for different purposes...!

Thanks again!
So I'll report back when I have something to report!