Czy istnieje sposób na proceduralną generację historii świata?

Intryguje mnie nieco znajdujący się tu diagram przedstawiający 1800 lat historii kultury w wyimaginowanym świecie, który stworzył jakiś facet.

Wydaje się, że tego rodzaju rzeczy mają mocne zastosowania do tworzenia gier, o ile są projektowane na cały świat.

Wygląda na to, że wykonał ten schemat ręcznie. Interesuje mnie to, czy istnieje sposób programowego utworzenia tego rodzaju diagramu.

Gdybyś miał za zadanie generować diagramy w stylu powyższym z losowych wartości, jak byś to zrobił? Czy są jakieś szczególne struktury danych lub algorytmy, które należy wziąć pod uwagę?

Jak dokładny chcesz być? Dobrym, ale złożonym wyborem byłaby symulacja całej tej historii:

1. Wygeneruj losową listę regionów i przylegania między tymi regionami.
2. Generuj losowe cywilizacje o cechach takich jak populacja, wojowniczość, technologia ... i zaludnij regiony.
3. Symuluj tyle lat historii, ile chcesz, określając wyniki na podstawie cech cywilizacji.

Np .: dwie sąsiadujące ze sobą wojujące cywilizacje mają większe prawdopodobieństwo rozpoczęcia wojny między sobą, co z czasem prowadzi do zmniejszenia populacji. Cywilizacje kupieckie mają większe zasoby, ale są doskonałym celem inwazji. Te bardzo zaludnione będą rosły szybciej, ale także będą miały większe szanse na głód. Kulturowo heterogeniczne cywilizacje mają mniejszą szansę na wojny wewnętrzne (co może prowadzić do rozpadu). I tak dalej ... Wyniki zmodyfikowałyby również cechy cywilizacyjne: wyższa technologia prowadzi do lepszego handlu, silniejszej broni itp.

Pozwala to również na pewne proceduralne opowiadanie historii: możesz wygenerować nie tylko schemat terytorium, ale także tekstowe opisy historii w czasie. Możesz uczynić ten system tak złożonym, jak chcesz.

EDYCJA: wyzwanie nie jest techniczne, ale dostosowuje heurystykę do generowania realistycznej i interesującej historii. Przyjrzyj się bliżej i pomyśl o 3 wyżej wymienionych punktach ... to właściwie twoje techniczne wyjaśnienie! Przetłumacz go na pętlę (każda iteracja może reprezentować tyle czasu, ile chcesz, 1 rok, pół roku, 1 miesiąc ...) i to wszystko. Będziesz musiał pracować wewnątrz (struktury danych, heurystyka) i dostosować go do konkretnego problemu i potrzeb. To jest trudna część i nikt nie może ci pomóc, ponieważ dotyczy wyobraźni, próby i błędu.

Nie ma wspólnych struktur danych dla tego problemu poza tymi, których będziesz używać do prawie każdego problemu: listy, kolejki, drzewa ... i będą one powiązane dla twojej konkretnej implementacji (czy potrzebuję drzewa genealogicznego? Listy cywilizacji na wojnie - kolejka zadań dla każdego miasta?) Oczywiście potrzebujesz również listy cywilizacji. Wybory są oczywiste i mają zdrowy rozsądek.

Symulacja jest kwestią przypadku / prawdopodobieństwa i można ją robić na tysiąc różnych sposobów z liczbami losowymi. Pomyśl o każdej innej grze, w której bierze udział symulacja, takiej jak menedżerowie futbolu, gry RPG (w końcu punkty wytrzymałości / statystyki to tylko symulacja walki ), gry strategiczne ... To tylko cechy (więc potrzebujesz sposobu na przechowywanie cech i danych cywilizacyjnych) i losowe wyniki na ich podstawie statystycznie (więc będziesz musiał losowo zmienić stan symulacji w oparciu o te cechy).

To jest istota twojego algorytmu: trudna do dostosowania heurystyka: jak rozdzielić cechy na początku symulacji dla każdej cywilizacji i jak statystycznie zmienić stan symulacji na ich podstawie.

W skrócie: twój algorytm jest po prostu pętlą obejmującą symulowany czas z dowolnym pożądanym przyrostem. Krótsze przyrosty prowadzą do dokładniejszej symulacji historycznej, ale oczywiście potrwają dłużej. Wewnątrz twojej pętli będzie kilka heurystyk takich jak (z grubsza):

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

Po całej tej pracy (lub podczas, gdy nie chcesz przechowywać danych) musisz zinterpretować cały stan symulacji w formacie czytelnym dla człowieka, takim jak tekst, obrazy lub cokolwiek chcesz. Jest to również próba i błąd, bardzo specyficzna dla twojej implementacji.

Specyficzne dla twojego pytania: aby wygenerować diagram podobny do tego w swoim pytaniu, musisz śledzić regiony świata (góra diagramu, oś x, to jest punkt 1: wygeneruj listę regionów w mojej odpowiedzi) i ich cywilizacje (kolory w wykres, punkt 2 ) w czasie (oś y, pętla symulacyjna w punkcie 3 ).

Maszyny stanowesą całkiem dobre w symulowaniu szerokich tematów (powyższy przykład kodu jest przybliżeniem zakodowanej na stałe maszyny stanów) - więc możesz zacząć od wdrożenia prostej struktury maszyny stanów, która jest ogólnie łatwa do poprawienia. Każda cywilizacja zaczynałaby się od jednej z tych maszyn stanowych, a symulacja prowadziłaby każdą maszynę stanową dla każdej tury. Każda machina stanu musiałaby być w stanie współdziałać z inną machiną stanu: na przykład zainicjowanie wojny wpłynęłoby na machinę stanu innej cywilizacji, prawdopodobnie z różnymi skutkami opartymi na ich stanie wewnętrznym - np. Gdyby były w stanie „głodu”, prawdopodobnie chcą negocjować pokój, ale cywilizacja „szukająca kłopotów” prawdopodobnie zemściłaby się. Każdy stan w maszynie miałby znaczący wpływ na cywilizację ” wskaźniki przedstawione powyżej podczas każdej „ramki” (bogactwo, wojowniczość, ludność itp.). Co najważniejsze, nie musisz zmieniać stanów na każdej klatce - tylko wtedy, gdy pojawi się okazja i / lub przypadkowa szansa: pozwala to na wystąpienie długich wydarzeń (takich jak wojna).

Tak jest. Oto prosty w historii generator historii:

#!/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])))

Który produkuje takie dane wyjściowe:

Dostosuj heurystykę, aby utworzyć różne wykresy.

Najprostszym sposobem na to jest zmiana func = random.choice([merge, split, revolt, conquest])linii, aby miała więcej niż jedną funkcję o tej samej nazwie. Na przykład func = random.choice([merge, split, revolt, conquest, merge, merge])doprowadzi do częstszego łączenia się narodów.