Comment fonctionnent les algorithmes de génération d'historique?

19

J'ai entendu parler du jeu Dwarf Fortress, mais ce n'est que maintenant qu'une des personnes que je suis sur Youtube a fait un commentaire à ce sujet ... J'ai été plus que surpris quand j'ai remarqué comment Dwarf Fortress génère réellement une histoire pour le monde!

Maintenant, comment fonctionnent ces algorithmes? Que prennent-ils habituellement en entrée, à part la durée de la simulation? Dans quelle mesure peuvent-ils être spécifiques?

Et plus important; peuvent-ils être créés en Javascript, ou Javascript est-il trop lent? (Je suppose que cela dépend de la profondeur de la simulation, mais prenez l'exemple de Dwarf Fortress.)

jcora
la source
3
"Peut-on les faire en Javascript?" La réponse est évidemment oui, mais cela dépend de la rapidité avec laquelle vous voulez les résultats et de la complexité que vous voulez qu'ils soient. La forteresse naine prend aussi du temps - et elle ralentit à mesure que le monde vieillit! Donc, tant que vous voulez une histoire superficielle, oui, vous pouvez le faire en Javascript, donc cela dépend de la complexité que vous voulez que l'histoire soit.
doppelgreener
2
Il signifie "au niveau de la forteresse naine", comme à l'échelle.
MichaelHouse
2
@Bane Oui, je veux dire que vous pouvez modifier la quantité d'histoire qu'il y aura dans DF. Lorsque vous démarrez un monde, il génère d'abord un terrain au hasard, puis commence à vieillir le monde sous vos yeux et à générer de l'histoire au fur et à mesure. Vous le regardez alors que les empires se dilatent et se rétrécissent, que le terrain change, que les forêts grandissent et reculent, que les zones deviennent hantées (ou plus hantées), etc. Elle progresse d'année en année (voire plusieurs années à la fois) sous vos yeux. Cela continue jusqu'à ce que vous lui disiez d'arrêter. Plus vous vous éloignez, plus la génération est lente (en raison de l'utilisation du processeur et non des mécanismes de jeu).
doppelgreener
1
Pour être très clair: plus le monde est âgé, plus chaque année est lente à calculer. Dans un monde jeune, il se précipitera au cours des premières années, dans un monde vieux de plusieurs centaines d'années, l'année suivante pourrait prendre une seconde ou quelques secondes à générer.
doppelgreener
1
Oh, ça, je sais. Par «profondeur», je ne voulais pas dire le nombre d'années, je voulais dire le nombre d'événements qui se produisent et la précision de la simulation. Vous pouvez simplement garder un certain nombre de personnes dans un empire, ou vous pouvez réellement avoir une classe appelée Person, qui fait des tâches, va à l'armée, etc. Shallow laisserait la taille de l'empire décider des résultats des batailles, mais profond serait d'avoir chaque soldat se battre pour le sien.
jcora

Réponses:

27

Tout d'abord, il y a quelques conseils pour la génération de l'histoire de la forteresse naine. Quelqu'un a demandé sur les forums Bay12 il y a quelque temps, et une transcription a été partagée et vous pouvez trouver où commence la discussion en recherchant: "notre sujet aujourd'hui est la génération du monde et la génération de l'histoire".


Je ne sais pas exactement comment Dwarf Fortress le fait, mais je vais vous expliquer comment je prévois d'implémenter un premier brouillon très basique dans mon jeu. Je vais utiliser un simple automate cellulaire . Si vous regardez à travers ces prototypes de spores , comme la culture cellulaire et le biome.

entrez la description de l'image ici

Ce sont des exemples d'automatisation cellulaire et de ce qu'ils peuvent produire. Essentiellement, je vais créer des règles pour différentes races. Voici quelques exemples de règles:

  • Leur hostilité envers les autres races
  • Leurs préférences climatiques
  • Leurs besoins en ressources
  • Leurs taux de natalité et leur durée de vie
  • Leurs désirs (recherche technologique, commerce, existence pacifique, domination mondiale)
  • Leurs capacités (construction de structures, collecte de ressources, guerre, etc.)
  • Etc...

