Système de Particules

Version imprimable

Voir 40 message(s) de cette discussion en une page

Citation:

Envoyé par Kannagi

Je pense que si tu arrive a mettre un tableau a la place : mGrid[caseY-1][caseX+j].size() , ça optimiserait pas mal :p

J'ai le même résultat avec un tableau simple :D

Mon super code :P

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#ifndef PARTICLESYSTEM_H
#define PARTICLESYSTEM_H
 
#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <list>
#include <memory>
#include <math.h>
#include "Particle.h"
#include "ParticleContact.h"
#include "Window.h"
#include "Map.h"
#include "Camera.h"
#include "QuadTree.h"
 
class ParticleSystem
{
    public:
        ParticleSystem();
        virtual ~ParticleSystem();
 
        void displayParticle(Window *window, Camera *camera);
        void createParticle(int type, float positionX, float positionY, float velocityX, float velocityY);
        void createParticles(int type, float positionX, float positionY);
 
        void computeParticles(Map *pMap);
        void createGrid();
        void findContacts();
        void computeForces();
        void updatePosition(Map *pMap);
 
 
    protected:
 
    private:
 
        const float PI = 3.14159f;
        const float TIME_STEP = 0.1f;
        const float GRAVITY = 0.5;
        const float n = 5.0f;
        const float w0 = -0.0f;
        const float a = -45.0f;
        const float VISCOSITY = 0.1f;
        const static int MAX_PARTICLES = 8192;
 
        const static int WIDTH_PARTICLE = 10;
        const static int WIDTH_PARTICLE_2 = 100;
        const static int RADIUS_PARTICLE = 5;
 
        Particle mParticles[MAX_PARTICLES];
 
        std::vector<ParticleContact> mParticleContacts;
        std::vector<int> mGrid[96][199];
 
        int mCountParticles;
};
 
#endif // PARTICLESYSTEM_H

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include "ParticleSystem.h"
 
ParticleSystem::ParticleSystem()
{
    mCountParticles = 0;
}
 
ParticleSystem::~ParticleSystem()
{
 
}
 
void ParticleSystem::displayParticle(Window *window, Camera *camera)
{
    for(int i=0; i<mCountParticles;i++){
        int posXwindow = window->getWidth()/2-(camera->getPosX() - mParticles[i].mPositionX);
        int posYwindow = window->getHeight()/2 + (camera->getPosY() - mParticles[i].mPositionY);
 
 
        window->renderImage("circle", posXwindow-RADIUS_PARTICLE, posYwindow-RADIUS_PARTICLE, WIDTH_PARTICLE, WIDTH_PARTICLE);
    }
 
    window->displayNumber(400, 400, mCountParticles, 0,400,0);
}
 
void ParticleSystem::createParticle(int type, float positionX, float positionY, float velocityX, float velocityY)
{
    mParticles[mCountParticles] = Particle(type, positionX, positionY, velocityX, velocityY);
    mCountParticles ++;
}
 
void ParticleSystem::createParticles(int type, float positionX, float positionY)
{
    float space = 11;
 
    for(int i=0; i< 30; i++)
        for(int j=0; j<30; j++)
            createParticle(type, positionX+space*i, positionY-j*space, 0, 0);
}
 
void ParticleSystem::computeParticles(Map *pMap)
{
    createGrid();
    findContacts();
    computeForces();
    updatePosition(pMap);
}
 
void ParticleSystem::createGrid()
{
    for(int caseX=0; caseX<199; caseX++)
        for(int caseY=0; caseY<96; caseY++)
            mGrid[caseY][caseX].clear();
 
    for(int i = 0; i<mCountParticles; i++){
        int x = mParticles[i].mPositionX/10;
        int y = mParticles[i].mPositionY/10;
        mGrid[y][x].push_back(i);
    }
}
 
