Discussion :

[Obligen]

Bonjour,

J'ai besoin d'un avis de gens plus compétents que moi dans ce domaine.
Je teste actuellement la programmation de physique simple, comme les collisions avec rétroaction, les lancers et tout ça.

Seulement, je me posais une question sur la traditionnelle "gaming loop", qui voudrait que l'on respecte le schéma basique suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
- A l'infini, faire
--- calculer les nouvelles positions des objets
--- dessiner les objets
--- attendre un peu si on est en avance

Certes, cela marche bien, mais du coup, soit on calcule les positions des objets en fonction du temps écoulé, et c'est relativement lourd, soit on calcule les positions en fonctions de nombre d'images affichées, et tout est très simple à coder, mais si ça rame, l'animation est ralentie au sens propre, et donc ce n'est pas bon.

Je sais que traditionnellement (sauf en Flash généralement), on calcule les positions des objets en fonction du temps écoulé, mais est-ce conventionnel d'utiliser plutôt 2 threads, de la façon suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
--------------------------------
Thread de calcul
--------------------------------
- A l'infini, faire
--- Calculer les nouvelles positions
--- Attendre un peu
 
--------------------------------
Thread de rendu
--------------------------------
- A l'infini, faire
--- Dessiner les objets
--- Attendre un peu

Forcément, on est pas forcé d'attendre le même temps, et on se retrouve donc avec un taux d'images par seconde (FPS), et un taux de calculs par seconde (CPS ?).

J'ai commencé à faire comme ça (n'y connaissant pas grand chose) en java, cela marche bien mais je ne pense vraiment pas que ce soit conventionnel, d'autant qu'en écrivant ces lignes je me dis que si le thread de calcul se met à ramer, l'animation sera ralentie quand même, ce qui n'est pas le cas dans un simple thread avec calcul des positions indexé sur le temps écoulé depuis le dernier calcul...

Bon, finalement j'ai peut être compris par moi même en écrivant ce message qu'elle était la seule solution envisageable, même si plus lourde à mettre en œuvre (plus facile de faire un "balle.x ++" qu'un "balle.x = tempsEcoule*vitesse")... autant laisser ça au cas où ça intéresse quelqu'un.


EDIT : A oui, une chose à laquelle j'ai pensé aussi. En utilisant 2 threads, on prend le risque de calculer une nouvelle position d'objet au même moment où on l'affiche, donc accès concurents. Ca n'a pas de conséquences dans les jeux simples avec peu d'objets à l'ecran, mais je pense que la scène serait mal rendue avec beaucoup d'objets. Du coup, on peut envisager d'insérer quelques accès atomiques aux données ou mettre en place quelques sémaphores, mais du coup, on en revient presque à la boucle simple classique, puisque soit on calcule, soit on affiche...

EDIT2 : Je pensais que dans le framework XNA de Microsoft (DirectX managé et intégré), on avait réellement deux threads différents, car il y a une méthode "Draw" et une méthode "Update". Mais ayant essayé d'afficher les FPS et les CPS à l'ecran, ils s'averent être les mêmes, il n'y a donc qu'un seul thread...

[shenron666]

est-ce conventionnel d'utiliser plutôt 2 threads, de la façon suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
--------------------------------
Thread de calcul
--------------------------------
- A l'infini, faire
--- Calculer les nouvelles positions
--- Attendre un peu
 
--------------------------------
Thread de rendu
--------------------------------
- A l'infini, faire
--- Dessiner les objets
--- Attendre un peu

à vue de nez je dirai que :
- ton thread de calcul va attendre que ton thread de rendu ai terminé d'afficher pour commencer
- ton thread de rendu va attendre ton thread de calcul jusqu'à ce qu'il ait terminé son boulot pour commencer à son tour
au final : gain 0%

avec quelques petits ajustements tu peux réussir à faire en sorte que le thread de rendu commence à traiter les objets que le thread de calcul a terminé de traiter

si le thread de calcul se met à ramer, l'animation sera ralentie quand même, ce qui n'est pas le cas dans un simple thread avec calcul des positions indexé sur le temps écoulé depuis le dernier calcul...

c'est pourquoi il faut toujours caler son animation sur le temps écoulé

Bon, finalement j'ai peut être compris par moi même en écrivant ce message qu'elle était la seule solution envisageable, même si plus lourde à mettre en œuvre

plus lourd c'est un peu exagéré

EDIT : A oui, une chose à laquelle j'ai pensé aussi. En utilisant 2 threads, on prend le risque de calculer une nouvelle position d'objet au même moment où on l'affiche, donc accès concurents. Ca n'a pas de conséquences dans les jeux simples avec peu d'objets à l'ecran, mais je pense que la scène serait mal rendue avec beaucoup d'objets. Du coup, on peut envisager d'insérer quelques accès atomiques aux données ou mettre en place quelques sémaphores, mais du coup, on en revient presque à la boucle simple classique, puisque soit on calcule, soit on affiche...

approfondis le sujet, renseigne toi sur :
- les threads et le multithreading
- les mutex et semaphores
- les "lock free data structures"
- la programmation événementielle
tu verras qu'il y a des tas de solutions pour multithreader certaines parties
sachant que, à l'heure actuelle, la seule chose qu'on ne peux pas multithreader c'est le rendu, ni en D3D ni en OGL (quoiqu'en OGL on peut mais ça ne sert à rien)

