Catégorie : Algorithmie

Algorithmie

Présentation du jeu de la vie

Introduction

Le jeu de la vie est un automate fini particulier proposé par John Conway de Cambridge dans les années 1970.

Un automate fini est une machine réalisant une seule action à partir d’une donnée d’entrée en respectant des règles prédéfinies.

Le jeu se déroule sur une grille à deux dimensions, théoriquement infinie (mais de longueur et de largeur finies et plus ou moins grandes dans la pratique. Les cases, qu’on appelle des « cellules », par analogie avec les cellules vivantes, peuvent prendre deux états distincts : « vivantes » ou « mortes ».

À chaque étape, l’évolution d’une cellule est entièrement déterminée par l’état de ses huit voisines de la façon suivante :

  • Si à un instant t une case est occupée par une particule, et qu’elle possède plus de trois voisins, alors à l’instant t+1 la particule meurt.
  • Si à un instant t une case est occupé par une particule, et qu’elle possède moins de deux voisins, alors à l’instant t+1 la particule meurt.
  • Si à un instant t une case est vide, et qu’elle possède exactement 3 voisins, alors à l’instant t+1 une nouvelle particule nait dans cette case.

Une cellule ne peut donc survivre qu’à la condition d’avoir 2 ou 3 voisins.

Logigramme

La transcription logique de cet algorithme est :

algo-2d

Exemple d’évolution

Un exemple de développement pour une grille est le suivant :

exemple

L’algorithme peut entrainer l’apparition de structure particulière découlant des règles particulières qui le régissent.

3 types de structures principales peuvent être différenciées:

  • Les structures stables sont des ensembles de cellules ayant stoppé toute évolution. Elles sont dans un état stationnaire et n’évoluent plus tant qu’aucun élément perturbateur n’apparaît dans leur voisinage.
  • Les oscillateurs se transforment de manière cyclique, en revêtant plusieurs formes différentes avant de retrouver leur état initial.
  • Les vaisseaux sont des structures capables, après un certain nombre de générations, de produire une copie d’elles-mêmes, mais décalée dans l’univers du jeu.
Algorithmie

Implémentation du jeu de la vie en 3D

Je vous propose de découvrir mon implémentation du jeu de la vie en 3D ainsi que les logigrammes correspondants.

Le code source est disponible ici : https://github.com/76MPaul/Jeu-de-la-vie-3D

Je n’ai malheureusement pas retrouvé le projet originel, seulement un regroupement du code sous un seul fichier (contrainte de l’exercice de l’époque probablement).

Si vous souhaitez uniquement tester le programme : https://github.com/76MPaul/Jeu-de-la-vie-3D/blob/master/jeu%20de%20la%20vie%203D%20v2.rar

Les logigrammes et le détails des algorithmes sont disponibles ici : http://www.paulmagnier.fr/algorithmes-jeu-de-vie-3d/

Vidéo de présentation :

Le programme gère le remplissage aléatoire de la grille, le remplissage manuel, le nombre d’étapes, la taille de la grille et le choix des conditions de vie.

Le remplissage aléatoire de la grille se fait à partir du menu options.

  • L’onglet Nombre de cases concernées gère le nombre de cases maximal affecte par le remplissage autour du centre de du cube. Il doit être compris entre 1 et 100.
  • Par exemple, pour une grille de taille 25, si on choisi 50 en valeur de Nombre de cases concernées, seules les 6 cases de part et d’autres du milieu du cube seront concernées par le remplissage.
  • L’onglet Pourcentages de cases gère le pourcentage de cases qui seront remplies lors du passage de l’algorithme. Il doit être compris entre 1 et 100.
  • Par exemples, pour une grille de taille 25, si on choisi 50 en valeur de Pourcentages de cases, (25*25*25)/2  seront remplies soit 7812.

Le remplissage manuel s’effectue en appuyant sur “S”. Elle se fait en 2 étapes :

  • Le choix de la tranche du cube que l’on vas modifier se fait par clique droit,
  • le choix des cubes dont on veux changer la valeur se fait aussi par clique droit.
  • Le retour à l’étape précédentes se fait par clique gauche.

Le choix des conditions de vie est possibles dans les options. De bases, les conditions sont 3/4/4/4.

  • Les deux premiers chiffres correspondent aux conditions de survie de la cellule. C’est à dire q’une cellule survivras (seras présente à l’étape suivante) si elle est entouré d’un nombre de cellule compris entre 3 et 4. L’ordre de ces conditions importe peu. On peut rentrer les conditions dans l’ordre 3/7 ou 7/3, l’inégalité  3< Nombre de cases alentour <7 seras conservé.
  • Les deux derniers chiffres sont les conditions de naissance d’une cellule. Une cellule naitras d’une case vide si elle est entouré de ConditionVie1 cellules ou ConditionVie2 cellules. L’ordre n’as donc pas non plus d’importance.

Le choix du nombre d’étapes ce fais aussi par le menu option, rentrez un nombres et appuyer sur valider.

Le choix de la taille de la grille ce fais en cliquant sur le bouton Taille Grille dans le menu option. Cinq taille de grille sont proposées. Elle est à 25 par défauts.

Attention,  changer la taille de la grille peut fortement impacter sur les performances du programme.

Screenshots :

Ce diaporama nécessite JavaScript.

Algorithmie

Algorithmes du jeu de la vie en 3D

L’algorithme de base

L’algorithme régissant le jeu de la vie en 3D se rapproche grandement de l’algorithme 2d. Cependant, ils différents par le nombre de cases à vérifier à chaque itérations. L’ajout d’une dimension entraine la vérification de 26 cases au lieu de 8.

Pour des tests sur les réponses de l’algorithme, j’ai décidé d’ajouter la possibilité de modifier les conditions de vie et de mort des cellules.

algorithme

  1. Lors de l’initialisation, l’algorithme copie la grille pour avoir une base de comparaison. La grille copiée servira à la vérification de la valeur des cases et la grille de base sera modifiée par l’algorithme.
  2. L’algorithme vérifie ensuite le tableau case par case
    1. Puis il additionne la valeur des 26 cases avoisinantes si celle-ci existent.
    2. Si la valeur de la case est 1
      1. La cellule ne peut survivre qu’à la condition d’avoir entre Condition 1 et Condition 2 voisines vivantes.
    3. Si la valeur de la case est 0
      1. La cellule morte renait si elle possède exactement Condition vie 1 ou Condition vie 2 voisines vivantes.

La recherche des invariances

La recherche d’invariance de manière manuelle étant longue et fastidieuse, j’ai décidé d’automatiser le processus à l’aide de l’algorithme suivant :

invariances

  1. Copie de la Grille de base. On appellera la grille copié Grille_Test.
  2. Passage dans l’algorithme du jeu de la vie de la Grille de base.
  3. L’algorithme compare ensuite les deux grilles
    1. Si la case (x,y,z) est pleine dans les deux grilles,
      1. alors si la valeur de la case de Grille_Test est inférieure à 4, on incrémente celle-ci.
      2. sinon, on lance l’harmonisation.
    2. Si les cases sont différentes, alors la valeur de la case est mise à 0.
  4. Si une des cases de Grille_Test à pour valeur 4, on lance l’harmonisation, c’est à dire que les seules cases pleines dans la Grille seront celles ayant pour valeur 4 dans la Grille_Test.
  5. Si les cases des deux grilles sont identiques, on incrémente le nombre d’étapes vérifiées. Il est remis à zéro à partir du moment où une différence est enregistrée.
  6. Si le nombre d’étapes vérifiées atteint 4, l’algorithme à trouvée une invariance. Sinon, si cette algorithme à été exécuté 25 fois, alors, on lance le remplissage aléatoire et on recommence.

Pourquoi avoir choisi 4 pour valeur de test dans le dernier algorithme?

  1. L’algorithme test si les cases de la grille change ou pas. Si la valeur d’une case de la grille test est 4, cela signifie que cette case de la grille n’a pas été modifiée pendant 4 étapes. La valeur 1 n’était pas possible, celle-ci correspondant à la valeur d’une case pleine. Il n’est pas rare qu’une case ne change pas d’état durant 2-3-4-5-6 étapes. Alors pourquoi quatre? Les valeurs deux et trois m’ont parus trop faible pour être significative d’une invariance. Comme on recherche des invariances, des valeurs plus élevées semblerait préférable mais le risque que la figure d’invariance soit polluée par l’extension des autres figures, et donc disparaisse, deviens de plus en plus important. La valeur quatre m’as donc parût être un bon compromis d’après les différents tests que j’ai effectué.
  2. Après avoir vérifié quatre fois qu’une partie de la grille ne changeait pas, on isole cette partie en mettant toutes les cases ayant une valeur différente de 4 à 0. On refait ensuite passer cette « nouvelle grille » dans l’algorithme pour vérifier si elle est invariante ou non. Les cases qui ne forment pas une figure d’invariance seront modifiées dès la première étape et donc la valeur vérification restera à zéro. La valeur quatre permet de s’assurer que la figure est bien une figure d’invariance même si une valeur de trois aurait pus fonctionner (pour plus de sureté, j’ai éliminé d’office la valeur 2).
Algorithmie

Mon implémentation du jeu de la vie 2D en…

Je vous propose de découvrir ici ma version du jeu de la vie en deux dimensions.

Il s’agissait d’un exercice d’algorithmie de 2011 afin d’appréhender celui-ci avant de réfléchir à une version 3D de l’algorithme.

Le code source est disponible ici : https://github.com/76MPaul/Jeu-de-la-vie-2D

Si vous souhaitez seulement tester le programme, téléchargez uniquement l’archive .rar : https://github.com/76MPaul/Jeu-de-la-vie-2D/blob/master/jeux%20de%20la%20vie.rar

Screenshots :

jeu-de-la-vie-2d