Is there a way to procedurally generate the history of a world?

Question

I am somewhat intrigued by the diagram found here representing 1800 years of cultural history in an imaginary world some guy created.

This sort of thing would seem to have strong applications for game development, insofar as world design.

It looks like he did this diagram by hand. What I'm interested in is seeing if there is a way to create this sort of diagram programatically.

If you were tasked with generating diagrams in the style of the above from random values, how would you go about it? Are there any particular data structures or algorithms that you would consider?

Answer 1

How accurate do you want to be? A good but complex choice would be simulating all that history:

1. Generate a random region list and adjacencies between these regions.
2. Generate random civilizations with characteristics such as population, belligerence, technology... and populate the regions.
3. Simulate as many years of history as you want, determining outcomes based on civilization characteristics.

E.g.: two adjacent belligerent civilizations have a higher probability of starting a war on each other, which leads to lower population over time. Merchant civilizations have higher resources, but are a great target for invasions. Highly populated ones will grow faster but also have more chances of hunger. Culturally-heterogeneous civs have a lower chance of internal wars (which could lead to breakups.) And so on... Outcomes would also modify the civilization characteristics: higher technology leads to better trading, stronger weapons, etc.

This allows for some procedural storytelling too: you can output not only a territory diagram, but also textual descriptions of history throught time. You can make this system as complex as you want.

---

EDIT: the challenge here is not a technical one, but adjusting the heuristics for realistic and interesting history generation. Take a closer look and think about the 3 aforementioned points... that's pretty much your technical explaination! Translate it to a loop (each iteration can represent as much time as you want, 1 year, half a year, 1 month...) and that's it. You'll have to work the inners (data structures, heuristics) and adapt it to your specific problem and needs. That's the hard part here and nobody can help you, since it's about imagination, trial and error.

There are no common data structures for this problem besides the ones you'll use for almost any problem: lists, queues, trees... and these will be tied for your specific implementation (do I need a genealogic tree? a list of civilizations at war? a queue of tasks for each civ?) Of course you need a list of civilizations too. The choices are obvious and pretty much common sense.

Simulation is a matter of chance/probability and you can make it a thousand different ways with random numbers. Think of any other game where simulation is involved like football managers, RPGs (after all, hitpoints/stats is just combat simulation), strategy games... It's just characteristics (so you'll need a way to store civilization characteristics and data) and random outcomes statistically based on them (so you'll have to randomly change the simulation state based on these characteristics.)

That's the essence of your algorithm: the hard to adjust heuristics: how to distribute characteristics at the beginning of the simulation for each civilization and how to statistically change the simulation state based on them.

In short: your algorithm is just a loop ranging the simulated time with any desired increment. Shorter increments lead to finer historic simulation, but will obviously take longer. Inside your loop there will be a bunch of heuristics like (roughly):

for each civilization
  if civ.isAtWar
    civ.population -= civ.population * 0.05;
    civ.wealth -= 1000.0;
    civ.belligerence += 1.0;
  if civ.population < 100
    civ.negotiatePeace()

After all this work (or during if you don't want to store the data) you must interpret all the simulation state into human-readable format like text, images or whatever you desire. This is trial and error too and very specific for your implementation.

Specific to your question: to generate a diagram like the one in your question you'll have to track world regions (top of the diagram, x axis, that's point 1: generate region list in my answer) and their civilizations (colors in the diagram, point 2) through time (y axis, the simulation loop in point 3.)

State machines are quite good at simulating broad topics (the code sample above is an approximation of a hard-coded state machine) - so you might start by implementing a simple state machine framework that is overall easy to tweak. Each civilisation would start off with one of these state machines and the simulation would run each state machine for each turn. Each state machine would need to be able to interact with other state machine: for example initiating a war would affect another civilisation's state machine, possibly with different outcomes based on their internal state - e.g. if they are in the 'famine' state they would likely want to negotiate peace, but a civilisation 'looking for trouble' would likely retaliate. Each state in the machine would have meaningful effects on the civilisation's metrics outlined above during each 'frame' (wealth, belligerence, populace, etc.). Most importantly you do not need to transition states on every frame - just when opportunity and/or random chance arises: this allows prolonged events (like war) to occur.

Answer 2

Yes, there is. Here's a dirt-simple history generator:

#!/usr/bin/env python
# to create a visualisation, run like this:
#    ./timeline.py --dot | dot -Tpng > filename.png
import sys
import random
from pprint import pprint
# Names is a newline separated list of nation names.
file = "names.txt"
names = open(file, "r").read().split("\n") 
history = []
dot = False
if len(sys.argv) > 1 and sys.argv[1] == "--dot":
  dot = True

def wrap(str, wrap='"'):
  return wrap+str+wrap

def merge(states, names):
  number = random.randint(2,3)
  mergers = [] 
  if number < len(states):
    mergers = random.sample(states, number)
    new_name = random.choice(names)
    states = list(set(states).difference(set(mergers)))
    states.append(new_name)
    names.remove(new_name)
    if dot:
      for state in mergers:
        print '"%s" -> "%s"'%(state, new_name)
      print '{rank=same; %s }'%wrap(new_name)
    else:
      print "MERGE %s ==> '%s'"%( ", ".join(map(wrap,mergers)), new_name)
  return states, names 


def split(states, names):
  number = random.randint(2,3)
  if number < len(names):
    splitter = random.choice(states)
    states.remove(splitter)
    new_states = random.sample(names, number)
    names = list(set(names).difference(set(new_states)))
    states = list(set(states).union(set(new_states)))
    if dot:
      for state in new_states:
        print '"%s" -> "%s"'%(splitter, state)
      print '{rank=same; %s }'%("; ".join(map(wrap, new_states)))
    else:
      print "SPLIT '%s' ==> %s"%(splitter, ", ".join(map(wrap,new_states)))
  return states, names

def revolt(states, names):
  old = random.choice(states)
  new = random.choice(names)
  names.remove(new)
  states.remove(old)
  states.append(new)
  if dot:
    print '"%s" -> "%s"'%(old, new)
    print '{rank=same; "%s"}'%new
  else:
    print "REVOLT '%s' ==> '%s'"%(old, new)
  return states, names

def conquest(states, names):
  if len(states) > 1:
    loser = random.choice(states)
    states.remove(loser)
    winner = random.choice(states)
    if dot:
      print '"%s" -> "%s" [label="conquered by"]'%(loser, winner)
    else:
      print "CONQUEST '%s' conquered '%s'"%(winner, loser)
  return states, names


#ignore empty names
names = [name for name in names if name] #yes, really.

origin = random.sample(names, random.randint(1,3))
names = list(set(names).difference(set(origin)))
history.append(origin) #random starting states

if dot:
  print "digraph g {"
  print "{rank=same; %s}"%("; ".join(map(wrap,origin)))
else:
  print("BEGIN %s"%(", ".join(map(wrap,history[0]))))

while names:
  func = random.choice([merge, split, revolt, conquest])
  states, names = func(history[-1], names)
  history.append(states)

if dot:
  print '{rank=same; %s}'%("; ".join(map(wrap,history[-1])))
  print "}"
else:
  print "END %s"%(", ".join(map(wrap,history[-1])))

Which produces output like this:

Adjust the heuristics to create different graphs.

The simplest way to do this would be to change the func = random.choice([merge, split, revolt, conquest]) line to have more than one function of the same name. For example func = random.choice([merge, split, revolt, conquest, merge, merge]) will lead to nations merging more often.