Discussion :

[luffy27]

Bonjour a tous,
Quelqu'un peut - il m'aider concernant la compréhension de l'algorithme HashLife développé par Bill Gosper car j'aimerais l'implémenter en java pour l'optimisation d'un jeu de la vie en 3D

merci d'avance ...

[HashMike]

Bonjour,
J'ai développé hashlife en C en 2008 et je suis parti de l'article suivant qui explique bien les bases de l'algo
http://www.drdobbs.com/java/184406478
Par contre en 3D ça risque de compliquer encore l'implémentation...
Bon courage!
Michel

[luffy27]

merci d'avoir répondu même si l'intérêt de mon post était que l'on puisse m'expliquer ce que je ne comprends pas, hors le lien que tu fournis je l'ai déjà retourné dans tous les sens et ce sans succès ....

C'est comme qui dirait " trop " compliqué !

[HashMike]

Je veux bien essayer de répondre à tes questions en puisant dans mes souvenirs et dans mon code, après tout dépend si tu veux une présentation globale du concept ou si tu as besoin d'éclaircissements plus précis... Le principe théorique n'est pas si compliqué que cela (mais tout simplement génial, merci Bill Gosper), l'implémentation l'est plus et perso m'a pris pas mal de temps pour avoir qq chose qui fonctionne (prise en compte de différents formats en entrée, hashtable, garbage collector, etc)...

[luffy27]

En fait afin de pouvoir implémenter il faut tt dabord que je puisse comprendre le concept de l'utilisation de hashlife ...
En gros ce que j'ai compris c'est que l'algorithme utilise un quadtree pour représenter l'univers, qu'il sépare chaque noeud pour les traités de façon récursive et qu'il mémorise grace a la table de hachage des générations en cache pour augmenter la vitesse de traitement.

Dis comme ca même ca me parait ultra-flou !

Je ne saisi pas le principe d'utilité du quadtree, son fonctionnement , les notions de noeuds , de feuilles et de niveau et surtout je ne comprend pas donc l'aspect global de l'algorithme en gros comment il fonctionne , meme si je crois en avoir décrit un principe assez réaliste...

Bref j'pédale dans la choucroute

[HashMike]

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

[luffy27]

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

Déja merci pour ton explication déja la partie précèdent ce que j'ai quoté m'est maintenant clair par contre, je ne comprends pas le principe de base , l'histoire du noeud central, je veux bien que tu me ré-explique si possible d'une façon plus simple ou différente cette partie si possible étayer d'un exemple schématique enfin visuel qui me permettrait de voir l'intérêt du truc, parce que sur le site de drdobbs.com il y a l'exemple de décomposition du quadtree de niveau 2 avec 4 noeud de niveau 1 et 16 feuilles de niveau 0 par contre je ne comprends pas l'explication avec la 2îème génération q2->NE = Q1->NE->SW etc...

Donc j'attends impatiemment la suite et puis qui sait une fois que j'aurais compris j'aurais plus qu'a tenter l'implémentation en 3D ^^ mais ca m'a l'air encore plus complexe ...

[luffy27]

Finalement on est tombé d'accord pour le faire en formalisme Life avec un algo simple de caractéristiques birth et survive du coup j'ferais pas de Hlife : ouf quelquepart ^^ !!

En tout cas merci beaucoup pour tout et j'me pencherais dessus je pense a nouveau mais pas de suite !!

[HashMike]

Merci pour l'info, et bon courage pour le dev. Implémenter HashLife directement en 3D ça aurait vraiment été du sport, à ma connaissance d'ailleurs je ne pense pas que quelqu'un l'ait encore fait

[chlab]

Bonjour, j'aimerai beaucoup faire revivre ce sujet de discussion !
Pour un projet d'info, il faut que je code un jeu de la vie (ça devrait aller pour ça ) mais du coup je m'interesse à l'algorithme de hashlife.

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

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).

merci beaucoup !!
chlab