void ParticleSystem::findContacts()
{
    for(int i=0; i<mCountParticles; i++)
    {
        int caseX = mParticles[i].mPositionX/10;
        int caseY = mParticles[i].mPositionY/10;
 
 
        // same case
        for(int k=0;k<mGrid[caseY][caseX].size();k++){
            int voisin = mGrid[caseY][caseX][k];
            float dx = mParticles[voisin].mPositionX - mParticles[i].mPositionX;
            float dy = mParticles[voisin].mPositionY - mParticles[i].mPositionY;
            if(dx > 0 || (dx==0 && dy>0)){
                float distance2 = dx * dx + dy * dy;
                if(distance2 < WIDTH_PARTICLE_2 && distance2 != 0){
                    float distance = sqrt(distance2);
                    float weight = (1.0f-distance/WIDTH_PARTICLE);
                    mParticleContacts.emplace_back(i, voisin, distance, weight);
                    mParticles[i].mDensity += weight;
                    mParticles[voisin].mDensity += weight;
                }
            }
        }
 
        // right case
        if(caseX+1<199){
            for(int k=0;k<mGrid[caseY][caseX+1].size();k++){
                int voisin = mGrid[caseY][caseX+1][k];
                float dx = mParticles[voisin].mPositionX - mParticles[i].mPositionX;
                float dy = mParticles[voisin].mPositionY - mParticles[i].mPositionY;
                float distance2 = dx * dx + dy * dy;
                if(distance2 < WIDTH_PARTICLE_2 && distance2 != 0){
                    float distance = sqrt(distance2);
                    float weight = (1.0f-distance/WIDTH_PARTICLE);
                    mParticleContacts.emplace_back(i, voisin, distance, weight);
                    mParticles[i].mDensity += weight;
                    mParticles[voisin].mDensity += weight;
                }
            }
        }
 
        //bottom cases
        for(int j=-1;j<2;j++){
            if(caseY-1>0 && caseX+j>0 && caseX + j<199){
                for(int k=0;k<mGrid[caseY-1][caseX+j].size();k++){
                    int voisin = mGrid[caseY-1][caseX+j][k];
                    float dx = mParticles[voisin].mPositionX - mParticles[i].mPositionX;
                    float dy = mParticles[voisin].mPositionY - mParticles[i].mPositionY;
                    float distance2 = dx * dx + dy * dy;
                    if(distance2 < WIDTH_PARTICLE_2 && distance2 != 0){
                        float distance = sqrt(distance2);
                        float weight = (1.0f-distance/WIDTH_PARTICLE);
                        mParticleContacts.emplace_back(i, voisin, distance, weight);
                        mParticles[i].mDensity += weight;
                        mParticles[voisin].mDensity += weight;
                    }
                }
            }
        }
 
        //apply gravity
        mParticles[i].mVelocityY -= GRAVITY;
        //compute pressure
        mParticles[i].mPressure = std::max(0.0f, n * (mParticles[i].mDensity - w0));
 
    }
 
}
 
void ParticleSystem::computeForces()
{
    while(!mParticleContacts.empty()){
 
        ParticleContact contact = mParticleContacts.back();
        mParticleContacts.pop_back();
 
        int p1 = contact.mParticule1;
        int p2 = contact.mParticule2;
 
        //compute force
 
 
        float nX = (mParticles[p2].mPositionX - mParticles[p1].mPositionX)/contact.mDistance;
        float nY = (mParticles[p2].mPositionY - mParticles[p1].mPositionY)/contact.mDistance;
 
        float forceX = TIME_STEP * a * (mParticles[p1].mPressure + mParticles[p2].mPressure) * contact.mWeight * nX;
        float forceY = TIME_STEP * a * (mParticles[p1].mPressure + mParticles[p2].mPressure) * contact.mWeight * nY;
 
        mParticles[p1].mVelocityX += forceX;
        mParticles[p1].mVelocityY += forceY;
 
        mParticles[p2].mVelocityX -= forceX;
        mParticles[p2].mVelocityY -= forceY;
 
        mParticles[p1].mVelocityX += TIME_STEP * VISCOSITY * (mParticles[p2].mVelocityX - mParticles[p1].mVelocityX);
        mParticles[p1].mVelocityY += TIME_STEP * VISCOSITY * (mParticles[p2].mVelocityY - mParticles[p1].mVelocityY);
 
        mParticles[p2].mVelocityX += TIME_STEP * VISCOSITY * (mParticles[p1].mVelocityX - mParticles[p2].mVelocityX);
        mParticles[p2].mVelocityY += TIME_STEP * VISCOSITY * (mParticles[p1].mVelocityY - mParticles[p2].mVelocityY);
    }
}
 
void ParticleSystem::updatePosition(Map *pMap)
{
    // update position
    for (int i = 0; i < mCountParticles; ++i) {
 
        if(mParticles[i].mVelocityX>50)
            mParticles[i].mVelocityX = 50;
 
        if(mParticles[i].mVelocityX<-50)
            mParticles[i].mVelocityX = -50;
 
        if(mParticles[i].mVelocityY>50)
            mParticles[i].mVelocityY = 50;
 
        if(mParticles[i].mVelocityY<-50)
            mParticles[i].mVelocityY = -50;
 
        mParticles[i].updatePosition(pMap ,TIME_STEP);
 
        //reset
        mParticles[i].mDensity=0.0f;
        mParticles[i].mPressure=0.0f;
    }
}

13/09/2017, 20h23
Kannagi

Tu m'a mal compris , je disais de remplacer mGrid[caseY][caseX].size() , par Grid[caseY][caseX] par exemple.

Alors, concernant le code:

Pourquoi mParticles est il un tableau de taille fixe "C style" :question: Tôt ou tard, quand tes problèmes de performances seront résolus, tu voudras augmenter le nombre de particules au point de faire exploser ta pile!

Utilises au minimum les fonctionnalités issues de la bibliothèque standard : std::array si tu as un nombre "relativement restreint" d'élément connu à la compilation std::vector + sa fonction reserve ou resize si le nombre devient "trop important" ou si le nombre d'éléments n'est pas connu à la compilation.

As tu une vague idée de ce que représente ton code std::vector<int> mGrid[96][199];:question: c'est une matrice qui contient 19 104 tableaux d'entiers! le tout placé dans la pile (à moins que tu n'aies recours à l'allocation dynamique pour ton ParticleSystem). Heu, je veux bien, mais... t'es sur d'avoir besoin de cela :question:

Et puis:

mGrid en lui-même va, effectivement, placer les 19000 std::vector l'un à la suite de l'autre en mémoire. Mais std::vector est une classe qui a recours à l'allocation dynamique de la mémoire pour pouvoir représenter les éléments qu'ils contient d'une manière contigue en mémoire. C'est à dire que les X éléments contenus par le std::vector qui se trouve en mGrid[0][0] n'ont pour ainsi dire aucune chance d'être contigus avec ceux qui se trouvent dans mGrid[0][1] (ou dans mGrid[1][0])

Cela peut ne pas être catastrophique, ou non...

Sans compter le fait que l'idéal est toujours de faire en sorte que toutes les notions qui apparaissent dans ton analyse des besoins / dans ton analyse fonctionnelle puissent avoir leur représentation dans le code. Tu as besoin de la notion de matrice :question: Crée un type de donnée (une classe, en l'occurrence) qui représentera cette notion.

Pour ce faire, il faut comprendre que, lorsque tu crées une matrice de LINES lignes et de ROWS colonnes, ce que tu veux en réalité, c'est d'être en mesure de représenter LINES * ROWS éléments (raison pour laquelle je parlais des 19000 std::vector). Tu peux donc tout à fait représenter ces éléments dans un tableau classique à une seule dimension. La formule pour accéder à l'élément se trouvant à la ligne L et à la colonne R est alors indice recherché = L * ROWS + C et, inversement, pour connaitre la ligne et la colonne à laquelle se trouve un élément donné au départ de son indice, on utilisera les formule L = indice / ROWS et C = indice % ROWS.

De plus, dans le cas particulier qui nous occupe, ta matrice a pour objectif de représenter une grille d'éléments et donc de nous permettre d'accéder aux "cases adjacentes" à la case sur laquelle on travaille. quand on parle de case adjacente, on envisage quatre directions et les combinaisons qu'elles permettent, à savoir

le haut
le bas
la gauche et
la droite.

Nous pouvons donc représenter ces notions sous la forme d'une énumération qui ressemblerait à
Code:

1 2 3 4 5 6 enum Direction{ up = 1 <<0, down = 1<<1, left = 1<<2, right = 1<<3 };
Cela pourrait se traduire en C++ par une classe proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 template <typename T> class Grid{ public: Grid(size_t l, size_t r, T const & t= T{}):lines_{l},rows{r}, items_{l*r, t}{ } /* permet d'accéder à un élément selon la ligne et la colonne à laquelle il se trouve */ T & operator() (size_t line, size_t row){ assert(line < lines_ && "line index out of bound"); assert(row < rows_ && "row index out of bound"); return items_[line*rows + row]; } /* pareil, mais la constance en plus */ T const & operator() (size_t line, size_t row) const{ return const_cast<Grid<T> *>(this)->operator()(line, row); } /* permet d'accéder à "l'élément adjacent" en fonction de la position courante * et de la direction indiquée */ T & adjacent(size_t currentLine, size_t currentRow, Direction d){ static T empty{}; // un élément vide, pour les cas particuliers /* demander l'élément de gauche et de droite en même temps n'a aucun sens */ assert(d & left && d & right && "Adjacent left + rigth has no sense"); /* pareil pour haut et bas */ assert(d &up && d& down && "Adjacent up + down has no sense") ; /* évitons les cas particuliers */ if( (currentLine == 0 && d & up) || (currentLine >= g.lines() && d & down)) // la première ou la dernière ligne return empty; if( (currentRow == 0 && d & left) || (currentRow >=g.rows() && d& right) ) // la première ou la dernière colonne return empty; if(currentRow >=g.rows() && d& right) return empty; /* calcul de la position de l'élément adjacent */ size_t adjacentRow{d& left ? --currentRow : d&right ? ++currentRow : currentRow}; size_t adjacentLine{d& up? -- currentLine : d & down? ++currentLine : currentLine}; return operator()(adjacentLine, adjacentRow); } /* pareil, la constance en plus */ T const & adjacent(size_t currentLine, size_t currentRow, Direction d) const{ return const_cast<Grid<T> *>(this)->adjacent(currentLine, currentRow, d); } size_t lines() const{ return lines_; } size_t rows const{ returns rows; } private: std::vector<T> items_; };
et tu pourrais donc l'utiliser dans ta classe ParticleSystem sous la forme de
Code:

1 2 3 4 /* ATTENTION !!! un index est toujours positif. Le type idéal pour le représenter * est size_t */ Matrix<std::vector<size_t>> mGrid;
(bien que, jusqu'ici, nous n'ayons pas changé le comportement général : les indice qui se trouve dans le std::vector se trouvant en position 0,0 sont toujours "très éloignés" de ceux se trouvant dans le std::vector de la position 0,1.)

Quant à la fonction adjacent, son principe est simple : elle permettra toujours d'obtenir un élément, quelle que soit la position courante, quelle que soit la direction choisie. Mais, et c'est là qu'est le trait de génie, si on est dans une situation dans laquelle l'élément demandé n'existe pas (parce que l'on demande l'élément "qui se trouve au dessus" de la première ligne, par exemple), elle renverra un élément qui répondra faux à toutes les questions que nous pourrions lui poser (sauf, bien sur, aux questions négative comme empty() ).

C'est ce que l'on appelle l'idiome de l'objet nul.

Si bien que, à défaut d'améliorer les performances de ton algorithme, nous pourrons au moins le simplifier pour lui donner une forme qui serait proche de
Code:

1 2 3 4 5 6 7 8 Soient toutes les directions possibles = up, down, left, right, up|left, up|right, down|left et down|right soit d = la grille que l'on utilise Soit currentLine = ligne de la case qui nous intéresse Soit currentRow = la colonne de la case qui nous intéresse Pour chaque direction possible d soit temp = adjacent(currentLine, currentRow, d) travailler avec temp Fin Pour
En C++, cela pourrait prendre la forme de
Code:

1 2 3 4 5 6 7 8 void ParticleSystem::someFunction(size_t currentLine, size_t currentRow){ /* toutes les directions possibles */ static std::array<Direction, 8> allDirections{up, down, left, right, up|left, up|right, down|left, down|right}; for( auto d : allDirections){ auto /* const */ & adj = mgrid.adjacent(line, roww, d); /* ce qu'il faut faire */ } }
Mais, surtout, le gros problème est que tu (en fait, tu la remplis : ta fonction createGrid devrait s'appeler ... fillGrid, ce serait plus correct ;) )ta grille à chaque fois que tu appelles computesParticles!

Ca signifie, en gros, que chaque fois que tu va faire appel à cette fonction, tu vas devoir t'amuser à passer toutes tes particules en revues pour savoir dans quelle case tu dois les mettre; ce qui est vraiment dommage lorsqu'on sait que, quoi qu'il arrive, une particule qui va se déplacer ne pourra, au mieux, que rester dans la case dans laquelle elle se trouve, au pire que se retrouver dans une case adjacente.

Ton objectif doit donc être d'éviter ces parcours inutiles. Et pour y arriver, il n'y a pas trente-si solutions :

tu dois t'assurer de ne remplir ta grille qu'une seule fois; puis,
A chaque appel à la fonction computesParticles, si la grille n'est par remplie (voir ci-dessous) la remplire, sinon, passer directement à l'étape 3
chaque fois que tu déplaces une particule, poses toi la question de savoir si elle change de case dans la grille

si elle ne change pas de case, tu la laisses bien où elle est
si elle change de case, demande la case adjacente qui correspond à son déplacement et déplace-la dans cette case

Pour le (1) Rajoutes, par exemple, un booleen mgridFillded initialisé à false, qui passera à true à la fin de ta fonction de remplissage

Attention!!! Pour le (3.2) il y a une astuce à prendre en compte du fait que tu utilises un std::vector: quand tu retires un élément du tableau, tu invalide l'itérateur sur lequel tu travailles, ainsi que les itérateurs vers tous les éléments qui suivent celui que tu as supprimé dont tu pourrais disposer.

Tu devras donc "trouver l'astuce" pour palier ce problème ;)

L'énorme avantage, c'est que, pour l'instant, tu parcoures au moins trois fois la liste entière de tes particules :

pour remplir la grille
pour calculer le déplacement de tes particules
pour afficher les particules

En faisant en sorte de ne déplacer dans ta grille que les particules qui on lieu de l'être, tu descendra à deux parcours de la liste entière. D'où, selon toutes vraisemblances, un gain de temps non négligeable ;)

De la même manière, il me semble que tu parcours ta grille au moins en deux occasions:

pour calculer les contacts entre les particules et
pour mettre ta map de particules à jour

Pourquoi ne ferais tu pas en sorte de mettre ta map à jour pour une particule donnée une fois que tu as "fait tout ce que tu devais faire" avec cette particule :question: Un parcours de la grille en moins == ... Beaucoup moins de particules à parcourir pour pouvoir les mettre à jour ;)

