Bon, comme c'est les vacances et que je n'ai pas grand chose à faire, j'ai décidé de me pencher un peu sur les automates cellulaires - comme par exemple le Jeu de la Vie de Conway.

Je trouve que les automates cellulaires sont parfaits car ils ont un côté programmation, un côté algorithmique et un côté ludique non négligeable... Voilà donc de quoi tuer de sérieuses heures.

Alors bien sûr, comme utiliser un programme déjà existant ça n'est pas marrant, j'ai décidé d'implémenter le mien avec mon langage de programmation favori : Java.

Cependant, il y a déjà plein d'automates cellulaires "classiques", optimisés, paramétrables, opensource, bref parfaits. Donc, pour compliquer la tâche, j'ai décidé de choisir un pavage hexagonal au lieu du classique pavage rectangulaire que les programmeurs choisissent la plupart du temps.

Réalisation technique

L'avantage du pavage rectangulaire, c'est qu'on peut exprimer les coordonnées d'une case (un carré dans la majorité des cas) très simplement...

On peut observer alors qu'une cellule possède quatre voisins directs. En général les conditions de survie ou d'apparition de la vie dans une case dépendent du nombre de voisins vivants. La notion de "voisin" ne se limite pas aux cases immédiatement adjacentes (même si c'est comme ça dans la plupart des cas).

Avec un pavage hexagonal, établir un système de coordonnées est déjà plus complexe, même si ça n'est pas impossible.

Comme on peut le voir, cette fois-ci une cellule a six voisins directs. Cela ouvre bien sûr de nouvelles possibilités. Le système de coordonnées que j'ai choisi n'est sans doute pas le meilleur mais il permet de calculer la simulation de façon théorique relativement simplement. En fait, peu importe le système de coordonnées choisi, tant qu'il est possible de donner les coordonnées des voisins d'une cellule à partir de ses coordonnées.

Le problème est d'afficher tout ça d'une façon simple... Autant pour dessiner et colorier des rectangles, c'est simple. Pour des hexagones, c'est déjà un peu plus subtil.

Je me suis inspiré de cet excellent article expliquant comment créer une grille hexagonale en .NET. J'ai repris les grands principes, adapté à ma sauce. Voici le résultat :

Une fois que j'ai pu avoir un résultat visible, j'ai réellement été agréablement surpris au niveau des performances. Avec mon modeste Core2 Duo E6600 standard, je peux générer et afficher environ 20 fois par seconde une carte de plus de 5700 hexagones (en gros tout mon écran avec une résolution de 1680x1050 avec des hexagones ayant pour côté 10 pixels). C'est un résultat convenable et tout à fait suffisant pour un usage "simple", c'est à dire des observations basiques et l'aspect amusant de la chose, mais ça ne suffira évidemment pas à faire de grandes simulations très complexes.

Observations effectuées

Pour la suite de cet article, j'utiliserai la notation Bx/Sy pour définir les règles du jeu utilisées. Il s'agit d'une notation utilisée dans la majorité des programmes, notamment Golly. La notation est très simple à comprendre, surtout à partir d'un example : si la règle est B456/S23, alors une cellule va naître si elle a exactement 4, 5 ou 6 voisins, et elle va survivre si elle a exactement 2 ou 3 voisins.

Règle B34/S34

D'après mes premières estimations, les cellules tendent à disparaître très rapidement en formant beaucoup d'oscillateurs, le plus souvent de période 2, de formes très variées mais suivant toutes le même principe : une « chaîne » de cellules, circulaire ou non, forme le coeur de l'oscillateur et est invariable. Cette chaîne est entourée de cellules espacées en général d'une cellule vide, parfois de deux. Ce sont ces cellules là qui vont osciller, comme si elles "tournaient" autour de la chaîne.

Oscillateurs de période 2 et de longueur de chaîne respectives de 1, 2 et 5.

Il n'y a pas l'air d'avoir de motifs invariables ou de vaisseaux « simples » dans cette configuration.

Règle B34/S234

Cette règle, qui a l'air de ressembler à la précédente, est en réalité très différente.

Les motifs statiques « still life » profusent, énormément de motifs simples sont stables. Lorsqu'il y a beaucoup de cellules, elles ont tendance à former des polygônes stables, de taille très variable, oscillant avec des périodes en général comprises entre 2 et 5. Lorsque les cellules en vie sont présentes en plus grande quantité, elles forment un motif caractéristique, qui possède une capacité d'adaptation extraordinaire.

Ce motif répétable peut s'adapter à un grand nombre de formes, tout en laissant place à plusieurs types d'oscillateurs.

Règle B3/S23

Avec cette règle, éponyme à celle du Jeu de la Vie dans sa version orthogonale, les cellules vont à première vue se stabiliser très rapidement en motifs statiques invariables simples. Les oscillateurs sont rares et n'apparaîssent que très peu comparés aux autres formes statiques.

J'espère que j'ai réussi à vous donner envie de vous intéresser aux automates cellulaires, ils sont vraiment intéressants. Le projet est maintenu et distribué via Github.