Game Of Life

Le problème exposé dans ce sujet a été résolu.

Bonjour !

Après deux ans sans avoir touché au C++, j’ai décidé de m’y remettre en faisant un petit Game Of Life. Je suis en train de faire la fonction pour voir si une cellule doit vivre ou mourir mais je bloque totalement. Voici ce que j’ai fait pour le moment :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void liveOrDie(bool (&grid)[gridSize][gridSize]) {
    for (unsigned int i = 0; i < gridSize; ++i) {
        for (unsigned int j = 0; j < gridSize; ++j) {
            unsigned int alive{0};

            // count alive cells around the grid[i][j] cell.
            for (int a = -1; a < 2; ++a) {
                for (int b = -1; b < 2; ++b) {
                    if (grid[a][b] && (a != 0 && b != 0))
                        ++alive;
                }
            }

            // change the state of the grid[i][j] cell.
            if (!grid[i][j] && alive == 3)
                grid[i][j] = true;
            else
                grid[i][j] = grid[i][j] && (alive == 2 || alive == 3);
        }
    }
}

Pour compter les cellules vivantes autour de ma cellule, j’aimerais faire quelque chose de propre et éviter 36000 if pour vérifier que ma cellule ne soit pas en bordure de grille (sinon je fais une erreur comme quoi je sors des limites du tableau). Je suis certain qu’il y a une solution plus propre qui m’éviterais ça.

Merci de votre aide !

Je vous met le programme complet, si vous avez des remarques, n’hésitez surtout pas :

 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
#include <iostream>

const unsigned int gridSize{10};

void drawGrid(bool const (&grid)[gridSize][gridSize]);

void liveOrDie(bool (&grid)[gridSize][gridSize]);

int main() {
   bool grid[gridSize][gridSize] = {false};

   // Making a glider
   grid[2][5] = true;
   grid[3][6] = true;
   grid[4][4] = true;
   grid[4][5] = true;
   grid[4][6] = true;

   drawGrid(grid);
   liveOrDie(grid);
   drawGrid(grid);

   return 0;
}

void drawGrid(bool const (&grid)[gridSize][gridSize]) {
   for (unsigned int i = 0; i < gridSize; ++i) {
       for (unsigned int j = 0; j < gridSize; ++j) {
           if (grid[i][j])
               std::cout << " O ";
           else
               std::cout << " . ";
       }

       std::cout << std::endl;
   }
}

void liveOrDie(bool (&grid)[gridSize][gridSize]) {
   for (unsigned int i = 0; i < gridSize; ++i) {
       for (unsigned int j = 0; j < gridSize; ++j) {
           unsigned int alive{0};

           // count alive cells around the grid[i][j] cell.
           for (int a = -1; a < 2; ++a) {
               for (int b = -1; b < 2; ++b) {
                   if (grid[a][b] && (a != 0 && b != 0))
                       ++alive;
               }
           }

           // change the state of the grid[i][j] cell.
           if (!grid[i][j] && alive == 3)
               grid[i][j] = true;
           else
               grid[i][j] = grid[i][j] && (alive == 2 || alive == 3);
       }
   }
}
+0 -0

Souvent le jeu de la vie se joue soit sur une grille infinie, soit sur une grille qui wrap (la dernière cellule à droite est le voisin de gauche de la première cellule de gauche, idem haut/bas).

Si j’étais toi je wrapperais. Je sais que ça répond pas vraiment à ta question. Tu comptes comment les cellules hors-cadre ? Mortes ?

+0 -0

Il y a quelques années, la ’good practice’ pour des grilles de taille fixe était la suivante : Imaginons une grille 20 lignes, 10 colonnes. On étend la grille, en ajoutant une ’bordure’ tout autour, donc 22 lignes, et 12 colonnes. Et on travaille non pas sur un tableau grid[22,12], mais sur un vecteur[264] (264=22*12)

Chaque case peut avoir 3 valeurs : Vivante, Morte, Bordure.

Puis tu as un vecteur Direction, avec les 8 directions : -13,-12,-11,-1,1,11,12,13. Essaie d’imaginer d’où viennent ces nombres -13, -12, -11… ils ne sont pas sortis d’un chapeau.

Et à partir d’une cellule, si la valeur de cette cellule est Bordure, tu ne fais rien, cette cellule restera toujours Bordure. Et si la valeur n’est pas Bordure, tu peux faire :

