Wie funktionieren Algorithmen zur Historienerstellung?

19

Ich habe vom Spiel Dwarf Fortress gehört, aber erst jetzt hat einer der Leute, denen ich auf Youtube folge, einen Kommentar dazu verfasst ... Ich war mehr als überrascht, als ich bemerkte, wie Dwarf Fortress tatsächlich eine Geschichte für die Welt hervorbringt!

Wie funktionieren diese Algorithmen? Was nehmen sie normalerweise als Eingabe außer der Länge der Simulation? Wie spezifisch können sie sein?

Und wichtiger; können sie in Javascript erstellt werden oder ist Javascript zu langsam? (Ich denke, das hängt von der Tiefe der Simulation ab, aber nehmen Sie die Zwergenfestung als Beispiel.)

jcora
quelle
3
"Können sie in Javascript erstellt werden?" Die Antwort lautet natürlich Ja, aber es hängt davon ab, wie schnell Sie die Ergebnisse erhalten und wie komplex sie sein sollen. Die Zwergenfestung braucht auch eine Weile - und sie verlangsamt sich, wenn die Welt altert! Solange Sie also einen flachen Verlauf wünschen, können Sie dies in Javascript tun. Dies hängt also davon ab, wie komplex der Verlauf sein soll.
Doppelgreener
2
Er bedeutet "auf der Ebene der Zwergenfestung", wie in der Skala.
MichaelHouse
2
@Bane Ja, ich meine, Sie können ändern, wie viel Geschichte es in DF geben wird. Wenn Sie eine Welt eröffnen, wird zuerst zufällig Terrain erzeugt, und dann wird die Welt vor Ihren Augen altern und dabei Geschichte schreiben. Sie sehen, wie Reiche expandieren und schrumpfen, wie sich das Gelände verändert, wie Wälder wachsen und zurückgehen, wie Gebiete heimgesucht werden (oder nicht mehr heimgesucht werden) und so weiter. Es schreitet Jahr für Jahr (oder mehrere Jahre hintereinander) vor Ihren Augen voran. Dies geht so lange weiter, bis Sie sagen, dass es aufhören soll. Je weiter Sie kommen, desto langsamer wird die Generierung (aufgrund der CPU-Auslastung, nicht der Spielmechanik).
Doppelgreener
1
Um ganz klar zu sein: Je älter die Welt ist, desto langsamer lässt sich jedes Jahr rechnen. In einer jungen Welt wird es in den ersten Jahren schnell gehen, in einer hundert Jahre alten Welt könnte es eine Sekunde oder ein paar Sekunden dauern, bis das nächste Jahr fertig ist.
Doppelgreener
1
Oh, das weiß ich. Mit "Tiefe" meine ich nicht die Anzahl der Jahre, sondern die Anzahl der Ereignisse und die Genauigkeit der Simulation. Man kann einfach eine Anzahl von Leuten behalten, die ein Imperium hat, oder man kann tatsächlich eine Klasse Personhaben, die Aufgaben erledigt, zur Armee geht usw. Flach wäre es, wenn die Größe des Imperiums über die Ergebnisse von Schlachten entscheidet, aber tief würde jeder Soldat für sich kämpfen lassen.
Jcora

Antworten:

27

Zunächst einmal gibt es einige Hinweise für die Geschichtserstellung über die Zwergenfestung. Jemand hat vor einiger Zeit in den Bay12-Foren nachgefragt , und ein Protokoll wurde geteilt, und Sie können herausfinden, wo die Diskussion beginnt, indem Sie nach "Unser heutiges Thema ist die Generierung von Welt und Geschichte" suchen.


Ich weiß nicht genau, wie Dwarf Fortress das macht, aber ich werde erklären, wie ich vorhabe, einen sehr einfachen ersten Entwurf in meinem Spiel umzusetzen. Ich werde einfache zellulare Automaten verwenden . Wenn Sie diese Sporen-Prototypen wie Zellkultur und Biom durchsehen.

Bildbeschreibung hier eingeben

Dies sind Beispiele für zellulare Automatisierungen und was sie produzieren können. Im Wesentlichen werde ich Regeln für verschiedene Rassen erstellen. Einige Beispiele für Regeln wären:

  • Ihre Feindseligkeit gegenüber anderen Rassen
  • Ihre Klimapräferenzen
  • Ihre Ressourcenanforderungen
  • Ihre Geburtenraten und Lebensspannen
  • Ihre Wünsche (Technologieforschung, Handel, friedliche Existenz, Weltherrschaft)
  • Ihre Fähigkeiten (Strukturaufbau, Ressourcensammlung, Kriegsführung usw.)
  • Und so weiter...