En un mot comme en cent : évite les "parcours à répétition" de tes collections. Dis toi qu'une simple boucle proche de
Code:

1 2 3 4 5 Tableau tab; for(size_t i = 0; i < tab.size(); ++i){ auto truc =tab[1]; /* tout ce qu'il faut faire avec truc */ }
va se traduire à l'exécution, pour un tableau de 200 éléments, par quelque chose comme
Code:

1 2 3 4 5 6 7 8 9 adresseDepart = 0xABCDEF /* ce qui suit va se répéter deux cents fois !!! * ======================= */ adresseTemporaire = adresseDeDepart + (i * taille de l'élément) // (1) charger (un registre quelconque) avec ce qu'il y a dans adresseTemporaire /* tout ce qu'il faut faire avec ce qu'il y a dans le registre */ incrementer i si i < 200 retourner en (1)
Cela devrait te permettre de te rendre compte que tu as largement intérêt à faire "tout ce que tu peux faire" avec un élément tant que "tu l'as en main", au lieu de ramasser "tous les éléments un à un" pour faire un truc puis de recommencer pour... faire autre chose ;)

Pourquoi passer un pointeur sur Map :question: D'ailleurs, pourrais tu nous montrer le code complet de cette classe :question: Comment celle que tu transmet à la fonction computeParticles est-elle créée :question:

18/09/2017, 10h32
guppyworld

Re,

Merci de votre aide, désolé pour la réponse un peu tardive :)

Citation:

Envoyé par koala01

Alors, concernant le code:

Pourquoi mParticles est il un tableau de taille fixe "C style" :question: Tôt ou tard, quand tes problèmes de performances seront résolus, tu voudras augmenter le nombre de particules au point de faire exploser ta pile!

Pour le moment c'est un tableau de taille fixe mais oui après je pourrais le remplacé par un vector.

Citation:

Envoyé par koala01

As tu une vague idée de ce que représente ton code std::vector<int> mGrid[96][199];:question: c'est une matrice qui contient 19 104 tableaux d'entiers! le tout placé dans la pile (à moins que tu n'aies recours à l'allocation dynamique pour ton ParticleSystem). Heu, je veux bien, mais... t'es sur d'avoir besoin de cela :question:

Je peux aussi faire a la limite std::vector<int> mGrid[96*199].

Citation:

Envoyé par koala01

mGrid en lui-même va, effectivement, placer les 19000 std::vector l'un à la suite de l'autre en mémoire. Mais std::vector est une classe qui a recours à l'allocation dynamique de la mémoire pour pouvoir représenter les éléments qu'ils contient d'une manière contigue en mémoire. C'est à dire que les X éléments contenus par le std::vector qui se trouve en mGrid[0][0] n'ont pour ainsi dire aucune chance d'être contigus avec ceux qui se trouvent dans mGrid[0][1] (ou dans mGrid[1][0])

Cela peut ne pas être catastrophique, ou non...

Comment je suis censé faire alors ? Car je ne peux pas savoir combien de particules une case va contenir donc j'utilise des vectors.

Citation:

Envoyé par koala01