Donc, l'apport le plus critique pour que tout cela fonctionne est un monde dans lequel plonger ces races. Le terrain déterminera leurs préférences et leur expansion. Donc, une fois que vous avez généré un monde, choisissez des endroits aléatoires dans le monde où ces races vivraient convenablement et laissez-les se déchaîner. Maintenant, les choses intéressantes commencent à se produire. Maintenant que vous avez des terres et des races avec des désirs et des capacités, vous pouvez commencer à construire une histoire. Ces races rassemblent des ressources, puis des structures sont construites:

  • Villes dans des zones à haute ressource et à haute habitabilité.
  • Des routes relient les grandes villes.
  • Ponts sur les rivières.
  • Tunnels à travers les montagnes.
  • Forteresses près des lignes de front d'expansion en réponse aux batailles.

Toute structure peut être pillée / conquise par d'autres races. Plus une structure (comme une ville ou une forteresse) existe depuis longtemps, plus elle est défendable, plus elle est difficile à prendre en main. Et plus il est souhaitable pour les courses qui veulent contrôler. Les batailles se déroulent là où les races se rencontrent (au moins une est hostile). Les batailles sont nommées d'après des points de repère ou des structures à proximité, ou si la bataille est importante ou si les points de repère ne sont pas nommés, les points de repère sont nommés d'après la bataille.

Les routes, les ponts et les tunnels sont élargis grâce au commerce et au transport des ressources. Chacun a un débit maximal qui peut augmenter avec les dépenses en ressources. Construire une forteresse de pierre au milieu des prairies? Ces routes vont devenir très utilisées pour transporter la pierre requise. Ils deviendront plus grands et obtiendront un nom.

Des catastrophes naturelles se produisent, affectant les populations et le cours de l'histoire. Les tremblements de terre peuvent réduire une ville en ruines ou effondrer un tunnel. Une inondation pourrait laver une route ou un pont.


Ce n'est pas aussi approfondi que Dwarf Fortress, mais c'est un début. Maintenant, comme vous pouvez l'imaginer (et comme Johnathan Hobbs l'a mentionné), plus ces races se développent, plus il y a de cellules simulées. Non seulement plus de cellules sont simulées, mais les simulations sont plus complexes car il y a maintenant des structures à construire / maintenir, des batailles à mener, du commerce au ... commerce, etc. Cela devient lourd pour n'importe quelle langue. Javascript pourrait ralentir plus tôt. Cependant, vous pouvez toujours sacrifier la complexité pour une vitesse améliorée.

Tout est une simulation (bien que complexe), vous enregistrez simplement les événements importants en cours de route et l'appelez l'histoire.

Je viens également de trouver un message sur le forum Bay12 pour les personnes qui réfléchissent à la façon de rendre la génération mondiale de Dwarf Fortress plus rapide. Je ne l'ai pas lu, mais il peut fournir des conseils si vous rencontrez des problèmes avec votre implémentation trop lente.

MichaelHouse
la source
Super et instructif comme toujours, @ Byte56. :)
jcora
1
Merci Bane. Peut-être pas toujours, il se trouve que les gens posent des questions dont je pense savoir quelque chose. Merci de m'avoir donné l'opportunité d'y réfléchir davantage et d'écrire quelque chose :)
MichaelHouse
4

Juste comme point secondaire, JavaScript n'est pas aussi lent que vous ne le pensez .

Les développeurs de navigateurs ont consacré beaucoup de temps et d'énergie à optimiser leurs moteurs JavaScript . Le benchmark auquel j'ai lié montre que, sur les tâches comparées, dans la médiane, JavaScript n'était que 5 fois plus lent que C , ce qui ne peut pas être dit pour d'autres langages interprétés. Et la borne inférieure est encore plus impressionnant: à égalité avec C .

Bien sûr, les benchmarks linguistiques ne signifient pas vraiment grand-chose - vous pourriez probablement trouver des contre-exemples en utilisant un benchmark différent. Mais le fait est que JavaScript est assez rapide . Non, ce n'est pas du C ou du C ++, et ça n'essaye pas de l'être. Mais il est bon de ne pas rester coincé dans l'état d'esprit "langage interprété == lent", car pour toute tâche de complexité non triviale, les performances auront plus d'importance sur la conception de l'algorithme et moins sur le choix de la langue.

J'allais en fait écrire tout cela dans un commentaire, mais j'ai manqué d'espace.

voithos
la source
1

Oui, il peut être construit sur javascript, vérifiez les projets comme ASM.js, qui obtiennent une vitesse presque deux fois plus lente que C. Si vous prenez soin de plusieurs cœurs (en utilisant des webworkers), cela peut être encore plus rapide que le DF (en termes de ressources) , qui est monocore en ce moment.

user29687
la source