1
2
3
4
pour direction = 0 a 7
   cellule_voisine = cellule_en_cours + tab_direction[direction]
   // et tu traites le contenu de 'cellule_voisine', tu as l'assurance que cellule_voisine est un nombre entre 0 et 263.
fin

Sinon, peu impoprte si tu utilises la technique ci-dessus ou non, je pense que tu as un problème dans ton code. Pour illustrer ce problème, permute les lignes 40 et 41. Normalement, ça ne devrait rien changer au résultat, on est d’accord ?

Et tu vas voir qu’à partir d’un même jeu de données initiales, tu vas obtenir un résultat différent entre d’une part ton programme actuel, et d’autre part la version modifiée en permutant les lignes 40 et 41.

Partant de là, je te laisse investiguer.

+0 -0

Souvent le jeu de la vie se joue soit sur une grille infinie, soit sur une grille qui wrap (la dernière cellule à droite est le voisin de gauche de la première cellule de gauche, idem haut/bas).

Si j’étais toi je wrapperais. Je sais que ça répond pas vraiment à ta question. Tu comptes comment les cellules hors-cadre ? Mortes ?

victor

La grille infinie dans la console c’est un peu inutile, je verrais si je fais une interface graphique avec la SFML un de ces quatre. Mais c’est vrai que wrapper n’est pas bête. Même beaucoup plus intéressant ! Les cellules hors cadre n’existent plus pour moi donc oui, elles sont comme mortes.

Mais du coup si je wrappe, comment fonctionne la logique ?

Il y a quelques années, la ’good practice’ pour des grilles de taille fixe était la suivante : Imaginons une grille 20 lignes, 10 colonnes. On étend la grille, en ajoutant une ’bordure’ tout autour, donc 22 lignes, et 12 colonnes. Et on travaille non pas sur un tableau grid[22,12], mais sur un vecteur[264] (264=22*12)

Chaque case peut avoir 3 valeurs : Vivante, Morte, Bordure.

Puis tu as un vecteur Direction, avec les 8 directions : -13,-12,-11,-1,1,11,12,13. Essaie d’imaginer d’où viennent ces nombres -13, -12, -11… ils ne sont pas sortis d’un chapeau.

elegance

J’ai compris ce que représente ces 8 directions, ce sont les cellules voisines de la cellule. Dans le vecteur j’irais à la position de ma cellule -13 pour avoir sa voisine, pareil avec -12, -11 etc. Mais je ne sais pas comment tu les as trouvé. ^^

J’aime bien ta solution, je vais d’abord commencer par celle-ci puis je ferais le wrapping. :)

Merci de votre aide !

+0 -0

Mais du coup si je wrappe, comment fonctionne la logique ?

Wizix

Si tu wrap y’a pas de différence entre le bord de la grille et le milieu, donc la logique est identique ;)

Par exemple le voisin de droite de la cellule {x: 10, y: 10}, si x est l’abscisse et que la grille fait 15 de côté, c’est {x: (10 + 1) % 15, y: 10}.

+0 -0

(Je suppose ici que tu veux considérer les cellules du bord comme perpétuellement mortes.) C’est le genre de morceaux de code que j’ai eu l’occasion de taper un très grand nombre de fois, et ma conclusion c’est que le plus clair est de faire quelque chose comme (à adapter éventuellement pour que ça ressemble plus à du C++) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
const int NB_DIRS = 4;
const int dirx[NB_DIRS] = {0, 0, 1, -1};
const int diry[NB_DIRS] = {-1, 1, 0, 0};

bool is_in_grid(int x, int y) { return x >= 0 && x < gridSize && y >= 0 && y < gridSize; }

for (int y = 0; y < gridSize; ++y)
    for (int x = 0; x < gridSize; ++x) {
        int nb_neigh_alive = 0;
        for (int d = 0; d < NB_DIRS; ++d) {
            int dx = x + dirx[d], dy = y + diry[d];
            if (is_in_grid(dx, dy) && alive[dy][dx]) nb_neigh_alive++;
        }
        // ...
    }

Édit : je mets aussi la remarque suivante en secret parce que je pense que c’est ce qu’on essaye de te faire deviner plus haut.

Par contre, je n’ai pas regardé en détail, mais il me semble que tu tombes dans l’écueil de modifier ta grille au fur et à mesure du parcours. Ça ne correspond pas aux règles du vrai "jeu de la vie".

+0 -0

