Ceci est une ancienne révision du document !

~~META:date created=2010-11-15~~ ~~DISCUSSION~~ {{tag>programmation python}} ======Game of life====== Le "jeu de la vie" est un [[wp>Cellular_automaton|automate cellulaire]] simple imaginé par [[http://bitstorm.org/gameoflife|John Conwell]] en 1970. Il est composé d'une grille dont chaque cellule peut être dans deux états : vivante ou morte, modifié au cours du temps selon les trois règles suivantes : - Une cellule vivante ayant moins de deux voisines vivantes meurt de solitude. - Une cellule vivante ayant plus de trois voisines vivantes meurt de surpopulation. - Une cellule morte ayant exactement trois voisines vivantes vit. Les voisines d'une cellule sont les huit cellules l'entourant : N, S, E, O, NE, NO, SE, SO. La programmation de cet automate est très simple, il s'agit généralement de créer et manipuler un tableau de deux dimensions. Ce travail - en python - visait à créer le moteur fonctionnel de l'automate (résultat affiché en console) en moins de lignes possible et le plus optimisé possible. =====Version 2===== //15/11/2010// Cette version utilise au maximum générateurs, listes et diverses syntaxes courtes, et un tableau d'une seule dimension parcouru par une seule boucle associé à une technique d'index relatifs permettant de l'analyser comme une grille en deux dimensions. Le code fait 14 lignes, les trois lignes d'affichage en console comprises. <code python> from random import random l = 500 rnge = range(l*l) nbrs = (1,-1,l,-l,l+1,l-1,-l+1,-l-1) grid = list(int(random()*1.8) for i in rnge) while not raw_input(): last = list(grid) for i in rnge: s = sum(last[i+n] for n in nbrs if 0 < i+n < l*l) if not last[i] and s == 3 : grid[i] = 1 if last[i] and (s < 2 or s > 3): grid[i] = 0 print str(grid[i]), if i+1 and not (i+1)%l: print print </code> ====Variables==== <code python> from random import random </code> Importation du module d'aléatoire utilisé pour remplir initialement la grille. <code python> l = 500 </code> ''l'' définit la largeur (et longueur) de la grille en nombre de cases. Pour être visible sans problème en console, préférer un tableau inférieur à 50x50 cases. Le programme peut toutefois calculer sans problème un tableau de 600x600 cases par exemple (hors affichage). <code python> rnge = range(l*l) </code> Cette liste correspond aux index des cases de la grille et sera utilisée pour la créer et la parcourir. La grille est de taille ''l*l'', afin de correspondre à une grille de deux-dimensions de côté ''l''. Elle est pré-calculée pour une question de performance, cf. [[http://nliautaud.fr/wiki/articles/python_benchmark#while_et_for|python benchmark]]. <code python> nbrs = (1,-1,l,-l,l+1,l-1,-l+1,-l-1) </code> Cette liste décrit les index relatifs des huit voisins (//neighbours//) ramenés au tableau d'une seule dimension. Le processus est détaillé plus bas. ====Initialisation de la grille==== <code python> grid = list(int(random()*1.8) for i in rnge) </code> Il s'agit d'un "générateur de liste" : <code python> list(value for i in range) </code> Proche de syntaxe courte de création de liste : <code python>[value for i in range]</code> Mais préférable pour des questions de performance. Cf. [[http://python.org/dev/peps/pep-0289|Generator Expressions]]. La valeur ajoutée à la liste est une manière d'obtenir aléatoirement soit ''0'' soit ''1'' : convertir en entier la valeur à virgule flottante aléatoire comprise entre ''0'' et ''1'' renvoyée par ''random()''. <code python>int(random()*1.8)</code> ''1.8'' est un "taux de remplissage" de la grille. ====Exécution des cycles==== <code python> while not raw_input(): last = list(grid) # analyse et mise à jour de la grille print </code> Cette boucle permet de mettre à jour la grille en appuyant sur <key>Enter</key>. Pour stopper le programme, entrer n'importe quelle valeur puis appuyer sur <key>Enter</key>. ''last'' est une copie de la grille permettant par la suite l'analyse de la grille dans son état précédent, non modifié, tout en modifiant l'état actuel. Le ''print'' vide inscrit un espace dans la console entre l'affichage de deux cycles. ====Analyse et modification de la grille==== <code python> for i in rnge: </code> On répète l'opération suivante pour chaque élément de ''rnge'', i correspondant alors à l'index des cellules de la grille. ===Somme des voisins=== Pour savoir le nombre de voisins vivants, il faut faire la somme de l'état des huit voisins. <code python> s = sum(last[i+n] for n in nbrs if 0 < i+n < l*l) </code> Il s'agit encore d'un "générateur de liste" créant la liste des états des huit voisins, intégré à la fonction ''sum()'' faisant directement la somme chacun des éléments de la liste. Cette ligne est similaire à : <code python> nbrsList = [] for n in nbrs: if 0 < i+n < l*l: nbrsList.append(last[i+n]) s = sum(nbrsList) </code> On ajoute les index relatifs stockés dans ''nbrs'' à l'index courant ''i'' pour déterminer l'index des voisins ''i+n''. L'état des voisin lors du cycle précédent est alors déterminé par ''last[i+n]''. Par exemple ''nbr[0]'' est ''1'', l'index de ce voisin est ''i+1'' et son état ''last[i+1]'', ce qui correspond à la case suivante du tableau, donc au voisin de droite. Description des index relatifs : * ''1'' : case suivante du tableau, EST. * ''-1'' : case précédente du tableau, OUEST. * ''l'' : case située une longueur de ligne après, SUD. * ''-l'' : case située une longueur de ligne avant, NORD. * ''l+1'' : case située une longueur de ligne plus une case après, SUD-EST. * ''l-1'' : case située une longueur de ligne moins une case après, SUD-OUEST. * ''-l+1'' : case située une longueur de ligne plus une case avant, NORD-EST. * ''-l-1'' : case située une longueur de ligne moins une case avant, NORD-OUEST. ==Bordures== La condition impose que l'index du voisin soit bien dans le tableau (une cellule au bord de la grille va observer des cases qui n'existent pas), c'est à dire que son index soit supérieur à ''0'' et inférieur à la taille du tableau : <code python> if 0 < i+n < l*l </code> La syntaxe ''x < y < z'', peu courante dans d'autres langages, correspond à ''x < y and y < z''. //La technique de la première version de "[[#bordures_mortes|bordure morte]]" n'a pas été réutilisée car elle s'avère peu utile dans un tableau uni-dimensionnel n'ayant que deux bords à vérifier.// ===Modification de la grille=== Les règles énoncées plus haut peuvent être décrites en deux règles générales de changement. <code python> if not last[i] and s == 3 : grid[i] = 1 </code> Si l'état de la cellule courante est ''0'' (morte), mais que la somme des voisins vivants est égal à ''3'', on change son état à ''1'' (vivante). <code python> if last[i] and (s < 2 or s > 3): grid[i] = 0 </code> Si l'état de la cellule courante est ''1'' (vivante), mais que la somme des voisins vivants n'est pas comprise entre ''2'' et ''3'', on change son état à ''0'' (morte). Si la cellule ne correspond pas à ces règles, on ne change pas son état. ===Affichage=== <code python> print str(grid[i]), if i+1 and not (i+1)%l: print </code> On affiche l'état de la cellule courante, et l'on ne va à la ligne que pour les index multiplicateurs de la largeur de la grille afin d'afficher le tableau en deux dimensions.. ====Benchmark==== Le programme s'exécute (hors affichage en console) en ''0.6934'' secondes par cycle (1.67 cycles par seconde) pour une grille de 500x500, soit 250.000 cellules. =====Version 1===== //03/11/2010// Cette version utilise certaines syntaxes courtes et un tableau à deux dimensions. 19 lignes, les trois lignes d'affichage en console comprises. <code python> from random import random l = 500 rng = range(1, l+1) d = (0,1, 0,-1, 1,0, -1,0, 1,1, 1,-1, -1,1, -1,-1) w = [[0]*(l+2)]*(l+2) for i in rng: for j in rng: w[i][j] = int(random()*1.8) for t in range(5): w2 = list(w) for i in rng: for j in rng: sum = 0 for y in range(0,len(d),2): sum += w2[i+d[y]][j+d[y+1]] if w2[i][j] == 0 : if sum == 3 : w[i][j] = 1 elif sum < 2 or sum > 3: w[i][j] = 0 print str(w[i][j]), print print </code> ====Bordures mortes==== Un problème à résoudre pour l'optimisation du code était de trouver un moyen court et efficace d'éviter les cases inexistantes. Lorsqu'une cellule est au bord de la grille, elle n'a pas huit voisins, le processus doit donc s'assurer de ne pas demander l'état de cases en dehors du tableau. Pour éviter l'ajout de conditions, lourdes car à calculer pour chaque case pour chaque cycle et prenant plusieurs lignes, il a été choisi d'ajouter au tableau de côté ''l'' une bordure d'une cellule d'état ''0''. Le tableau réel est donc de côté ''l+2''... <code python>[[0]*(l+2)]*(l+2)</code> ...et le processus de mise à jour et l'affichage ne concerne que les case de ''(1, 1)'' à ''(l, l)'' : <code python>range(1, l+1)</code> Toutes les cellules mises à jour ayant alors bien huit voisines et les bordures n'ayant aucune influence sur le résultat des règles car toujours définies à ''0'', il n'est plus besoin d'ajouter une quelconque condition durant le processus. ====Benchmark==== Cette version s'exécute (hors affichage en console) en ''0.9613'' secondes par cycle (1.04 cycles par seconde) pour une grille de 500x500, soit 250.000 cellules.