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 1680×1050 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.

Freenet est un réseau anonyme et chiffré qui est basé sur Internet. Il a été créé par Ian Clarke, est distribué sous licence GPL et est maintenu par beaucoup de développeurs bénévoles ainsi qu’un développeur à plein temps, payé grâce aux donations. Le but principal est de prôner la liberté d’expression et de rendre toute censure impossible. C’est pourquoi, par exemple, il est impossible de supprimer du contenu de Freenet une fois qu’il a été inséré dans le réseau. De même, chaque noeud (un noeud est un ordinateur faisant tourner Freenet) n’a aucun moyen de savoir ce qui transite et ce qui est stocké dans le disque dur.

De façon plus pratique, Freenet permet d’insérer des Freesites, un ensemble de pages xHTML formant un site anonyme ou non, d’effectuer du partage de fichiers, de consulter des groupes de discussion et de s’envoyer des Freemails (système d’e-mail basé sur le réseau Freenet).

Freenet est surtout connu pour avoir soulevé de nombreux débats éthiques, du fait de l’absence totale de censure. Cependant, si vous tenez à conserver un réseau où vous serez sûr que personne ne pourra vous enlever votre liberté d’expression, alors Freenet devrait vous intéresser, surtout avec les projets de loi récents visant à filtrer Internet en France (LOPPSI). Le réseau est vraiment conçu pour ça, les développeurs eux-mêmes ne pouvant arrêter le réseau, même sous pression juridique.

Un historique proche relativement chargé

Il y a quelques mois, ce projet a bien failli ne pas continuer d’exister, et ceci pour plusieurs raisons.

Tout d’abord, le bénévole chargé de l’administration du serveur principal hébergeant le serveur SVN a décidé qu’il ne pouvait plus continuer. Or, personne d’autre n’avait les compétences nécessaires et la confiance nécessaire pour le remplacer. Pour pallier cela, les sources ont été déplacées sur GitHub. Ce choix est discutable, GitHub pourrait facilement décider d’arrêter d’héberger les sources de Freenet à cause de problèmes légaux ! Finalement, git permet assez facilement de s’adapter à ce cas de situation et donc cette éventualité ne causerait pas la mort du projet.

Vu que le projet n’est alimenté en argent que par les dons et qu’un développeur est payé à plein temps, l’argent a commencé à manquer de façon très sérieuse. C’est aussi pour cette raison que le serveur principal a été coupé suite à l’abandon du bénévole chargé de son administration, il représentait un coût non négligeable. Pour donner un indice, le projet a survécu avec moins de 1000$ en réserve pendant plusieurs mois.

Finalement, à la surprise de tous, Google a versé une importante donation de 18 000$ au projet au début du mois de mai. La survie du projet n’est donc plus un problème à moyen terme. Pour rappel, Google a joué un rôle important pour le projet, notamment grâce aux Google Summer of Code (GSoC).

Les nouveautés de la version 0.7.5

La version précédente, 0.7, datait de mai 2008. Mais cela ne veut pas dire qu’aucune nouveauté n’est apparue depuis plus d’un an. Le fonctionnement de Freenet est un peu particulier au niveau des versions. Le noeud se met à jour lui-même (en général de façon automatique) via le réseau Freenet ; le numéro de version est donc une notation symbolique pour mettre en évidence les nouveautés des précédents builds. Les développeurs n’attendent pas de date précise pour ajouter de nouvelles fonctions, ils le font lorsqu’ils jugent de façon arbitraire qu’il y en a eu suffisamment pour changer le numéro de version.

Depuis la version 0.7, de très grosses nouveautés ont été implémentées. Voici un résumé non exhaustif des plus significatives.

Résultat de plus d’un an de travail acharné, l’intégration de db4o (Database for Objects) a permis d’augmenter très grandement la performance et de réduire les ressources utilisées par le noeud. Il est par exemple possible de télécharger plusieurs gigaoctets de fichiers sans pour autant observer une augmentation de la quantité de mémoire vive utilisée. Un noeud typique consommera maintenant entre 100 et 250 mégaoctets de mémoire vive, pas plus. Grâce à db4o, on peut maintenant faire des petits serveurs dédiés Freenet en réutilisant du vieux matériel, ou bien avec du matériel miniature. Cela laisse de belles perspectives pour l’avenir : Freenet sur de l’embarqué.

L’interface web de Freenet (FProxy) a été améliorée afin de la rendre beaucoup plus accessible aux néophytes. De nouveaux installeurs ont été mis au point afin de rendre l’installation plus simple, et de renforcer la compatibilité avec Windows Vista.

Enfin, la majorité du système de plugins a été refondue en profondeur. Cela permettra par exemple d’avoir des dépendances inter-plugins, ou encore leur mise à jour automatique. C’est une modification peu importante pour l’utilisateur, mais c’est une brique nécessaire à l’achèvement de la prochaine “grosse” version de Freenet, la 0.8.

Qu’attendre à court/moyen terme ?

Freenet 0.8 comportera Freetalk/WoT, un nouveau système officiel pour communiquer avec les autres utilisateurs. Annoncé depuis longtemps comme révolutionnaire, tout le monde l’attend avec impatience. Étant donné que Freenet est un réseau entièrement décentralisé, ce système se basera sur une technique de “Toile de confiance” (Web of Trust). En gros, vous devez noter votre confiance envers les autres utilisateurs, afin de rendre impossible toute tentative de spam. Les autres utilisateurs vous notent également. Il paraît évident que les identités ayant de très mauvaises notes seront ignorées des autres, et ne pourront donc plus communiquer. C’est un système de filtrage décentralisé et « démocratique » en quelque sorte : chacun a son mot à dire, et le système se régule de lui-même.

Un nouveau type de clé sera aussi créé : les MHKs (Multiple not Duplicated Hash Key) serviront à partager de gros fichiers plus efficacement qu’à l’heure actuelle. Le fonctionnement est complexe, mais globalement, les blocs d’index seront insérés avec plus de redondance afin d’éviter la perte prématurée de données.

Enfin, les noeuds pourront aussi partager leur bloom filter avec leurs voisins immédiats. Cela signifie que votre noeud “saura” ce que stocke chacun de ses voisins, ce qui représentera un gain important de performances. En revanche, l’implémentation d’un tel système est très délicate, et il faudra donc être patient.

Le mot final

Cette avancée symbolique de Freenet a bien sûr pour but d’attirer plus d’utilisateurs, mais aussi de faire connaître Freenet aux internautes du monde entier : Freenet est indétectable de l’extérieur si utilisé en mode Darknet (en se connectant uniquement à des amis à proximité de confiance), et il faut donc au moins savoir que des solutions existent pour pallier la tendance qu’ont les gouvernements à filtrer le web, ou à envisager de le faire, tout au moins. Freenet est tout de même utilisable si on ne connaît personne qui l’utilise : le mode Opennet vous connectera à des inconnus (la seule différence par rapport au Darknet, c’est qu’on peut savoir que vous utilisez Freenet. Mais comme il n’est pas encore illégal en France, ça ne pose aucun problème).

Enfin, Freenet étant développé entièrement en Java, il est compatible avec n’importe quel système d’exploitation disposant d’une JVM version 1.5 au minimum. Cela inclut Windows, Mac OS, GNU/Linux, FreeBSD, Solaris, …

(Publication originale ici, rédigée par moi-même.)