Der wichtigste Input für all das ist eine Welt, in die man diese Rassen stürzen kann. Das Gelände bestimmt ihre Vorlieben und Ausdehnung. Wenn Sie also eine Welt geschaffen haben, wählen Sie zufällige Orte in der Welt aus, an denen diese Rassen angemessen leben würden, und lassen Sie sie los. Jetzt fängt das Interessante an. Jetzt, da Sie Land und Rassen mit Wünschen und Fähigkeiten haben, können Sie damit beginnen, eine Geschichte aufzubauen. Diese Rassen sammeln Ressourcen und bauen dann Strukturen auf:

  • Städte in ressourcenreichen Gebieten mit hoher Lebensfähigkeit.
  • Straßen verbinden die größeren Städte.
  • Brücken über Flüsse.
  • Tunnel durch Berge.
  • Festungen in der Nähe der Front der Expansion als Reaktion auf Schlachten.

Jede Struktur kann von anderen Völkern überfallen / erobert werden. Je länger ein Bauwerk (wie eine Stadt oder eine Festung) in der Geschichte existiert, desto schutzwürdiger ist es, desto schwerer ist es, es zu übernehmen. Und umso wünschenswerter ist es für Rennen, die Kontrolle wollen. Schlachten werden dort ausgetragen, wo sich Rennen treffen (mindestens eines ist feindselig). Schlachten werden nach Orientierungspunkten oder nahegelegenen Strukturen benannt, oder wenn der Kampf bedeutend ist oder die Orientierungspunkte nicht benannt sind, werden die Orientierungspunkte nach dem Kampf benannt.

Straßen, Brücken und Tunnel werden durch Handel und Transport von Ressourcen erweitert. Jeder hat einen maximalen Durchsatz, der sich mit dem Ressourcenaufwand erhöhen kann. Eine steinerne Festung inmitten von Grasland bauen? Diese Straßen werden stark genutzt, um den benötigten Stein zu transportieren. Sie werden größer und bekommen einen Namen.

Naturkatastrophen wirken sich auf die Bevölkerung und den Verlauf der Geschichte aus. Erdbeben können eine Stadt in Trümmer verwandeln oder einen Tunnel einstürzen lassen. Eine Flut kann eine Straße oder Brücke auswaschen.


Es ist nicht so tiefgreifend wie die Zwergenfestung, aber es ist ein Anfang. Nun, wie Sie sich vorstellen können (und wie Johnathan Hobbs sagte), werden umso mehr Zellen simuliert, je mehr sich diese Rassen ausdehnen. Es werden nicht nur mehr Zellen simuliert, sondern die Simulationen sind auch komplexer, da jetzt Strukturen aufgebaut / aufrechterhalten werden müssen, Kämpfe um Löhne, Handel um ... Handel und so weiter. Das wird für jede Sprache schwierig. Javascript wird möglicherweise früher langsamer. Sie können jedoch immer auf Komplexität verzichten, um die Geschwindigkeit zu verbessern.

Es ist alles eine Simulation (wenn auch komplexe), Sie zeichnen nur die wichtigen Ereignisse auf und nennen es Geschichte.

Ich habe auch gerade einen Bay12-Forumsbeitrag für Leute gefunden, die sich Gedanken darüber machen, wie die Generation der Zwergenfestung schneller werden kann. Ich habe es nicht durchgelesen, aber es kann einige Hinweise geben, falls Sie jemals auf Probleme stoßen, bei denen Ihre Implementierung zu langsam ist.

MichaelHouse
quelle
Großartig und informativ wie immer, @ Byte56. :)
jcora
1
Vielen Dank, Bane. Vielleicht nicht immer, es kommt einfach vor, dass Leute Fragen stellen, von denen ich glaube, dass ich etwas weiß. Danke, dass du mir die Gelegenheit gegeben hast, darüber nachzudenken und etwas aufzuschreiben :)
MichaelHouse
4

Nur als Nebeneffekt ist JavaScript nicht so langsam, wie Sie vielleicht denken .

Die Browser-Entwickler haben viel Zeit und Energie in die Optimierung ihrer JavaScript-Engines gesteckt . Der Benchmark, mit dem ich verlinkt habe, zeigt, dass JavaScript im Median von den Benchmark-Aufgaben nur fünfmal langsamer war als C , was für einige andere interpretierte Sprachen nicht gesagt werden kann. Und die untere Grenze ist noch beeindruckender: auf dem Niveau C .

Natürlich bedeuten Sprachbenchmarks nicht wirklich viel - Sie könnten wahrscheinlich Gegenbeispiele finden, die einen anderen Benchmark verwenden. Aber der Punkt ist, dass JavaScript ziemlich schnell ist . Nein, es ist nicht C oder C ++ und es versucht nicht, es zu sein. Aber es ist gut, nicht in der "interpretierten Sprache == langsam" zu stecken, denn für jede Aufgabe von nicht trivialer Komplexität wird die Leistung mehr für das Algorithmus-Design und weniger für die Sprachauswahl von Bedeutung sein.

Eigentlich wollte ich das alles in einen Kommentar schreiben, aber mir ging der Platz aus.

voithos
quelle
1

Ja, es kann auf Javascript aufgebaut werden. Überprüfen Sie Projekte wie ASM.js, die fast die doppelte Geschwindigkeit als C erreichen. , das ist jetzt Monocore.

user29687
quelle