[Obligen]

Merci de ces réponses, je vais continuer à creuser la question, c'est assez intéressant

[IrmatDen]

Salut,

Si ça peut te donner un début de piste, j'ai lu cet article sur Gamasutra qui présente rapidement quelques approches. Ca te donnera un premier aperçu, et des noms et mot-clé pour creuser plus avant tes recherches

[Obligen]

Merci pour le lien, c'est très instructif

[deadalnix]

perso, j'ai une représentation du monde statique. Celle-ci peut être utilisée pour l'affichage.

En parallèle la physique est calculée. Un fois une étape complète au niveau de la physique, c'est cette partie qui choppe un lock sur le monde statique, et qui commit le plus rapidement possible les nouvelles infos.

De plus, cette façon de faire se marie bien avec les algo de lag compensation (non encore implémenté pour ma part, mais au programme).

[screetch]

l'autre possibilité est de faire une copie du monde
si tu as séparé tes objets et leur position (base de donnée géographique), tu peux copier la géographie, effectuer le rendu de la copie tout en calculant les nouvelles positions dans d'autres thrads

n'oublie pas que le parallelisme de threads n'est pas la seul possibilité, le parallelism de tache est aussi souvent utilisé

[shenron666]

l'autre possibilité est de faire une copie du monde
si tu as séparé tes objets et leur position

si tu as beaucoup d'objets à gérer, tu perds énormément de temps juste pour copier leur position mais l'idée de base est bonne
fonctionner avec 2 bases, une en lecture, une en écriture
- la base en lecture sert pour le thread d'affichage afin qu'il sache où placer les objets et en même temps pour le ou les threads de calcul afin qu'ils sachent où sont actuellement placés les objets
- la base en écriture est utilisée par les threads de calcul pour stocker les nouvelles positions des objets pour la prochaine étape

une fois les calculs effectués et l'affichage terminé on swap les bases (un simple échange de pointeurs ou de références, pas un swap des données inutilement long)

on répartissant intelligemment les taches entre les threads de calcul, on a très peu besoin de lock sur la base d'écriture
quand à la base de lecture, vu qu'elle n'est pas modifiée, pas besoin de lock

un principe similaire au "double buffering" utilisé pour l'affichage

[deadalnix]

C'est plus ou moins ce que je fais, sauf qu'il y a un index et qu'on sauvegarde plusieur position dans le passé Dans le but de pouvoir :
1/ Gerer le lag compensation dans le futur
2/ Permettre des calcul physique totalement asynchrones du rendu.

Perso, il y en a 8. Le pas de physique étant de 10ms, ça fait 80ms. Avec deux pas, on peut avoir les vitesses.

[screetch]

tu ne peux pas t'en tirer avec juste un swap a priori, il te faut repartir des positions mises a jour

[deadalnix]

Oui, mais le soucis est de lire/écrire dans les mêmes données.

Rien ne t'empêche de lire les données pour les afficher au niveau de la partie graphique et de les lires aussi dans la parti physique pour les mettre a jour.

Sauf que les mises a jour seront inscrite dans un autre buffer.

[screetch]

hmmmoui donc tu les copie....

[deadalnix]

Non.

Tu as deux buffer que nous apellerons A et B.

Dans A, un représentation du monde. Celle-ci sert a l'affichage.
Le moteur physique lis les données de A, fait ses petits calculs et met a jour les données dans B.

Un fois les calculs terminés, tu inverse els références entre A et B.

B sert donc à l'affichage. Le moteur physique lis aussi dans B et met a joru les données dans A. Et on recommence.

On peut faire le tout avec 8 buffers, pour gerer le lag compensation. Ici, les buffers peuvent être plus legers car il n'y a plus besoin de mémoriser les vitesses (contrairement a un modèle a deux buffers).

[shenron666]

tu ne peux pas t'en tirer avec juste un swap a priori, il te faut repartir des positions mises a jour

relis bien ma méthode, c'est ce que je fait

hmmmoui donc tu les copie....

pas du tout

deadalnix me semble avoir bien compris le principe et ça semble lui donner des idées intéressantes

[screetch]