Mais, surtout, le gros problème est que tu (en fait, tu la remplis : ta fonction createGrid devrait s'appeler ... fillGrid, ce serait plus correct ;) )ta grille à chaque fois que tu appelles computesParticles!

Ca signifie, en gros, que chaque fois que tu va faire appel à cette fonction, tu vas devoir t'amuser à passer toutes tes particules en revues pour savoir dans quelle case tu dois les mettre; ce qui est vraiment dommage lorsqu'on sait que, quoi qu'il arrive, une particule qui va se déplacer ne pourra, au mieux, que rester dans la case dans laquelle elle se trouve, au pire que se retrouver dans une case adjacente.

Mon but était d'éviter de devoir faire des remove d'élement qui se trouve au milieu de vector lorsqu'une particule passe d'une case à une autre.
Après oui cela permet de gagner een temps sur la fonction qui rempli la grille.

Citation:

Envoyé par koala01

Cela devrait te permettre de te rendre compte que tu as largement intérêt à faire "tout ce que tu peux faire" avec un élément tant que "tu l'as en main", au lieu de ramasser "tous les éléments un à un" pour faire un truc puis de recommencer pour... faire autre chose

Je ne peux pas traiter les particules une seule fois car ce que je fais:

-Parcours de toute les particules pour trouver les contacts de cette particule.
-Une fois toutes les contacts trouvés, on peux calculer la pression de la particule
-Parcourir tous les contacts pour mettre à jour la vélocité en utilisant la pression

Citation:

Envoyé par koala01

Pourquoi passer un pointeur sur Map D'ailleurs, pourrais tu nous montrer le code complet de cette classe Comment celle que tu transmet à la fonction computeParticles est-elle créée .

Je viens de mettre le code sur github ça sera plus pratique que les copier-coller en masse. :)
https://github.com/AlexisMalamas/Gam...master/War_4.3
18/09/2017, 12h55
koala01
Citation:

Envoyé par guppyworld

Je peux aussi faire a la limite std::vector<int> mGrid[96*199].

Ce sera déjà mieux ;)

Citation:

Comment je suis censé faire alors ? Car je ne peux pas savoir combien de particules une case va contenir donc j'utilise des vectors.

Tu choisi la bonne manière de subdiviser ton espace.

En gros, tu as trois possibilités majeure pour subdiviser ton espace (il n'y a que la troisième possibilité qui n'aura vraiment de sens que pour un quadtree / un octreee ):

Ou bien tu décides de subdiviser ton espace par rapport au nombre d'éléments (tes particules, dans le cas présent) que peut contenir chaque subdivision. Tu peux définir une valeur maximale (recommandé) au delà de laquelle tu subdivise à nouveau ta division et éventuellement une valeur minimale au delà de laquelle tu décideras d'annuler la subdivision.

Cette manière de travailler présente l'avantage d'avoir toujours "à peu près le même nombre" de particule par subdivision. Par contre, la superficie de chaque subdivision et la "densité" d'éléments par mesure de surface / de volume est variable: tu peux aussi bien te retrouver avec trois particules très éloignées les unes des autres dans une très grande subdivision que te retrouver avec le maximum de particules que tu as décidé "entassées" dans une subdivision dont sa surface / son volume suffit à peine à les contenir (voire, soit "trop petit" pour arriver à les contenir)

Ou bien, tu décides de fixer la taille (superficie / volume) de chaque subdivision, et de subdiviser une partie de ton espace aussi longtemps que tu n'es pas descendu en dessous de cette limite. Cela te créera des subdivisions de taille égale, mais tu pourrais très bien te retrouver avec des subdivisions "pleines à craquer" et d'autres totalement vides.

Ou bien, tu décides de limiter le nombre de fois que tu subdivise ton espace. C'est surtout pratique dans un quadtree / octree parce que cela te permet de limiter le nombre de noeuds à parcourir depuis ton "espace global" pour atteindre un "sous espace particulier".

Mais c'est surtout nécessaire en conjonction avec au moins l'une des deux autres possibilités invoquées, de manière à pouvoir décider à un moment que "l'espace est assez subdivisé, et tant pis si certaines subdivisions dépassent le nombre d'éléments admis".

Citation:

Mon but était d'éviter de devoir faire des remove d'élement qui se trouve au milieu de vector lorsqu'une particule passe d'une case à une autre.
Après oui cela permet de gagner een temps sur la fonction qui rempli la grille.

De manière générale, cela te prendra toujours bien moins de temps de supprimer un élément depuis le milieu de ta collection afin de le déplacer dans ta grille que de recréer ta grille à chaque fois ;)

Citation:

Je ne peux pas traiter les particules une seule fois car ce que je fais:

-Parcours de toute les particules pour trouver les contacts de cette particule.
-Une fois toutes les contacts trouvés, on peux calculer la pression de la particule
-Parcourir tous les contacts pour mettre à jour la vélocité en utilisant la pression

Non, ce que tu ne peux pas faire, c'est calculer les contacts qu'il y a entre les différentes particules tant que tu n'as pas évalué la position de toutes les particules. Ca, nous sommes d'accord ;)

Mais rien ne t'empêche, une fois que tu as évalué la position probable de toutes tes particules à l'instant T+1, de faire tous les calculs dus aux contacts en une fois pour chaque particule, ce qui sera toujours mieux que de changer ta particule de référence sans arrêt.

