Structures de données pour l'interpolation et le threading?

20

J'ai eu des problèmes de tremblement de la fréquence d'images avec mon jeu récemment, et il semble que la meilleure solution serait celle suggérée par Glenn Fiedler (Gaffer on Games) dans le classique Fix Your Timestep! article.

Maintenant - j'utilise déjà un pas de temps fixe pour ma mise à jour. Le problème est que je ne fais pas l'interpolation suggérée pour le rendu. Le résultat est que je reçois des images doublées ou sautées si mon taux de rendu ne correspond pas à mon taux de mise à jour. Ceux-ci peuvent être visuellement perceptibles.

Je voudrais donc ajouter une interpolation à mon jeu - et je suis intéressé de savoir comment les autres ont structuré leurs données et leur code pour prendre en charge cela.

Évidemment, je devrai stocker (où? / Comment?) Deux copies des informations d'état du jeu pertinentes pour mon moteur de rendu, afin qu'elles puissent interpoler entre elles.

De plus, cela semble être un bon endroit pour ajouter du filetage. J'imagine qu'un thread de mise à jour pourrait fonctionner sur une troisième copie de l'état du jeu, laissant les deux autres copies en lecture seule pour le thread de rendu. (Est-ce une bonne idée?)

Il semble que le fait d'avoir deux ou trois versions de l'état du jeu pourrait introduire des problèmes de performances et - beaucoup plus important - de fiabilité et de productivité des développeurs, par rapport à une seule version. Je suis donc particulièrement intéressé par les méthodes pour atténuer ces problèmes.

Je pense en particulier au problème de savoir comment gérer l'ajout et la suppression d'objets de l'état du jeu.

Enfin, il semble qu'un certain état ne soit pas directement nécessaire pour le rendu, ou qu'il serait trop difficile de suivre différentes versions de (par exemple: un moteur physique tiers qui stocke un seul état) - je serais donc intéressé de savoir comment les gens ont traité ce genre de données dans un tel système.

Andrew Russell
la source

Réponses:

4

N'essayez pas de reproduire tout l'état du jeu. L'interpoler serait un cauchemar. Isolez simplement les parties qui sont variables et nécessaires au rendu (appelons cela un "état visuel").

Pour chaque classe d'objets, créez une classe d'accompagnement qui pourra contenir l'état visuel de l'objet. Cet objet sera produit par la simulation et consommé par le rendu. L'interpolation se branche facilement entre les deux. Si l'état est immuable et transmis par valeur, vous n'aurez aucun problème de thread.

Le rendu n'a généralement pas besoin de connaître les relations logiques entre les objets, donc la structure utilisée pour le rendu sera un vecteur simple, ou tout au plus un simple arbre.

Exemple

Design traditionnel

class Actor
{
  Matrix4x3 position;
  float fuel;
  float armor;
  float stamina;
  float age;

  void Simulate(float deltaT)
  {
    age += deltaT;
    armor -= HitByAWeapon();
  }
}

Utilisation de l'état visuel

class IVisualState
{
  public:
  virtual void Interpolate(const IVisualState &newVS, float f) {}
};
class Actor
{
  struct VisualState: public IVisualState
  {
    Matrix4x3 position;
    float fuel;
    float armor;
    float stamina;
    float age;

    virtual auto_ptr<IVisualState> Interpolate(const IVisualState &newVS, float f)
    {
      const VisualState &newState = static_cast<const VisualState &>(newVS);
      IVisualState *ret = new VisualState;
      ret->age = lerp(this->age,newState.age);
      // ... interpolate other properties as well, using any suitable interpolation method
      // liner, spline, slerp, whatever works best for the given property
      return ret;
    };
  };

  auto_ptr<VisualState> state_;

  void Simulate(float deltaT)
  {
    state_->age += deltaT;
    state_->armor -= HitByAWeapon();
  }
}
Suma
la source
1
Votre exemple serait plus facile à lire si vous n'utilisiez pas "nouveau" (un mot réservé en C ++) comme nom de paramètre.
Steve S
3

Ma solution beaucoup moins élégante / compliquée que la plupart. J'utilise Box2D comme moteur physique, donc garder plusieurs copies de l'état du système n'est pas gérable (cloner le système physique puis essayer de les garder synchronisés, il pourrait y avoir une meilleure solution mais je n'ai pas pu trouver un).

Au lieu de cela, je garde un compteur de la génération physique . Chaque mise à jour incrémente la génération physique, lorsque le système physique double les mises à jour, le compteur de génération double également les mises à jour.

Le système de rendu garde une trace de la dernière génération rendue et du delta depuis cette génération. Lors du rendu d'objets qui souhaitent interpoler leur position, vous pouvez utiliser ces valeurs ainsi que leur position et leur vitesse pour deviner où l'objet doit être rendu.

Je n'ai pas expliqué quoi faire si le moteur physique était trop rapide. Je dirais presque que vous ne devriez pas interpoler pour un mouvement rapide. Si vous avez fait les deux, vous devez faire attention à ne pas faire sauter les sprites en devinant trop lentement puis en devinant trop vite.

Quand j'ai écrit les trucs d'interpolation, je faisais tourner les graphiques à 60 Hz et la physique à 30 Hz. Il s'avère que Box2D est beaucoup plus stable lorsqu'il fonctionne à 120 Hz. Pour cette raison, mon code d'interpolation est très peu utilisé. En doublant la fréquence d'images cible, la physique met à jour en moyenne deux fois par image. Avec une gigue qui pourrait également être 1 ou 3 fois, mais presque jamais 0 ou 4+. Le taux de physique plus élevé résout en quelque sorte le problème d'interpolation. Lorsque vous exécutez à la fois la physique et la fréquence d'images à 60 Hz, vous pouvez obtenir 0 à 2 mises à jour par image. La différence visuelle entre 0 et 2 est énorme par rapport à 1 et 3.

deft_code
la source
3
J'ai aussi trouvé ça. Une boucle physique de 120 Hz avec une mise à jour de trame proche de 60 Hz rend l'interpolation presque sans valeur. Malheureusement, cela ne fonctionne que pour l'ensemble des jeux qui peuvent se permettre une boucle physique à 120 Hz.
Je viens d'essayer de passer à une boucle de mise à jour de 120 Hz. Cela semble avoir le double avantage de rendre ma physique plus stable et de rendre mon jeu fluide à des fréquences d'images pas tout à fait à 60 Hz. L'inconvénient est qu'il brise toute ma physique de jeu soigneusement réglée - c'est donc certainement une option qui doit être choisie au début d'un projet.
Andrew Russell
Aussi: je ne comprends pas vraiment votre explication de votre système d'interpolation. Cela ressemble un peu à l'extrapolation, en fait?
Andrew Russell
Bon appel. J'ai en fait décrit un système d'extrapolation. Compte tenu de la position, de la vitesse et du temps écoulé depuis la dernière mise à jour physique, j'extrapole où serait l'objet si le moteur physique n'avait pas calé.
deft_code
2

J'ai souvent entendu cette approche des pas de temps suggérée, mais en 10 ans dans les jeux, je n'ai jamais travaillé sur un projet réel qui reposait sur un pas de temps fixe et une interpolation.

