Comment Dwarf Fortress assure-t-il le suivi de tant d’entités sans perdre en performances?

79

Dans la forteresse des nains, vous pouvez avoir des centaines de nains, d'animaux, de gobelins, etc., à tout moment, chacun avec ses propres routines complexes d'IA et de recherche de cheminement. Ma question est la suivante: comment cela ne produit-il pas un ralentissement notable? Est-ce que chaque nain tourne dans son propre thread?

RSH1
la source
6
Question interessante. Bien que je n'aime pas la façon dont elle est formulée, ce ne serait que spéculation de répondre à la question dans sa formulation. Quoi qu'il en soit, vous avez peut-être vu cet article parler avec Tarn Adams. Où ils couvrent brièvement la recherche de chemin.
MichaelHouse
25
Cela produit absolument un ralentissement notable lorsque vous avez une topologie en tunnel complexe et plus de 100 nains.
Russell Borogove
3
Oui, DF dans mon expérience est incroyablement lent dans le scénario que vous décrivez.
argentage
4
Détruisez un escalier principal et regardez votre framerate tomber comme un rocher pendant un moment pendant que chaque nain repousse soudainement en même temps.
Mooing Duck
2
Je vais ajouter quelque chose et convenir que DF n'est pas le meilleur exemple; En fait, DF est connu pour ses problèmes de performances.
Robert S.

Réponses:

110

Tout système ayant un fil pour chacun des nombreux personnages s'épuiserait très rapidement en ressources. Les threads peuvent vous donner accès à des cœurs de processeur supplémentaires, mais ils ne rendent rien de plus intrinsèquement plus efficace, et ils entraînent des frais généraux.

La réponse simple est simplement d’être efficace dans le traitement de chaque entité du jeu.

  • Ne traitez pas chaque entité à chaque image.
  • Divisez le traitement en tâches qui doivent souvent être faites et celles qui ne le sont pas souvent.
  • Répartissez les algorithmes de longue durée sur plusieurs images afin qu'elles ne bloquent pas le traitement sur d'autres systèmes.
  • Assurez-vous que des algorithmes et des structures de données efficaces sont utilisés.
  • Cachez les résultats de calculs coûteux s'ils sont susceptibles d'être réutilisés.
Kylotan
la source
2
+1 pour cela, pour expliquer réellement ce qui se passe, plutôt que de nous concentrer sur des graphiques comme moi. :)
Matt Kemp
4
Pour être honnête, je vous ai donné aussi +1 parce que j'avais oublié cet aspect, et c'est très vrai - retirez gfx de l'équation et c'est comme si vous rendiez les ordinateurs 2x ou 3 fois plus rapides instantanément.
Kylotan
J'ai entendu dire que DF est maintenant multithread, mais au moins jusqu'à récemment, tout était fait en un seul thread. (Peut-être encore, pas sûr)
Mooing Duck
@MooingDuck Ce n'est toujours pas le cas.
Tharwen
63

Dwarf Fortress n’est pas une source ouverte, et bien que de nombreuses conjectures et ingénierie inverse puissent expliquer son fonctionnement, je me concentrerai plutôt sur quelques techniques de base pour l’optimisation d’une 3D (et non de graphiques 3D, mais d’un monde en 3D). même type.

Comme dans tous les jeux vidéo, il y a beaucoup de fumée et de miroirs qui créent l'illusion de complexité à partir de règles et de systèmes simples. Celles-ci vont de l’utilisation de nombres aléatoires simples pour un mouvement sans but jusqu’à la pré-cuisson d’un maillage de nœuds de haut niveau pour la recherche de parcours.

Mouvement

En parlant de cheminement, cela peut souvent être un problème très difficile à résoudre pour de grands espaces comme une carte DF (jusqu’à 768x768x64 IIRC), mais le problème peut être simplifié et accéléré de la manière suivante:

  • Réseau de nœuds préchauffés: lors de la création de la carte, le monde peut être divisé en blocs, et chaque bloc peut avoir ses sorties et ses entrées mappées. Lorsqu'un morceau est mis à jour, par exemple lorsqu'un mur est construit, seul le réseau de ce morceau doit être mis à jour.
  • Recherche de chemin par étape: L'exécution d'un chemin sur l'ensemble de la carte, cellule par cellule, prendrait beaucoup de temps. Vous feriez plutôt une recherche dans un réseau de blocs plus volumineux, qui mappe toutes les connexions entre des blocs, puis n'exécutait un chemin intra-bloc que lorsque passer de morceau en morceau. Cela fait 2 choses pour vous. Il accélère la recherche de chemin en le divisant en plusieurs morceaux plus petits et permet également à l'unité de changer de direction en cours de route le long du chemin lorsqu'un morceau est mis à jour. Il repasserait par le grand réseau si l'un des nœuds nécessaires pour effectuer la mise à jour croisée.
  • Direction aléatoire: lorsqu'il ne se déplace pas vers un but, il suffit à l'unité de marcher sans but. De nombreux roguelikes déplacent simplement l'unité dans une direction aléatoire, ce qui ne semble pas naturel. Diverses techniques de direction peuvent être utilisées, les plus simples privilégiant les déplacements en ligne droite et ayant de moins en moins de chances de se déplacer dans les directions allant vers l’arrière, ce qui n’a que 1% de chances environ. Ainsi, l’unité inversait parfois parfois complètement la direction, mais rarement.

Je ne couvrirai pas les bases de la découverte. La plupart des roguelikes utilisent A *, mais il existe d'autres méthodes pour écorcher le chat. Mmmm Chat en cuir ..

Tâches personnelles

L’un des principaux facteurs qui font que les unités DF apparaissent et se sentent vivantes est leur liste d’objectifs personnels. En vérité, beaucoup de jeux roguelike ont cela à un niveau basique. Chaque unité a essentiellement une liste de désirs (et pour vos tâches, les tâches qu’elle demande à accomplir) et qu’elle choisira en fonction de sa personnalité (stats.)

Certaines tâches ont des exigences. Faire une jupe en cuir nécessite que le dorf soit dans tel ou tel magasin qui a X articles. Tous ces éléments sont donc cochés et ajoutés en tant que tâches à leur liste. Aussi simple que cela.

Comme la plupart du temps, une unité sera en transit, les vérifications de ce que font les unités peuvent être très rapides, seules quelques unités seront en train de faire un choix à un moment donné. Ainsi, dans l’ensemble, il n’ya pas de ralentissement, même pour des centaines de personnes. des milliers d'unités. Et rappelez-vous, dans DF, tout ce qui va des abeilles aux troglodytes en passant par les arbres sont des unités.


En effectuant des recherches supplémentaires, il est clair que DF fait hilarement un travail terrible en tant que médiateur. Il ne s'agit pas de diviser la carte en fragments, mais bien de diviser la carte en segments ou en zones connectées (ce qui est mieux que rien à coup sûr). Mon évaluation ci-dessus est encore moins un exemple du fonctionnement de DF que je ne le pensais. :) Ce qui ne veut pas dire que DF est tout simplement incroyable pour un million d'autres raisons.

Cela montre que ce qui est important dans un jeu, c'est le jeu. Pas de graphismes, pas de programmation géniale, pas de super écriture, pas de bonne musique, pas même l'interface; Rien d'autre n'est même 1% aussi important que le jeu lui-même.

DampeS8N
la source
1
1024X1024X32? La verticale est 128 ou 256 je crois. C'est beaucoup plus grand que 32.
Lawton le
@Lawton Je crois que je me suis trompé au sujet de la taille maximale, mais la hauteur n'est pas si incorrecte. Je le corrige. J'ai chargé le jeu et l'embarquement dans lequel je me trouve ne compte qu'environ 45 niveaux. D'autres pourraient être «simulés», mais je n'y ai pas accès pour creuser ou construire.
DampeS8N
@ DampeS8N Je viens de charger une carte moyenne non modifiée et pouvais afficher de +16 à -156, environ 180 niveaux. Les cartes de 40 niveaux sont l'exception et non la règle. Même si vous ne pouvez en creuser que 40 parce que vous êtes bloqué par un aquifère ou une lave, ce n'est pas pertinent, car la zone située en dessous est toujours peuplée de divertissement simulé.
Lawton
@Lawton, ma carte me permet uniquement de parcourir 45 niveaux. Ils sont absolument variables, mais je n’étais pas facilement en mesure de trouver des chiffres sur le nombre de cartes accessibles à chaque carte. Cela peut également dépendre de la version du jeu que nous utilisons. En fin de compte, ce n'est pas si important pour ma réponse.
DampeS8N
C'est un vieux poste mais les profondeurs de la forteresse naine dépendent des couches sédimentaires. Comme la croûte terrestre est plus épaisse à certains endroits. DF n'est pas tout à fait géologique, mais ils l'étudient comme des pros: D.
Madmenyo
50

De cette page :

Eh bien [le parcours] a l'air incroyable de mon côté, car il y a une tonne de personnages qui le font tous à la fois.

TA: Les nains eux-mêmes se déplacent principalement avec A *, avec la vieille méthode heuristique classique. La difficulté réside dans le fait qu’elle ne peut pas appeler A * si elle ne sait pas qu’elle peut y arriver à l’avance, sinon elle finira par inonder la carte et tuer le processeur.

Je ne sais pas si c'est vraiment ainsi qu'il empêche "d'inonder la carte" , mais la manière habituelle de le faire dans les jeux consiste à utiliser une modification de A * appelée Hierarchical Path-Finding A * ou HPA *. L'idée est de diviser la grille en plusieurs morceaux, plus volumineux, puis d'utiliser A * pour trouver le meilleur chemin entre chaque morceau et ses morceaux voisins. Vous pouvez vous en servir pour créer un graphique beaucoup plus petit sur lequel exécuter A * pour chaque unité.

Cheminement hiérarchique

Vous pouvez également regrouper ces morceaux dans des morceaux encore plus volumineux, d'où provient la "hiérarchie".

Cet algorithme ne trouve que des chemins quasi-optimaux, mais pour des jeux comme Dwarf-Fortress, c'est généralement correct. Il est toujours garanti de trouver un chemin s'il en existe un; et quand il n'y a pas de chemin, cela ne fait que remplir le plus petit graphique, ce qui fait gagner un temps considérable.

Il existe également une abstraction de HPA * qui concerne les unités qui peuvent survoler certains terrains mais pas d'autres (telles que les falaises, que les unités aériennes peuvent traverser mais que les unités terrestres ne peuvent pas franchir) . Cela s'appelle HAA * et un article très accessible l'explique ici .

Vous pouvez en savoir plus sur les différents algorithmes de recherche de chemins ici .

BlueRaja - Danny Pflughoeft
la source
3
J'ai trouvé cette vidéo du développeur RimWorld très enrichissante. C'est un jeu similaire, alors que seulement en 2D. Il explique les bases de l'orientation et les avantages de la séparation de la carte en régions. youtube.com/watch?v=RMBQn_sg7DA
Sire
18

Au contraire, c'est le contraire qui se passe: tout tourne sur un seul thread et atteint maintenant le point où cela devient le facteur de blocage (la dernière fois que j'ai vérifié!)

La raison pour laquelle c'est rapide, c'est qu'il n'y a pas de graphismes sophistiqués. C'est trompeur, mais la principale chose qui ralentit les choses est de dessiner des choses (imaginez plus de deux tiers d'une image dans les titres AAA). Comme la forteresse naine est assez basique, elle consacre le reste de son temps à faire des choses intéressantes.

Matt Kemp
la source
8
Un point en faveur de cela est la réécriture OpenGL d’il ya quelque temps, dont je me souviens bien, qui a entraîné une augmentation massive du taux de trame. Ainsi, même le simple graphisme de sprite que DF a efficacement impacté.
Millimoose
3
+1 Bande graphique = temps libre énorme pour l'informatique de jeu
Laurent Couvidou
2
Il convient de noter que les graphismes de DF sont aussi exigeants que tout jeu 2D indépendant moderne. Il existe de nombreuses textures, même petites et simples, et elles peuvent être réparties sur des moniteurs Full HD de l'immobilier. Il n'y a pas d'effets de particules flashy ou ce que vous avez, mais le travail brut "peindre tous ces pixels" est toujours présent et en raison du nombre d'appels de tirage nécessaires pour les minuscules dalles, il est en fait un assez gros défi de rendre performant.
DampeS8N
Cela peut sembler une réponse idiote au début, mais c’est correct, imaginez ce que vous pouvez faire avec une alimentation en GPU de 4 à 12 Go et de 4 à 12 trops si vous n’avez pas besoin de dessiner des primitives complexes, des déroulements, des textures, de transformer des vecteurs 3D en un tableau
2D
10

Je ne sais pas comment DF est codé mais le nombre d'IA ne m'impressionne pas vraiment car ce que les gens surveillent souvent, c'est que l' IA n'a pas besoin de précision . Il est parfaitement viable de faire la plupart des choses seulement toutes les quelques secondes. Il est également viable d'utiliser des calculs imprécis. L'imperfection permet d'économiser beaucoup de performances . Vous pouvez exécuter la routine de prise de décision de 100 unités toutes les 100 ms ou de 1 000 unités toutes les secondes. Le temps de traitement prend la même quantité de temps CPU, mais bon ... vous avez 10 fois plus d'unités.

Voici un exemple simple pour gérer plusieurs unités:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

L'IA deviendra de moins en moins sensible, mais le joueur ne le remarquera probablement que dans des cas extrêmes.

API-Beast
la source
Il y a beaucoup à dire pour parcourir des piles de tâches qui ne sont pas précises au niveau du cadre. Les jeux AAA fixent souvent de manière explicite chaque service dans des pourcentages de trames de sorte qu'un service ne puisse pas marcher sur les pieds des autres services. Si la méthode d'animation du renversement des arbres en fonction de la vitesse et de la direction du vent est lente, moins d'arbres seront traités plutôt que de consommer le budget d'autres équipes.
DampeS8N