ah oui d'accord je vois. je vais voir, j'en suis justement pas loin de coder cette partie.

[deadalnix]

deadalnix me semble avoir bien compris le principe et ça semble lui donner des idées intéressantes

En fait, mon code marche pratiquement comme ça.

J'ai un position « lockée » définie par un index. C'est dans cette position que mon moteur physique écrit.

Une autre position est définie comme position pour le rendu. C'est un autre index. Elle sert pour le rendu.

Un fois un rendu affichée, l'index de référence du rendu est avancé a la dernière position totalement calculée par le moteur physique.

Les index « bouclent », c'est a dire, que quand on arrive au bout du tableau (ici de 8 éléments) on revient au début.

[Rafy]

Et donc si j'ai bien compris tu peux donc "remonter" dans le temps pour 80ms ?
(Je pose la question car en fait je vais bientôt avoir besoin de bosser sur le lag compensation)
Tu stockes quoi ?
Car ce que je me dis c'est qu'il fut non seulement stocker l'état des objets (c'est à dire position etc.) mais aussi les contraintes appliquées sur les objets.
Je vais prendre un exemple pour faire simple :
je conduit un vaisseau spacial. Je vias tout droit réacteur à fond. Je suis en phase d'accélération, j'ai donc une force à l'arrière de mon vaisseau. je stocke mes états etc... ça stocke ça stocke... Un autre joueur me tire dessus un tir super puissant (instantané pour simplifier).. Moi je ne suis pas encore au courant de tout ça.... le serveur pas encore non plus...ça stocke ça stocke... Le serveur reçoit l'ordre de tire. Remonte dans le temps pour trouver l'instant de et le lieu de collision... Le tir devait me toucher.... la physique est alors recalculée en prenant en compte cette collision. (le tir par exemple me pousse)...
Pour cela le serveur doit donc ajouter aux forces qu'ils y avait avant (dans l'exemple l'effort de poussé) les efforts rajoutés...

Et pour en revenir au sujet, il faut faire attention que le temps qu'on passe à switcher (au niveau du proc) entre les thread n'est pas plus long que les calculs qu'on fait dans les thread. Si c'est le cas on perd plus de temps qu'on en gagne, et autant rester en single thread....

[deadalnix]

deux choses :

1/ Je ne penses jamais thread mais taches. ca me permet d'avoir un même code sur un nombre de thread quelquonque que je peux choisir.

2/ Oui, il va falloir remonter dans le temps. Dans un premier temps, il va falloir faire le test d'intersection avec le tir sur les objets qui vont bien. Si un objet est impacté, il est ajouté au objets a "lag compenser". Les autres objets ont déjà des pos calculées en fonctions des contraintes. Si le vaisseau impacté en vient a interagir avec d'autres objets, ils seront eu aussi ajouté aux objets a revoir.

Au final, le processus est assez legers car le calcul ne concerne que peu d'objets.

il peut être aussi judicieu de ne pas appliquer le tout sur les objets non critiques pour le gameplay.

[shenron666]

le lag compensation n'a rien à voir avec le multithreading de la game loop
si tu veux en discuter tu peux créer un sujet là dessus
je pense que ça pourrait intéresser du monde

Si c'est le cas on perd plus de temps qu'on en gagne, et autant rester en single thread....

passer en multithread permet aussi de pouvoir exploiter les coeurs que nos cher processeurs vont avoir de plus en plus nombreux

si tu suis ta logique aujourd'hui, tu prends déjà du retard
l'avenir est au multithreading autoadaptif, ton programme voit combien de threads la machine est capable de supporter, il s'adapte afin d'en tirer les meilleures performances

je préfère avoir un moteur multithread aussi efficace sur 2 coeurs qu'un moteur monothread
car le moteur multithread se comportera mieux sur plus de 2 coeurs (plus de fluidité ou plus de qualité entre autres choix)

[Rafy]

Ce que je voulais dire c'est que si on a plein de tâches qui ne demandent presque pas de temps de calcul, alors le temps qu'on utilise pour passer les tâches au thread peut-être beaucoup plus long que le temps effectif pour traiter les taches....
Un exemple con, mais qui permet de comprendre :
j'ai 100000 additions à faire. En ST on va les faire les unes apres les autres et on utiliser 100000 * temps d'une addition.
En MT on va utiliser environ 100000 * temps de passage des taches aux thread + 100000 * temps d'une addition / nombre de thread...
Une addition c'est gratuit, mais le temps de passage d'une tache est loin de l'être....
C'est bien de penser MT, mais il faut le faire intervenir au bon endroit. Il faut que les tâches à effectuées reste prépondérantes par rapport au temps de passage des taches....
Je pense que ça peut effectivement être une bonne idée de parler du lag compensation dans un post.