Je crois aussi que tu devrais commencer par simplifier un peu les choses en ne t'attaquant qu'à un problème à la fois:
- Commence par une seule particule qui se trouve "bloquée" dans ton espace. Quand elle rencontre la limite de l'espace, elle rebondit dessus de la même manière qu'une balle de billard (c'est relativement simple à mettre en place ;) )
- Une fois que tu auras quelque chose de fonctionnel, rajoute deux ou trois particules, et fait en sorte qu'elles rebondissent les unes sur les autres lorsqu'elles entrent en collision.
- Puis rajoute la subdivision de ton espace, car tu n'aura aucun besoin de tester les collision si tes quatre particules se trouvent à une extrémité de ton espace différente.
- Rajoutes ensuite "suffisamment de particules" (100, 200) que pour remplir correctement ton espace et voir comment cela se passe.
- Ensuite, rajoutes les notions une à une (en testant et en observant le résultat à chaque fois): la gravité en premier, la densité (fixe) ensuite, puis la compression (quand une particule est "prise en sandwich" par deux autres), ...
- Termines en rajoutant des particules "petit à petit" (par 100 ou 200 à la fois)
De cette manière, tu pourras te focaliser sur un problème à la fois, mais tu auras toujours le "plaisir de voir" que le résultat correspond à tes besoins.
18/09/2017, 13h29
Bousk

C'est peut-être une connerie mais : ne pourrait-on pas avoir 1 seul vector de particule std::vector<particules> que tu tries en fonction de leur région pour que les proches dans une même région soient contigües ? plutôt que d'avoir un vector par région.
Si non, selon la taille des particules, peut-être qu'un vector unique et un vector par région avec un simple pointeur vers les particules de la région pourrait limiter les cache miss. Selon le nombre de particules que l'on peut mettre dans le cache.
19/09/2017, 17h00
guppyworld

Citation:

Envoyé par koala01

Mais rien ne t'empêche, une fois que tu as évalué la position probable de toutes tes particules à l'instant T+1, de faire tous les calculs dus aux contacts en une fois pour chaque particule, ce qui sera toujours mieux que de changer ta particule de référence sans arrêt.

Je n'ai pas très bien compris ou est-ce que je changer la particule de référence sans arrêt. Le fait de parcourir les particules une par une ?

Citation:

Envoyé par koala01

Je crois aussi que tu devrais commencer par simplifier un peu les choses en ne t'attaquant qu'à un problème à la fois:

Commence par une seule particule qui se trouve "bloquée" dans ton espace. Quand elle rencontre la limite de l'espace, elle rebondit dessus de la même manière qu'une balle de billard (c'est relativement simple à mettre en place )
Une fois que tu auras quelque chose de fonctionnel, rajoute deux ou trois particules, et fait en sorte qu'elles rebondissent les unes sur les autres lorsqu'elles entrent en collision.
Puis rajoute la subdivision de ton espace, car tu n'aura aucun besoin de tester les collision si tes quatre particules se trouvent à une extrémité de ton espace différente.
Rajoutes ensuite "suffisamment de particules" (100, 200) que pour remplir correctement ton espace et voir comment cela se passe.
Ensuite, rajoutes les notions une à une (en testant et en observant le résultat à chaque fois): la gravité en premier, la densité (fixe) ensuite, puis la compression (quand une particule est "prise en sandwich" par deux autres), ...
Termines en rajoutant des particules "petit à petit" (par 100 ou 200 à la fois)

De cette manière, tu pourras te focaliser sur un problème à la fois, mais tu auras toujours le "plaisir de voir" que le résultat correspond à tes besoins.

Oui, j'ai déja fait tous ça. La simulation fonctionne bien et la seule chose que je recherche maintenant est la quantité. :P

Citation:

Si non, selon la taille des particules, peut-être qu'un vector unique et un vector par région avec un simple pointeur vers les particules de la région pourrait limiter les cache miss. Selon le nombre de particules que l'on peut mettre dans le cache.

Stocker les références des particules plutôt que les indices des particules ? Mouè je sais pas trop si c'est vraiment plus efficace. Faut que je test ça.
19/09/2017, 18h24
koala01
Citation:

Envoyé par guppyworld

Je n'ai pas très bien compris ou est-ce que je changer la particule de référence sans arrêt. Le fait de parcourir les particules une par une ?

Imaginons que tu aies devant toi une grande table avec 100 "trucs" en bois -- de forme et de taille quelconque, mais identique -- rangés dans un ordre quasi militaire.

Et imaginons que tu aies pour instructions quelque chose comme
- tous les trucs doivent être dépoussiérés
- si le vernis d'un truc est abîmé, tu dois le poncer pour retirer l'ancienne couche de vernis et le revernir
Mais, et c'est une règle absolue, tout truc sur lequel tu n'es pas occupé à travailler doit être remis scrupuleusement à sa place. Sinon, gare à la schlakke!

Sachant que le nettoyage d'un truc prend un temps T, que sa vérification prend un temps U, que son ponçage prend un temp V et que son vernissage prend un temps W et que tous ces temps sont constants, qu'est ce qui sera le plus rapide :question:
A - tu prend un truc, tu le nettoies, tu le vérifies et, si besoin, tu le ponces et tu le vernis ou
B -
- tu prend un truc, tu le nettoies, tu le repose pour passer au suivant, et ce pour tous les trucs
- tu prend un truc, tu le vérifie, et tu marque "quelque part" s'il faut le poncer et le vernir avant de le poser et de passer au suivant, et ce pour tous les trucs
- tu prends un truc qui doit être poncé, tu le ponces, puis tu le poses et passes au truc suivant qui doit être poncé, et ce pour tous les trucs qui doivent être poncés
- tu prend un truc qui a été poncé, tu le vernis, tu le poses et tu passe au truc suivant qui a été poncé, et ce pour tous les trucs qui doivent être vernis (et qui sont donc sensés avoir été poncés au préalable)
Je peux te garantir que la solution A sera bien plus rapide, car chaque truc ne sera pris en main et reposé qu'une seule fois, et que ca aussi ca prend du temps. Or, la solution B imposerait que chaque truc soit pris en main et reposé minimum deux fois. Et cela va monter à quatre fois pour ceux qui doivent être poncés et vernis. Et tout le temps que tu perds à prendre un truc et à le reposer, c'est du temps perdu ;)

Hé bien, tu peux te dire qu'il en va exactement de même pour le processeur: accéder à une donnée qui se trouve en mémoire, cela prend du temps parce que cela implique deux choses:
- la barrette mémoire doit RAM se "brancher" de manière à fournir la donnée qui est demandée et
- le processeur doit copier la donnée qu'il a demandé dans un registre
Ca prend d'ailleurs tellement de temps d'obtenir une information depuis la mémoire RAM que les processeurs utilisent ce que l'on appelle la mise en cache de données. Le principe est relativement simple : une fois que la barrette mémoire a été branchée afin de lui permettre de fournir une donnée, la différence de temps nécessaire à l'obtention de 1 seul octet et le temps qu'il faut pour obtenir 1ko (1024 octets) est "minime" (au yeux de la RAM).

Mais ne te méprends pas, cela prend quand même "un temps fou" aux yeux du processeurs, dont l'unité de temps est un bon millier de fois plus petite que celle de la RAM.

Si bien que, lorsque le processeur à la RAM de lui fournir une donnée particulière, il ne se contente pas de la seule donnée en question: il récupère directement 1ko qu'il va placer dans une mémoire particulière appelée le cache. Il s'agit d'une très petite quantité de mémoire, mais hyper rapide (par comparaison aux barrettes de RAM qui proposent de très grands espaces de stockage mais dont l'accès est particulièrement lent).