Je suis arrivé à un résultat presque satisfaisant. D’un côté ça fonctionne mais de l’autre ça fonctionne que jusqu’à un moment… :lol:

Voici le 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
const unsigned int nbDirs{8};
const int dirx[nbDirs] = {-1,  0,  1, 1, 1, 0, -1, -1};
const int diry[nbDirs] = {-1, -1, -1, 0, 1, 1,  1,  0};

void liveOrDie(bool (&grid)[gridSize][gridSize]) {
    bool gridTemp[gridSize][gridSize] = {false};

    for (unsigned int y = 0; y < gridSize; ++y) {
        for (unsigned int x = 0; x < gridSize; ++x) {
            unsigned int alive{0};

            // count alive cells around the grid[y][x] cell.
            for (unsigned int d = 0; d < nbDirs; ++d) {
                unsigned int dx{x + dirx[d]};
                unsigned int dy{y + diry[d]};

                if (grid[dy % gridSize][dx % gridSize]) {
                    ++alive;
                }
            }

            // change the state of the grid[y][x] cell.
            if (!grid[y][x] && alive == 3)
                gridTemp[y][x] = true;
            else
                gridTemp[y][x] = grid[y][x] && (alive == 2 || alive == 3);
        }
    }

    copyGrid(gridTemp, grid);
}

En essayant mon planeur, ça fonctionne jusqu’à la génération n°5 où j’obtiens ça :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Génération 4:
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  O  .  .  .
 .  .  .  .  .  .  .  O  .  .
 .  .  .  .  .  O  O  O  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
# Génération 5:
 .  .  .  .  .  .  O  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  O  .  O  .  .
 .  .  .  .  .  .  O  O  .  .
 .  .  .  .  .  .  O  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .  .  .

Mais jusqu’à la génération 5 pas de soucis, j’ai exactement les patterns que je suis sensé avoir.

Pareil, je vous mets le code complet :

 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
#include <iostream>

const unsigned int gridSize{10};
const unsigned int nbDirs{8};

const int dirx[nbDirs] = {-1,  0,  1, 1, 1, 0, -1, -1};
const int diry[nbDirs] = {-1, -1, -1, 0, 1, 1,  1,  0};

void drawGrid(const bool (&grid)[gridSize][gridSize]);
void liveOrDie(bool (&grid)[gridSize][gridSize]);
void copyGrid(bool (&gridOne)[gridSize][gridSize], bool (&gridTwo)[gridSize][gridSize]);

int main() {
   bool grid[gridSize][gridSize] = {false};

   // Making a glider
   grid[2][5] = true;
   grid[3][6] = true;
   grid[4][4] = true;
   grid[4][5] = true;
   grid[4][6] = true;


   for (unsigned int i = 0; i < 5; ++i) {
       drawGrid(grid);
       liveOrDie(grid);
       std::cout << std::endl;
   }
   drawGrid(grid);

   return 0;
}

void drawGrid(const bool (&grid)[gridSize][gridSize]) {
   for (unsigned int i = 0; i < gridSize; ++i) {
       for (unsigned int j = 0; j < gridSize; ++j) {
           if (grid[i][j])
               std::cout << " O ";
           else
               std::cout << " . ";
       }

       std::cout << std::endl;
   }
}

void liveOrDie(bool (&grid)[gridSize][gridSize]) {
   bool gridTemp[gridSize][gridSize] = {false};

   for (unsigned int y = 0; y < gridSize; ++y) {
       for (unsigned int x = 0; x < gridSize; ++x) {
           unsigned int alive{0};

           // count alive cells around the grid[y][x] cell.
           for (unsigned int d = 0; d < nbDirs; ++d) {
               unsigned int dx{x + dirx[d]};
               unsigned int dy{y + diry[d]};

               if (grid[dy % gridSize][dx % gridSize]) {
                   ++alive;
               }
           }

           // change the state of the grid[y][x] cell.
           if (!grid[y][x] && alive == 3)
               gridTemp[y][x] = true;
           else
               gridTemp[y][x] = grid[y][x] && (alive == 2 || alive == 3);
       }
   }

   copyGrid(gridTemp, grid);
}


void copyGrid(bool (&gridOne)[gridSize][gridSize], bool (&gridTwo)[gridSize][gridSize]) {
   for (unsigned int y = 0; y < gridSize; ++y) {
       for (unsigned int x = 0; x < gridSize; ++x) {
           gridTwo[y][x] = gridOne[y][x];
       }
   }
}
+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte