Conway's Game of Life

Publié le par Aurélien

Bonjour tout le monde !

Comme mis dans l'edit du post précédent, j'ai codé un algorithme 6 fois plus rapide que celui qu'on trouve traditionnellement concernant le je de la vie de Conway. Le principe est de stocker pour chaque cellule le nombre de voisins en plus de l'état de la cellule, pour ne pas avoir à vérifier le nombre de voisins de chaque cellule, mais que des cellules vivantes / qui ont au moins un voisin. Si l'algorithme vous intéresse, n'hésitez pas à me contacter.

L'étape suivante a été de porter cet algo sur arduino. Cette première version ne tourne que sur un monde de 8*8, faute de RAM. J'attends donc avec impatience mes 2 barrettes de... 32ko de RAM, wahou ! Comme ça je pourrait faire les calculs dans un monde allant jusqu'à sqrt(32k+32k) =  256 * 256. Enfin je me limiterai à 128*128, la résolution de l'écran (si il y a assez de puissance, on pourra voir plus grand par la suite...).

Sinon, pour avoir une idée de la puissance de l'algorithme sur arduino uno/duemilanove ou chipkit uno32, voilà des petits benchmark :

benchmark

Ces chiffres peuvent nous donner une idée de ce que ça donnera en 128*128, même si j'ignore encore le temps que prendra l'affichage et l'accès à la ram externe (tout passe par le protocole SPI).

En comptant 500µs/cycle en 8*8, si on considère que le temps de calcul est proportionnel à la surface, on aurait 500*(128²/8²) = 500*256 = 128ms... soit 8FPS (frame per second) avec un arduino UNO (atmega328), alors qu'avec un chipkit uno 32, on aurait 80FPS (c'est même trop, autour de 12 c'est plus agréable à regarder). De plus l'inconvénient du chipkit est qu'il est beaucoup plus difficile de sortir de microcontroleur de l'environnement de développement (c'est du cms). Une solution éventuelle serait de zommer * 2 pour diminuer la quantité de calculs (par 2²). Un peu dommage...

On remarque que le temps de calcul ne dépend que d'un tiers de la quantité de cellules présentes (partie du graphe qui fluctue entre 500 et 320). C'est à dire que les deux tiers du temps qui sont utilisés même lorsqu'il n'y a pas de cellule correspond au temps passé à parcourir le tableau pour vérifier s'il y a une cellule à updater... une piste pour la recherche de l'optimisation. Voyons voir sur un arduino uno si c'est bien le cas...

benchmark2

On voit bien que la principale composante du temps de calcul est constante, ce qui veut dire que c'est le parcours des tableaux et non les opérations effectuées dessus qui prennent du temps. A moins de trouver un meilleur algorithme, je ne crois pas qu'on puisse réduire cela. Il va donc falloir se contenter d'une simulation un peu lente, ou alors réduire la résolution... Damn it !

Edit : une idée me vient... le plus de temps perdu est dans le parcours des tableaux, qui sera doublé du temps de communication avec la ram externe... dans ce cas, il n'y a qu'à faire un tableau d'indexation (de taille inférieure que tableau des cellules) des zones vides, ou non, qui sera stocké dans la ram interne ! Une sorte de quad tree, quoi ! Question : de quelle taille doit être l'indexation ? On a 2ko de ram en interne, et faut indexer un tableau de 128*128. Un tableau booléen suffit, etant donné qu'on stocke juste zone vide/zone non vide. Mais sur l'Ardrduino les booléen sont stocké sur 8bits (honteux, haha). Donc on va stocker ça en octets, et jongler avec des masques (quel poête). Donc si on découpe en régions de 16 cellules de surface, ça nous fait 128²/16 = 1024 bits pour le tableau d'indexation, soit la moitié de la ram interne. Impeccable. Allez, j'vais coder ça, et on verra les résultats !

...ou pas. Il est facile de marquer une zone "occupée" dès qu'une cellule y apparait, mais lorsqu'une cellule meurt, on ne va pas revérifier toute la zone pour savoir s'il faut la marquer comme vide... Une autre solution serait donc de découper la map en zones de 8 cases (4*2 par exemple) et stocker dans un tableau le nombre de cellules présentes dans la zone. Ainsi, facile de faire +1 ou -1 en fonction de. Mais... il faut aussi compter le fait que si il y a des voisins à la zone, il peut apparaitre des cellules dans celle ci alors qu'elle est vide. Encore une impasse. Je crois pas qu'on puisse faire mieux, étant donné la RAM qu'on a. Sinon il aurait sufit de ça.

Bon, ben reste plus qu'à attendre la ram et voir si c'est potable... on pourra toujours gagner un peu en remplaçant le crystal de l'arduino par un 20Mhz (16Mhz d'origine), mais le gain est faible...

See you soon !

Publié dans Programmation

Commenter cet article