Différences

Ci-dessous, les différences entre deux révisions de la page.

--- travaux:game_of_life [2010/11/15 23:13]
nico
+++ travaux:game_of_life [2010/11/16 20:49]
nico
@@ Ligne 1: / Ligne 1: @@
+~~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.
+=====Introduction=====
+La programmation de cet automate est assez simple, il s'agit généralement de créer et manipuler un tableau de deux dimensions.
+Ce travail - en python - vise à créer le moteur fonctionnel de l'automate (et son affichage en console) le plus optimisé possible... en moins de lignes possible.
+=====Source=====
+Ce programme 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 programme crée une grille de taille donnée, la remplit aléatoirement selon un taux de remplissage, la calcule et met à jour selon les règles de l'automate cellulaire puis l'affiche en console (en indiquant chaque cellule vivante par son nombre de voisins) quand l'utilisateur le demande, et permet de quitter le programme simplement.
+Le code fait 13 lignes et 334 caractères.
+<code python>
+from random import random
+l=10
+r=range(l*l)
+n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
+g=list(int(random()*1.8) for i in r)
+while not raw_input():
+  p = list(g)
+  for i in r:
+    s = sum(p[i+x] for x in n if 0<i+x<l*l)
+    if not p[i] and s==3 : g[i]=1
+    if p[i] and (s<2 or s>3): g[i]=0
+    print chr(32+p[i]*(16+s)),
+    if i+1 and not (i+1)%l: print
+</code>
+Appuyer sur <key>Enter</key> pour calculer un cycle, rester appuyé pour calculer en boucle.
+Appuyer sur n'importe quelle touche et appuyer sur <key>Enter</key> pour quitter.
+=====Explication=====
+Je décrit ci-dessous le fonctionnement du programme, ligne par ligne.
+====Préparation des variables====
+<code python>
+from random import random
+</code>
+Importation du module d'aléatoire utilisé pour remplir initialement la grille.
+<code python>
+l=10
+</code>
+''l'' comme **length** : 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>
+r=range(l*l)
+</code>
+''r'' comme **range** : liste des index des cases de la grille 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''.
+Cette liste est pré-calculée pour une question de performance, cf. [[http://nliautaud.fr/wiki/articles/python_benchmark#while_et_for|python benchmark]].
+<code python>
+n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
+</code>
+''n'' comme **neighbours** : Cette liste décrit les index relatifs des huit voisins dans le tableau d'une seule dimension. Le processus est détaillé plus bas.
+====Initialisation de la grille====
+<code python>
+g=list(int(random()*1.8) for i in r)
+</code>
+''g'' comme **grid**.
+Il s'agit d'un générateur de liste utilisant la syntaxe :
+<code python>
+list(value for i in range)
+</code>
+C'est proche de la syntaxe courte de boucle :
+<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 donc un "taux de remplissage" de la grille pouvant être manipulé entre ''0'' (''0*0 < résultat < 0*1'', donc grille toujours vide) et ''1.99'' (''1.99*0 < résultat < 1.99*1'', donc grille aléatoirement remplie).
+====Exécution des cycles====
+<code python>
+while not raw_input():
+  p=list(g)
+</code>
+Cette boucle permet de mettre à jour la grille en appuyant sur <key>Enter</key> (la condition d'exécution est vraie puisque ''raw_input()'' n'a rien renvoyé).
+Pour stopper le programme, entrer n'importe quelle valeur puis appuyer sur <key>Enter</key> (la condition d'exécution est fausse puisque ''raw_input()'' a renvoyé une valeur).
+''p'' comme **previous** 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.
+====Analyse et modification de la grille====
+<code python>
+  for i in r:
+</code>
+On répète l'opération suivante pour chaque élément de ''r'', i correspondant donc tour à tour à l'index de chaque cellule 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(p[i+x] for x in n if 0<i+x<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()'' retournant directement la somme chacun des éléments de la liste.
+Cette ligne est similaire à :
+<code python>
+nbrsList = []
+for x in n:
+  if 0 < i+x < l*l:
+    nbrsList.append(last[i+x])
+s = sum(nbrsList)
+</code>
+On ajoute les index relatifs stockés dans ''n'' à l'index courant ''i'' pour déterminer l'index des voisins ''i+x''. L'état des voisin lors du cycle précédent est alors déterminé par ''last[i+x]''.
+Par exemple ''n[0]'' est ''1'', l'index de ce voisin est ''i+1'' et son état ''p[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+x<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. Mais du coup les bords droite/gauche de la grille sont infinis (un objet sortant à droite réapparaît à gauche).
+===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 p[i] and s==3:g[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 p[i] and(s<2 or s>3):g[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 chr(32+p[i]*(16+s)),
+</code>
+Cette ligne affiche un espace pour les cellules mortes et le nombre de voisins pour les cellules vivantes, en générant le code ASCII en base 10 du caractère visé. Cf. [[wp>ASCII]] et [[http://pyref.infogami.com/chr|chr()]]
+Si la cellule est morte, le calcul sera ''32+0*(16+s)'' donc toujours ''32'', qui est le code ASCII du caractère ''Espace''.
+Si la cellule est vivante, le calcul sera ''32+1*(16+s)'' donc toujours ''48+s''. A ''48'' (le code du chiffre ''0'') est rajouté le nombre de voisins, ce qui donne ''49'' (le code du chiffre ''1''), ''50'' (le code du chiffre ''2''), etc...
+<code python>
+    if i+1 and not(i+1)%l:print
+</code>
+On va à la ligne pour les index multiplicateurs de la largeur de la grille afin d'afficher le tableau en deux dimensions.
+=====Benchmark=====
+Les temps ci-après concernent l'exécution du programme légèrement modifié afin d'indiquer une moyenne (sur 100 cycles) des temps de calcul sans affichage de la grille en console :
+<code python>
+from time import time
+t=time()
+cycles = 100
+from random import random
+l=100
+r=range(l*l)
+n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
+g=list(int(random()*1.8) for i in r)
+for bench in range(cycles):
+  p=list(g)
+  for i in r:
+    s=sum(p[i+x] for x in n if 0<i+x<l*l)
+    if not p[i] and s==3:g[i]=1
+    if p[i] and(s<2 or s>3):g[i]=0
+print str((time()-t) / cycles)
+</code>
+^  Taille  ^  Nombre de cellules  ^  Secondes par cycle  ^  Cycles par seconde  ^
+| ''50''   |       ''5.000''      |      ''0.0068''      |    ''147''      |
+| ''100''  |      ''10.000''      |      ''0.0267''      |    ''37.2''     |
+| ''500''  |      ''250.000''     |      ''0.6934''      |    ''1.67''     |
+| ''600''  |      ''360.000''     |      ''1.0087''      |    ''0.99''     |
+=====Version précédente=====
+Cette version utilise certaines syntaxes courtes, un tableau à deux dimensions et affiche l'état de toutes les cellules un certain nombre de fois.
+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.