Bonjour, j'aimerai faire revivre un sujet qui s'est fini bien trop tôt !

Il s'agit d'un sujet à propos de l'algorithme hashlife : la discussion que j'ai lu est sur cette page, mais elle est marquée résolue, alors je la relance.

Du coup je remet le dernier post :
Citation Envoyé par HashMike Voir le message
Dans l'article sur DrDobbs, le coeur de l'algorithme qui va être transcrit dans la fonction récursive est décrit dans la figure 4: http://www.drdobbs.com/showArticle.j...dj0604b&pgno=6.
La structure quadtree est un noeud d'arbre à 4 branches: NE, NO, SE, SW.
Chaque branche est à son tour un noeud, ou une feuille quand on arrive au "bout de l'arbre". Dans le jeu de la vie, la feuille représente une cellule de l'univers.
Pour ce qui est des niveaux, considérons que la feuille est au niveau 0. Le niveau 1 sera donc un quadtree de 4 feuilles (donc 2x2 cellules de l'univers), Le niveau 2 un quadtree de 4 noeuds de niveau 1 (4x4 cellules), etc...
Initialement, on doit donc construire le quadtree a partir du pattern en entrée, la racine du quadtree sera à un niveau variable suivant sa taille.
Le principe de base de l'algorithme est de calculer la 2^nième génération de la partie centrale d'un quadtree Q1 au niveau n qui est lui même un quadtree Q2 de niveau n-1 composé de:
Q2->NE = Q1->NE->SO
Q2->NO = Q1->NO->SE
Q2->SE = Q1->SE->NO
Q2->SO = Q1->SO->NE
C'est pour cela que le quadtree est la structure idéale pour implémenter l'algorithme hashlife, on composera toujours le noeud central au niveau n-1 à partir d'un ensemble de 4 noeuds au niveau n-2 d'un noeud au niveau n... Si tu me suis toujours je continue dans un prochain post
personnellement, Je viens juste de comprendre la dernière phrase de Hashmike (après beaucoup de temps de réflexion néanmois ) et j'aimerai comprendre la suite !
Notamment pourquoi calculer la 2kième génération de la partie centrale d'un noeud de niveau n? (sur wikipedia ils parlent de calculer la 2n-2ième génération).
Et la structure est-elle vraiment un quadtree ? (parceque on découpe bien en 4 zones, mais finalement c'est la zone centrale qui est interressante ?)

merci beaucoup !!
chlab