tondeurh

Hello,

Grâce aux automates cellulaires, en 1986, Langton Chris à montré que quelques règles élémentaires simples peuvent conduire à des comportements émergents assez inattendus.

Et certains attracteurs, bien que n'étant pas "étranges" sont toutefois étonnants.

La fourmi de Langton est un automate cellulaire dont l'évolution semble régie par un attracteur.

Les règles de la fourmi de Langton sont simples:
Prenez une grille infinie (dans tes rêves sur ton PC) remplie de cases blanches(ou noires) avec une fourmi sur l'une des cases.
A chaque itération, on applique les règles suivantes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
    Si la fourmi se trouve sur une case colorée, elle tourne à gauche et avance d'une case; la case qu'elle quitte change de couleur et devient blanche(vide).
    Si la fourmi se trouve sur une case vide elle tourne à droite et avance d'une case; la case qu'elle quitte change de couleur et devient colorée.

nb: Il fut un temps, cela se pratiquai en noir & blanc, pour ma part je suis passé à la couleur, il existe des variantes multicolore avec une seule fourmi.

Après un démarrage chaotique, et quelle que soit la configuration de grille initiale, la fourmi finit toujours par construire une autoroute: Au bout d'environ 10 000 itérations, la fourmi construit toujours le même motif qui forme une "route".

Il semblerait que cette route soit un attracteur de la fourmi de Langton (a ce que j'ai pu en lire).
Les quelques règles de base du niveau élémentaire ne permettent pas de prédire ce comportement émergent à l'échelle macroscopique.

L’autoroute est en fait un motif périodique de 104 pas qui se répète, et conduit au tracé que vous observez. Personne ne comprend pourquoi elle apparaît et comment elle peut émerger du désordre qui caractérise la phase chaotique.

Ce qu’il y a de plus perturbant, c’est que même si on part d’une grille dont les cases sont coloriées aléatoirement, l’autoroute finit toujours par apparaître un jour ou l’autre.

C’est encore un problème ouvert de démontrer que quelle que soit la configuration initiale, une autoroute apparaît (à moins de chercher un contre-exemple).

Toutefois un pas intéressant a été franchi : il à été démontré que la trajectoire de la fourmi est toujours non-bornée. C’est à dire que la fourmi finit toujours son parcours à l’infini…

Parmi les autres variétés d'automates cellulaires, on trouve les vers de Paterson. (Je cite ce turmite simplement parce qu'il est vraiment superbe à voir évoluer dans son espace triangulaire.

Mais l'automate cellulaire le plus fascinant est le jeu de la vie (ceci est une autre histoire).

Je vous propose les codes sources d'une application d'un simulateur des fourmis de Langton (je sais il y en a des millions et tout ceci n'est pas nouveau!), cette application à été écrite en Java avec le Gui JavaFX (toujours aussi excellent!) et NetBeans évidemment (excellent éditeur que je vous conseille au passage).
Les codes sources se trouvent sur le gibHub à l'adresse suivante https://github.com/tondeur-h/LangTonAnt
Pour ceux qui veulent pas s’embête à recompiler les sources, ils peuvent télécharger le fichier JAR à l'adresse suivante : http://tondeurh.fr/software/LangTonAnt.jar

Pour les profanes du Java : double cliquer sur ce fichier ou lancer une console DOS (bof) / Linux (yes!) et exécutez la commande :
java -jar LangTonAnt.jar

Que propose cette application ?
Au delà d'un simulateur qui propose de faire évoluer 4 fourmis simultanément auquel vous pouvez affecter une position/direction de départ et une couleur personnalisé.
Vous pouvez grâce au bouton "random simulation" choisir ces valeurs au hasard (et il parait qu'il fait bien les choses!).
Une fois toutes ces valeurs affectés, un clic sur le bouton "Run" et il n'y a plus qu'a regarder le spectacle de ces fourmis qui vont se battre pour occuper l'espace vide et construire des autoroutes.

L'intérêt est aussi de consulter les sources, et de voir comment fonctionne la classe Task (une Thread lance cette tâche) qui permet à la fois de faire l'ensemble des calculs, mais aussi de permettre l'affichage de l'image du déplacement des fourmis sur notre écran, avec une mise à jour constantes de certaines valeurs comme le nombre de cellules occupés par nos fourmis en temps réel (grâce à la mise en place d'un Listener sur l'objet Task "task.messageProperty().addListener").

Cela donne des images assez sympa parfois, un petit exemple ci dessous :


A j'oubliai, si vous voulez sauvegarder des images de vos simulation le bouton "Save Image" est fait pour cela.. Au format png et dans le dossier d'installation de votre application.

Et vous pouvez toujours m'envoyer vos superbes productions...

Les sources sont à vous,

Pour en savoir beaucoup plus sur les fourmis de Langton, lisez cette thèse de 2001 au moins les 30 premières pages:
Influence du réseau spatial sur le comportement d'un système dynamique : la fourmi de Langton.
By: Anahi GAJARDO-SCHULZ
Number: PhD2001-02
Date: June 2001
http://www.ens-lyon.fr/LIP/Pub/PhD2001.php

Merci JavaFx, Netbeans, Wikipédia et DuckDuckGo!