Il semble généralement plus d'efforts qu'un système à pas de temps variable (en supposant une plage sensible de fréquences d'images, dans la plage de 25 Hz à 100 Hz).

J'ai essayé l'approche d'horodatage fixe + interpolation une fois pour un très petit prototype - pas de threading, mais une mise à jour logique d'horodatage fixe et un rendu aussi rapide que possible lorsque je ne le mets pas à jour. Mon approche consistait à avoir quelques classes telles que CInterpolatedVector et CInterpolatedMatrix - qui stockaient les valeurs précédentes / actuelles, et avaient un accesseur utilisé à partir du code de rendu, pour récupérer la valeur du temps de rendu actuel (qui serait toujours entre le précédent et le heure actuelle)

Chaque objet de jeu définirait, à la fin de sa mise à jour, son état actuel dans un ensemble de ces vecteurs / matrices interpolables. Ce genre de chose pourrait être étendu pour prendre en charge le filetage, vous auriez besoin d'au moins 3 ensembles de valeurs - un qui était en cours de mise à jour et au moins 2 valeurs précédentes pour interpoler entre ...

Notez que certaines valeurs ne peuvent pas être interpolées de manière triviale (par exemple, «animation frame sprite», «effet spécial actif»). Vous pouvez peut-être ignorer complètement l'interpolation, ou cela peut entraîner des problèmes, selon les besoins de votre jeu.

À mon humble avis, il est préférable d'aller simplement pas de temps variable - sauf vous fassiez un RTS ou un autre jeu où vous avez un grand nombre d'objets et vous deviez synchroniser 2 simulations indépendantes pour les jeux en réseau (envoyer uniquement des commandes / commandes sur le réseau, plutôt que des positions d'objet). Dans cette situation, le pas de temps fixe est la seule option.

bluescrn
la source
1
Il semble qu'au moins Quake 3 utilisait cette approche, le "tick" par défaut étant de 20 ips (50 ms).
Suma
Intéressant. Je suppose que cela a ses avantages pour les jeux PC multijoueurs hautement compétitifs, pour garantir que les PC plus rapides / les cadences plus élevées n'obtiennent pas trop d'avantages (contrôles plus réactifs ou différences petites mais exploitables dans la physique / comportement de collision) ?
bluescrn
1
En 10 ans, n'avez-vous rencontré aucun jeu qui ne fonctionnait pas avec la physique et la simulation? Parce qu'au moment où vous le ferez, vous devrez à peu près interpoler ou accepter la secousse perçue dans vos animations.
Kaj
2

Évidemment, je devrai stocker (où? / Comment?) Deux copies des informations d'état du jeu pertinentes pour mon moteur de rendu, afin qu'elles puissent interpoler entre elles.

Oui, heureusement, la clé ici est "pertinente pour mon moteur de rendu". Cela pourrait n'être rien de plus que l'ajout d'une ancienne position et d'un horodatage pour cela dans le mix. Étant donné 2 positions, vous pouvez interpoler à une position entre les deux, et si vous avez un système d'animation 3D, vous pouvez généralement simplement demander la pose à ce moment précis de toute façon.

C'est vraiment très simple - imaginez que votre moteur de rendu doit être capable de rendre votre objet de jeu. Il demandait à l'objet à quoi il ressemblait, mais maintenant il doit lui demander à quoi il ressemblait à un certain moment. Vous avez juste besoin de stocker toutes les informations nécessaires pour répondre à cette question.

De plus, cela semble être un bon endroit pour ajouter du filetage. J'imagine qu'un thread de mise à jour pourrait fonctionner sur une troisième copie de l'état du jeu, laissant les deux autres copies en lecture seule pour le thread de rendu. (Est-ce une bonne idée?)

Cela ressemble à une recette pour une douleur supplémentaire à ce stade. Je n'ai pas réfléchi à toutes les implications, mais je suppose que vous pourriez gagner un peu de débit supplémentaire au prix d'une latence plus élevée. Oh, et vous pouvez tirer certains avantages de pouvoir utiliser un autre noyau, mais je ne sais pas.

Kylotan
la source
1

Notez que je ne cherche pas réellement dans l'interpolation, donc cette réponse ne l'aborde pas; Je veux juste avoir une copie de l'état du jeu pour le thread de rendu et une autre pour le thread de mise à jour. Je ne peux donc pas commenter la question de l'interpolation, bien que vous puissiez modifier la solution suivante pour interpoler.

Je me posais des questions à ce sujet alors que je concevais et pensais à un moteur multithread. J'ai donc posé une question sur Stack Overflow, à propos de façon de mettre en œuvre une sorte de modèle de conception de "journalisation" ou de "transactions" . J'ai eu de bonnes réponses et la réponse acceptée m'a vraiment fait réfléchir.

Il est difficile de créer un objet immuable, car tous ses enfants doivent également être immuables, et vous devez faire très attention à ce que tout soit vraiment immuable. Mais si vous faites bien attention, vous pouvez créer une superclasseGameState qui contient toutes les données (et les sous-données et ainsi de suite) de votre jeu; la partie "Modèle" du style d'organisation Model-View-Controller.

Ensuite, comme le dit Jeffrey , les instances de votre objet GameState sont rapides, économes en mémoire et thread-safe. Le gros inconvénient est que pour changer quoi que ce soit sur le modèle, vous devez en quelque sorte recréer le modèle, vous devez donc faire très attention à ce que votre code ne se transforme pas en un énorme gâchis. La définition d'une nouvelle valeur dans l'objet GameState sur une nouvelle valeur est plus complexe que la simplevar = val; , en termes de lignes de code.

Je suis cependant terriblement intrigué par cela. Vous n'avez pas besoin de copier l'intégralité de votre structure de données à chaque trame; vous venez de copier un pointeur sur la structure immuable. En soi, c'est très impressionnant, n'est-ce pas?

Ricket
la source
C'est une structure intéressante en effet. Cependant, je ne suis pas sûr que cela fonctionnerait bien pour un jeu - car le cas général est un arbre d'objets assez plat qui change chacun exactement une fois par image. Aussi parce que l'allocation dynamique de mémoire est un gros no-no.
Andrew Russell
L'allocation dynamique dans un cas comme celui-ci est très facile à faire efficacement. Vous pouvez utiliser un tampon circulaire, grandir d'un côté, relâcher du second.
Suma
... ce ne serait pas une allocation dynamique, juste une utilisation dynamique de la mémoire préallouée;)
Kaj
1

J'ai commencé par avoir trois copies de l'état du jeu de chaque nœud dans mon graphique de scène. L'une est en cours d'écriture par le thread du graphe de scène, l'autre en cours de lecture par le moteur de rendu, et une troisième est disponible en lecture / écriture dès que l'un de ces besoins doit être échangé. Cela a bien fonctionné, mais c'était trop compliqué.

J'ai alors réalisé que je n'avais qu'à garder trois états de ce qui allait être rendu. Mon thread de mise à jour remplit maintenant l'un des trois tampons beaucoup plus petits de "RenderCommands", et le Renderer lit à partir du dernier tampon qui n'est pas actuellement écrit, ce qui empêche les threads de s'attendre les uns les autres.

Dans ma configuration, chaque RenderCommand a la géométrie / les matériaux 3D, une matrice de transformation et une liste de lumières qui l'affectent (faisant toujours un rendu direct).

Mon thread de rendu n'a plus à faire de calculs d'abattage ou de distance lumineuse, ce qui a considérablement accéléré les choses sur les grandes scènes.

Dwayne
la source