Jeu de la vie : Incompréhensions sur l'évolution

Affichage des motifs

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

Bonjour, n'ayant jamais codé de Jeu de la Vie auparavant, j'ai voulu m'y essayer. Néamoins je me suis rendu compte qu'après (selon moi) avoir correctement appliqué les règles, mon algorithme n'arrive n'affiche pas les motifs qu'ils devrait.

Sans tarder, le code qui effectue l'évolution :

 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
void GameCtx_set_status(GameCtx *game, const Uint16 x, const Uint16 y)
{
   Uint16 i, j, neighbours = 0;
   Uint16 xmin, ymin, xmax, ymax;
   _Bool status = game->grid[y][x];
   
   !x ? (xmin = 0) : (xmin = x - 1);
   !y ? (ymin = 0) : (ymin = y - 1);

   (x < GRID_X - 1) ? (xmax = x + 1) : (xmax = GRID_X - 2);
   (y < GRID_Y - 1) ? (ymax = y + 1) : (ymax = GRID_Y - 2);

   for(j = ymin; j <= ymax; j++)
   {
       for(i = xmin; i <= xmax; i++)
       {
           if(game->grid[j][i])
               neighbours++;
       }
   }

   if(status)
       neighbours--;

   if(!status && neighbours == 3)
       status = 1;
   if(status && (neighbours < 2 || neighbours > 3))
       status = 0;

   game->grid[y][x] = status;
}

void GameCtx_evolve(GameCtx *game)
{
   Uint16 i, j;

   for(j = 0; j < GRID_Y; j++)
   {
       for(i = 0; i < GRID_X; i++)
           GameCtx_set_status(game, i, j);
   }
}

Pourtant en regardant les règles, je trouve son évolution normale. Selon Wikipedia :

Image utilisateur devrais donner Image utilisateur et à nouveau Image utilisateur et se répéter à l'infini.

Ici, ces trois cellules initiales deviennent Image utilisateur puis Image utilisateur

En sachant que je parcours la grille de gauche à droite et de haut en bas :

Au premier tour : Rien ne change pour la cellule en haut à gauche, la suivante devient vivante car elle a trois voisines, la suivante aussi, ensuite sur la nouvelle ligne celle à gauche ne change pas car elle a deux voisines, la suivante meure car elle a quatre voisines, et rien ne change pour la dernière.
Au second tour : Il n'y a aucun changement pour les deux premières cellules vivantes, la suivante meure car elle n'a qu'une vosine, celle d'après nait, et la dernière ne change pas.

On arrive donc à un motif stable, ce qui m'a l'air normal. Alors comment ce fait-il que selon wikipedia et plein d'autre ce motif devrait revenir à son origine ? Est-ce j'ai loupé quelque chose ? J'aimerais comprendre comment l'évolution devrais normalement se dérouler.

+0 -0

Bonjour,

Ton problème est que tu fais les calculs sur la grille que tu es en train de modifier. Il faut toujours compter les voisins sur la grille du tour précédent. En pratique ça veut dire que tu a besoin de 2 grilles. Il y a bien sur des astuces si tu veux être plus économe en mémoire mais ça demande un poil plus de gymnastique.

+0 -0

L'évolution se déroule correctement maintenant :

 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
Uint32 GameCtx_get_neighbours(GameCtx *game, const Uint32 x, const Uint32 y)
{
   Uint32 i, j, neighbours = 0;
   Uint32 xmin, ymin, xmax, ymax;
   
   !x ? (xmin = 0) : (xmin = x - 1);
   !y ? (ymin = 0) : (ymin = y - 1);

   (x < GRID_X - 1) ? (xmax = x + 1) : (xmax = GRID_X - 2);
   (y < GRID_Y - 1) ? (ymax = y + 1) : (ymax = GRID_Y - 2);
   
   for(j = ymin; j <= ymax; j++)
   {
       for(i = xmin; i <= xmax; i++)
       {
           if(game->grid[j][i])
               neighbours++;
       }
   }
   
   if(game->grid[y][x])
       neighbours--;

   return neighbours;
}