Le but de la manoeuvre est de se dire que, avec "un peu de chance" la donnée que l'on demandera au processeur de manipuler "la fois d'après" sera... juste à coté de celle qu'il doit manipuler pour l'instant. Evidemment, c'est un quitte ou double. Car, si la donnée que le processeur doit manipuler "après" est "à coté" de celle qu'il vient de terminer de manipuler, il n'y a même plus besoin de s'adresser à la RAM. Et plus on sera dans ce cas de figure, moins le processeur devra attendra après la donnée qu'il doit manipuler. Par contre, si la donnée dont il a besoin "après" n'est pas dans le cache, il a quand même demandé 1ko de données inutiles.

Mais la mise en cache des données n'est que la première partie du travail, car, pour que le processeur puisse manipuler une donnée, il faut qu'il puisse y accéder au travers d'un de ses registres. Charger une donnée dans un registre depuis le cache du processeur, cela ne prend pas vraiment longtemps. Mais une goutte de pluie ne représente rien par rapport à la masse d'eau de l'océan. Et pourtant, l'océan n'est composé que de gouttes de pluie! Et tu as déjà vu les inondations et les dégats que peut provoquer la pluie :question:

Tu dois donc bien penser que, quelle que soit l'action que tu entreprends, elle va prendre "un certain temps" (ca me fait penser au sketche de Fernand Raynaud ca). Et, si tu multiplie suffisamment "ce certain temps", tu obtiendra une durée assez longue que pour sembler pénible à un humain (qui a pourtant déjà beaucoup de mal à entrevoir les centièmes de secondes)

Voir 40 message(s) de cette discussion en une page