void GameCtx_evolve(GameCtx *game)
{
   Uint32 i, j, neighbours;
   
   _Bool n_grid[GRID_Y][GRID_X];
   
   for(j = 0; j < GRID_Y; j++)
   {
       for(i = 0; i < GRID_X; i++)
       {
           n_grid[j][i] = game->grid[j][i];
           neighbours = GameCtx_get_neighbours(game, i, j);

           if(!n_grid[j][i] && neighbours == 3)
               n_grid[j][i] = 1;
           else if(n_grid[j][i] && (neighbours < 2 || neighbours > 3))
               n_grid[j][i] = 0;
       }
   }

   for(j = 0; j < GRID_Y; j++)
   {
       for(i = 0; i < GRID_X; i++)
           game->grid[j][i] = n_grid[j][i];
   }
}

J'ai repris quelques exemples que j'ai vu, ce n'est pas explicitement dit dans les règles qu'il est nécessaire d'utiliser deux grilles. Par contre, c'est vrai qu'au niveau de la mémoire ça devient un peu chaud, encore plus pour le processeur où je dépasse quelques fois rapidement les 50 % lorsqu'il y a un certain nombre de cellules.

+0 -0

Tu peux utiliser un tableau contenant 2 grilles.

Il te reste alors à travailler sur le numéro de l'itération courante modulo 2 pour sélectionner lequel sera la source, et lequel sera la cible. Tu t'épargneras une phase de recopiage. Il seront tour à tour source et cible.

Si tu te sens une âme de tueur de la mort, tu peux décider d'utiliser des quad-tree pour diviser ta grille en sous-grilles plus petites, tu t'imposes alors de ne modifier que les sous-grilles dans lesquelles il y a des cellules vivantes, tu gagnerais un peu de processeur.

+0 -0

Ce n'est pas dit dans les règles que tu dois utiliser 2 grilles car ça n'a rien à voir avec le règle. Cependant, l'implémentation des règles la plus simple utilise 2 grilles. D'ailleurs, tu peux n'utiliser qu'une grille.

+1 -0

Ce n'est pas dit dans les règles que tu dois utiliser 2 grilles car ça n'a rien à voir avec le règle. Cependant, l'implémentation des règles la plus simple utilise 2 grilles. D'ailleurs, tu peux n'utiliser qu'une grille.

ache

En effet :

 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
void GameCtx_evolve(GameCtx *game)
{
    SDL_Point changes[GRID_X * GRID_Y];
    Uint32 i, j, neighbours, nb_changes = 0;
    
    for(j = 0; j < GRID_Y; j++)
    {
        for(i = 0; i < GRID_X; i++)
        {
            neighbours = GameCtx_get_neighbours(game, i, j);

            if((!game->grid[j][i] && neighbours == 3) ||
            (game->grid[j][i] && (neighbours < 2 || neighbours > 3)))
            {
                changes[nb_changes].x = i;
                changes[nb_changes].y = j;

                nb_changes++;
            }
        }
    }

    for(i = 0; i < nb_changes; i++)
    {
        if(game->grid[changes[i].y][changes[i].x])
            game->grid[changes[i].y][changes[i].x] = 0;
        else
            game->grid[changes[i].y][changes[i].x] = 1;
    }
}

Ce que je voulais dire par là, c'est qu'il n'est pas précisé qu'il faut utiliser la grille précédente sans apporter de modifications en même temps qu'on la parcours. Sinon, c'est quand un peu plus économe.

Algue-Rythme : Je suppose que c'est cette méthode qui doit utiliser le moins de ressources après une comparaison des trois. Même si pour le moment j'ai un petit problème de clignotement, sans doute pas trop difficile à règler. Je vais voir après, si je peux découper la grille en d'autres sous-grilles et donc éviter de devoir faire trop de boucles.

+0 -0

Matrice creuse au lieu d'une matrice pleine si tu bosses sur des grosses grilles, ça devrait régler le problème de mémoire. (en C++ std::unordered_set<Position>)

Si tu conserves une matrice pleine, une grille unique associée avec tableau de 9 cases est suffisant.

+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