La fourmilière

 

La fourmilière fait partie des automates cellulaires a deux dimensions, comme le jeu de la vie. Il s'agit d'observer comment des fourmis sortant d'un trou se répartissent dans leur environnement en obéissant à des lois précises. Cet automate appellé Rotor router a été récemment inventé par Jim Propp(university du Wisconsin). Dans la rubrique "Logique et calcul" du numéro de mai 2005 du mensuel "Pour la science" Jean Paul Delahaye décrit cet automate.


Les lois du Rotor router
Pour bien comprendre, les 15 premières étapes
Les questions que l'on peut se poser
Le principe du programme
Pour utiliser le programme

Le programme et son commentaire
Quelques résultats
Conclusions

Les lois du Rotor router

Les fourmis sortent successivement du même "trou"( case origine), une cellule carrée d'un quadrillage carré infini. Chaque fourmi, en sortant de ce trou, cherche une case libre ou s' installer définitivement. Chaque case du quadrillage a deux caractéristiques :

1) La case est occupée par une fourmi ou ne l'est pas.

2) Chaque case possède une orientation(Ouest,Nord, Est, Sud) qui varie chaque fois qu'une fourmi arrive dans cette case, si elle est occupée par une autre fourmi. Au début du jeu, chaque case est orientée vers l'ouest.

Lorsqu'une fourmi arrive dans une case inocupée, elle s'y installe et n'en bouge plus. Dans le cas contraire, elle modifie l'orientation de la case, en la faisant tourner d'un angle droit dans le sens des aiguilles d'une montre(O-N-E-S-O) puis se dirige vers la case suivante en suivant la nouvelle direction indiquée par la case. Dés que cette fourmi s'est installée définitivement dans une case, une nouvelle fourmi sort du "trou", parcourt un certain nombre de cases puis s'installe à son tour dans la première case libre.

On peut arrêter le processus lorsque 100 fourmis se sont installées, ou bien 1000, ou beaucoup plus , par exemple un million.

Pour bien comprendre, les 15 premières étapes.

Chaque case ci dessous est numérotée en fonction de son orientation : Ouest est codé par 1, Nord par 2, Est par 3, Sud par 4. Les cases définitivement occupées par une fourmi sont colorées en jaune.

Fourmi 1 sort du trou et s'installe dans la première case. Fourmi 2 sort du trou,trouve la case occupée par fourmi1, change l'orientation de la case qui passe au nord. Fourmi 2 se dirige vers le nord, et s'installe dans la case immédiatement au dessus. Fourmi 3 sort du trou, trouve fourmi 1, change l'orientation de la case qui passe à l'Est. Fourmi 3 se dirige vers l'Est,et s'installe dans la première case.
Fourmi 4: elle sort du trou, change l'orientation de cette case qui passe au Sud. Fourmi 4 se dirige donc vers le sud, et trouve immédiatement une case vide. Fourmi 5 sort du trou, change l'orientation de la case qui passe a l'ouest. Fourmi 5 se dirige vers l' ouest , et s'installe dans la case libre. Fourmi6 sort du trou, trouve fourmi1, change l'orientation de la case centrale qui passe au Nord.
Fourmi6 se dirige vers le Nord et trouve Fourmi2. Elle change l'orientation de cette case qui passe au Nord. Fourmi6 poursuit donc en direction du Nord, et s'installe. Fourmi 7 sort du trou, constate que la case est occupée par fourmi1 et change l'orientation de cette case en Est. Fourmi7 se dirige vers l'Est, trouve la case occupée par fourmi3, change l'orientation de cette case qui devient Nord. Fourmi7 se dirige vers le Nord, et trouve une case inoccupée, s'y installe.

Les questions que l'on peut se poser.

Quelle est la forme de la fourmilière obtenue après l'installation d'un certain nombre de fourmis ? Une fourmi peut-elle ne jamais trouver une case libre, en ayant par exemple un parcours bouclé ? Comment varie la longueur des parcours des fourmis ?
Pour répondre à ce genre de questions et à d'autres, la méthode expérimentale semble tout d'abord indiquée, même si certains résultats peuvent être obtenus directement. Aussi, est il utile de modéliser l'installation des fourmis sur un réseau quadrillé, en utilisant un programme informatique. Comme pour le jeu de la vie, on peut utiliser le quadrillage des feuilles d'un tableur comme Excel et faire un programme en visual Basic, qui simule le déplacement et l'installation des fourmis au fur et à mesure de leurs sorties de la case origine.

Le principe du programme

Chaque case a deux caractéristiques, le fait d'être libre ou non, et son orientation. On peut donc coder le statut de chaque case par un couple d'entiers ou alors par un seul entier X de deux chiffres. Le premier chiffre est 0 ou 1, suivant que la case est occupée ou non par une fourmi. Le deuxième chiffre, celui des unités est 1, 2, 3, 4 suivant l'orientation de la case. Si une fourmi s'installe dans une case inoccupée, le nombre qui la code augmente de 10. Si une fourmi arrive dans une case occupée, alors la case change d'orientation et le chiffre des unités augmente de 1 modulo 4. Réciproquement , à l'arrivée dans une case, le nombre qui code cette case livre ses 2 informations et indique alors à la fourmi ce qu'elle doit faire.

Si on est curieux, on peut mettre de nombreux compteurs au milieu du programme. On peut ainsi connaitre pour une fourmi donnée, la longueur de son parcours avant de pouvoir s'installer dans une case. Sur les N premières fourmis on peut repèrer celle qui a eu le plus long trajet (ou le plus court) et quel est la longueur de ce trajet. On peut calculer le nombre de pas total etc etc.

 

Pour utiliser le programme

  Une fois le programme téléchargé, ouvrir le fichier avec Excel puis aller dans le menu Outils-Macro-Macro(cliquer sur le deuxième Macro), une fenêtre s'ouvre, cliquer sur "programme principal" puis sur éxécuter.Il faut s'arranger pour que la case ligne numéro I0, colonne numéro J0 soit au centre de votre écran. Les paramètres I0 et J0 sont tous deux initialisés à 128, mais peuvent être modifiés dans le programme, sous programme initialiser. Le paramètre " maximum" du sous programme d'initialisation est réglé sur 1000. C'est dire que 1000 fourmis vont sortir de la fourmilière et s'installer. Ce paramètre, comme d'autres, peut être modifié en allant directement dans le sous programme "initialiser". Pour celà faire apparaitre le programme en faisant Outils-Macro-Visual Basic editor (ou Alt F11) ou encore Outils-Macro-Macro-modifier. Dans maximum=1000, remplacer 1000 par la valeur désirée. Pour revenir à la feuille de calcul faire à nouveau Alt F11.

Une fois le programme terminé, on peut aller voir les différents compteurs sur la feuille "compteurs". Pour effacer le dessin de la feuille 1, le sélectionner à la souris et blanchir les cases avec le pot de peinture de Excel.

télécharger le programme " fourmilière"

 

Le programme et son commentaire

Dim i, j, I0, J0, n, compteurfourmi, nmax, nmin, ralentissement, nombrepasmaximum, nombrepasminimum, numerochemin As Single
Dim compteurdepas, compteurdebut, nombrepastotal, moyenne, maximum, X, a, b, r As Single
Dim orientation(1 To 255, 1 To 255): Dim Etat(1 To 255, 1 To 255) As Single: Dim nombre(1 To 255, 1 To 255) As Single

Cette partie déclare les variables. Les single sont des entiers. A la troisième ligne sont déclarés des tableaux à deux dimensions, et ces tableaux sont constitués d'entiers.

Sub initialiser()

I0 = 128: J0 = 128: compteurfourmi = 0
For i = I0 - Sqr(n) To I0 + Sqr(n)
For j = J0 - Sqr(n) To J0 + Sqr(n)
Etat(i, j) = 0
nombre(i, j) = 0
Cells(i, j) = ""
Cells(i, j).Interior.ColorIndex = 2
Feuil4.Cells(i, j).Interior.ColorIndex = 2
Feuil4.Cells(i, j) = ""
Feuil2.Cells(i, j) = ""
Feuil3.Cells(i, j) = ""
Next
Next

maximum = 500: nombrepastotal = 0
a = 0: nmax = 0: nmin = 0: nombrepasmaximum = 0: numerochemin = 321: ralentissement = 1:
nombrepasminimum = 1000: compteurdebut = 500

End Sub

Les tableaux Etat, nombre, orientation sont tous initialisés à 0. Les cellules des feuilles 2,3,4 sont vidées de leurs contenus sur les 255 premières lignes et colonnes. Le role du tableau Etat est de donner le statut de la case (i,j)( occupée ou non), pour n'importe quelle case. Si la case (i,j) est occupée, alors Etat(i,j) =1 , sinon 0. Orientation(i,j) prend les valeurs 1,2,3 ou 4 suivant l'orientation de la case (i,j). Nombre(i,j) code à la fois l'Etat et l'orientation de la case (i,j).

I0 et J0 sont les numéros des ligne et colonne de la case origine qui démarre le chemin de chaque fourmi. maximum= 1000 signifie que le programme s'arrêtera lorsque les 1000 premières fourmis sont installées. numerochemin=321 signifie que le dessin du déplacement de la fourmi n°321 s'affichera( sur la feuille 4). compteurdebut = 500 signifie que c'est à partir de la 501ème fourmi que l'on cherche le plus petit chemin.(voir le sous programme suivant). Cette valeur peut être modifiée dans le programme. nombrepasminimum est initialisé avec un grand nombre qui diminue au fur et à mesure que des parcourts de fourmis sont constitués de moins de pas. nombrepasmaximum est initialisé à 0 et augmente au fur et à mesure du passage des fourmis.

Sub nouvellefourmi()

i = I0: j = J0
If nombrepasmaximum < compteurdepas Then
nombrepasmaximum = compteurdepas
nmax = compteurfourmi
End If
If (compteurdepas < nombrepasminimum And compteurfourmi > compteurdebut) Then
nombrepasminimum = compteurdepas
nmin = compteurfourmi
End If
compteurfourmi = compteurfourmi + 1
Feuil1.Cells(67, 53) = compteurfourmi
Feuil4.Cells(115, 115) = compteurfourmi
compteurdepas = 0
End Sub

Lorsque ce sous programme est appellé par le programme principal, c'est qu'une fourmi a trouvé une case libre pour s'installer. Le premier If compare le nombre de pas de la précédente fourmi au nombre de pas maximum qu'une fourmi déjà installée a fait. Ceci pour découvrir parmi toutes les fourmis,à partir de la fourmi n° compteurdebut celle qui a fait le plus grand trajet, et la longueur de ce trajet. Le compteur de fourmi est incrémenté et le compteur de pas remis à 0. Le compteur de fourmi apparait sur la page 1 et sur la page 4.

Sub etatdecellule()
nombre(i, j) = nombre(i, j) + 1
X = Etat(i, j)
a = Int(X / 10): b = X - 10 * a
If a = 0 Then
X = X + 10
Cells(i, j).Value = 0
End If
If a = 1 Then
b = b + 1 - 4 * Int(b / 4)
cette ligne peut être remplacée par : b = 1+Int(4 * Rnd) pour rendre aléatoire la direction de la fourmi(voir § quelques résultats)
X = 10 * a + b
End If
Etat(i, j) = X

End Sub

Quand une fourmi arrive dans la case (i,j), nombre(i,j) qui mesure le nombre de passages sur la case(i,j) est incrémenté. Le nombre X (voir principe du programme) qui code à la fois l'occupation et l'orientation de la case(i,j) est décodé. La variable "a" qui peut prendre les valeurs 0 ou 1 renseigne sur l'occupation de la cellule, et la variable b sur son orientation. Si la case est inoccupée(a=0) , alors la fourmi s'installe et donc la case devient occupée, ce qui se traduit par augmenter X de 10. Si la case est occupée(a=1) alors l'orientation est changée ce qui se traduit pour b par une augmentation de 1 modulo 4. L' avant dernière ligne du sous programme stocke dans Etat(i,j) la nouvelle valeur de X.

Sub fourmiavance()
For f = 1 To ralentissement: Next
orientation(i, j) = b
If b = 1 Then i = i - 1
If b = 2 Then j = j + 1
If b = 3 Then i = i + 1
If b = 4 Then j = j - 1
nombrepastotal = nombrepastotal + 1
r = Sqr((i - I0) * (i - I0) + (j - J0) * (j - J0))
compteurdepas = compteurdepas + 1
moyenne = compteurdepas / (r + 1)

End Sub

Lorsqu'une fourmi arrive sur une case, le programme principal appelle le sous programme etatdecellulepour savoir si la case est occupée ou non. Si la case est occupée le programme principal appelle le sous programme fourmiavance qui va indiquer à la fourmi la direction à prendre. La première boucle for-next permet de ralentir le programme en donnant une valeur à la variable ralentissement (entre 1 et 10^9)dans le sous programme initialiser. Orientation(i,j) prend la valeur b déterminée dans le sous programme etatdecellule. En fonction de la valeur de b, la valeur i du numéro de ligne est incrémentée(direction sud) ou décrémentée(Nord) ou c'est la valeur de j qui est incrémentée(Ouest) ou décrémentée(Est). Différents compteurs sont également modifiés. r est la distance de la fourmi à son point de départ.

Sub couleur()
Feuil1.Cells(i, j).Interior.ColorIndex = b + 3
If compteurfourmi = numerochemin Then
Feuil4.Cells(compteurdepas + 1, 1).Value = i
Feuil4.Cells(compteurdepas + 1, 2).Value = j
Feuil4.Cells(i, j).Value = compteurdepas
For f = 1 To ralentissement: Next
Feuil4.Cells(i, j).Interior.ColorIndex = b + 2
End If
End Sub

Ce sous programme a deux fonctions. La première est de colorer chaque case en fonction de son orientation, ce qui est réalisé par la première ligne qui suit le nom du sous programme. La deuxième fonction est de décrire en feuille 4, le parcours de la fourmi dont le numéro est numerochemin, paramètre à initialiser dans le sous programme d'initialisation. Le parcours de cette fourmi est décrit sur une colonne de la feuille 4, mais également apparait sur cette feuille 4, le parcours en couleur de cette fourmi particulière.

Sub resultats()
n = maximum
For i = -Int(Sqr(maximum)) To Int(Sqr(maximum))
For j = -Int(Sqr(maximum)) To Int(Sqr(maximum))
Feuil2.Cells(i + I0, j + J0).Value = nombre(i + I0, j + J0)
Feuil3.Cells(i + I0, j + J0).Value = orientation(i + I0, j + J0)
Next
Next
End Sub

Ce sous programme est destiné à collecter quelques résultats. Sur la feuille 2, apparait dans chaque case(i,j) , le nombre de passages de fourmis dans cette case. Sur la feuille 3, apparait l'orientation de chaque case après que la dernière fourmi soit installée. Ce renseignement pourrrait être supprimé car il apparait déjà sur la feuille 1, traduit en couleur.

Sub programmeprincipal()
initialiser
While compteurfourmi < maximum Or a = 1
If a = 0 Then
nouvellefourmi
End If
If a = 1 Then fourmiavance

etatdecellule
couleur
Wend
Feuil2.Cells(3, 13) = nombrepastotal 'affichage des variables'
Feuil2.Cells(3, 4) = "nombre de pas total"
Feuil2.Cells(6, 13) = compteurdepas
Feuil2.Cells(6, 4) = "nombre de pas pour cette fourmi"
Feuil2.Cells(9, 13) = moyenne
Feuil2.Cells(9, 4) = "nombre de pas pour cette fourmi/rayon"
Feuil2.Cells(12, 13) = nombrepasmaximum
Feuil2.Cells(12, 4) = "nombre de pas pour le trajet le plus long"
Feuil2.Cells(15, 13) = nmax
Feuil2.Cells(15, 4) = "numéro de la fourmi qui a le plus long trajet"
Feuil2.Cells(18, 13) = nombrepasminimum
Feuil2.Cells(18, 4) = "nombre de pas pour le trajet le plus court"
Feuil2.Cells(21, 13) = nmin
Feuil2.Cells(21, 4) = "numéro de la fourmi qui a le trajet le plus court"
Feuil2.Cells(24, 4) = "rayon"
Feuil2.Cells(24, 13) = r

resultats
End Sub

Voila le programme principal. C'est le programme qu'il faut appeler en premier. Il se charge ensuite lui même d'appeler les autres sous programmes dans l'ordre qu'il faut. Il appelle d'abord le programme initialiser. Ensuite, tant que le compteur de fourmi n'est pas arrivé au maximum ou que a=1( la dernière fourmi sortie n'a pas trouvé de place), si a=0( une case est libre donc une fourmi s'installe)le programme appelle le sous programme nouvellefourmi . Si a=1, la case est occupée et c'est le programme fourmiavance qui est appelée. Ensuite le sous programme ETATDE CELLULE est appelée pour faire évoluer les paramètres de la case(orientation et occupation). Puis c'est le sous programme couleur qui est appelée pour coder l'orientation de chaque cellule par une couleur ce qui a pour effet de rendre le résultat plus beau et spectaculaire. En effet les déplacements de fourmis étant très rapides, on voit des éclairs de couleur apparaitre dans tous les sens.

Ensuite viennent une suite de résultats affichés en feuille2.

Quelques résultats

On observe que la forme de la fourmilière se rapproche de celle d'un disque, de plus en plus parfait au fur et à mesure que le nombre de fourmis installées grandit. Une explication intuitive pourrait-être : Aucune direction ne semblant être privilégiée, il est naturel que les fourmis se dirigent dans toutes les directions avec une égale probabilité, ce qui conduit à la fabrication d'une fourmillière en forme de disque. ce raisonnement vaut ce qu'il vaut. Pour vérifier cette intuition on peut étudier la forme obtenue de la fourmillière en changeant la règle concernant le changement d'orientation des cases. Par exemple, on peut rendre aléatoire la détermination de cette orientation en remplaçant par exemple la ligne : b = b + 1 - 4 * Int(b / 4) du sous programme etatdecellule par la ligne b = 1+Int(4 * Rnd). Le programme n'est alors plus déterministe, 2 éxécutions de programme donnera 2 résultats différents. Cependant, comme dans le cas du programme déterministe, aucune direction n'est privilégiée. On constate alors que la forme de la fourmilière se rapproche aussi de celle d'un disque mais néanmoins beaucoup moins parfait, plus ébréché que dans le cas déterministe. Il semble qu'il y ait un effet de frontière à analyser.

Le nombre de pas de chaque fourmi avant installation dans une case libre est très variable. Voici quelques résultats sur le nombre de pas maximum ou minimum observé, par tranche de 1000 fourmis.
  n° de fourmi pour le chemin le plus court nombre de pas n° de fourmi pour le chemin le plus long nombre de pas
1000 premières fourmis 1 1 968 2264
1001 à 2000 1018 45 1532 5722

2001 à 3000

2290 115 2468 10487
3001 à 4000 3822 148 3912 10914
4001 à 5000 4634 174 4880 18027
5001 à 10000 6714 200 9964 47894

Quand à la question posée plus haut concernant d'éventuel parcours bouclé et périodique, il semble que celà soit impossible. En effet si un tel parcours existait, celà signifierait que la fourmi passerait plusieurs fois par la même case et se dirigerait à chaque fois dans la même direction. Or ceci est impossible puisque, entre deux passages successifs sur la même case, la case a changé son orientation.

Conclusion

De multiples questions peuvent apparaitre lorqu'on observe cet automate cellulaire. Le Rotor router a déjà fait l'objet d'une thèse et des compléments peuvent être trouvés sur la toile en tapant Rotor Router dans un moteur de recherche. Le programme présenté plus haut est simplifiable mais aussi étoffable si on veut y adjoindre d'autres instruments de mesure que les compteurs déjà existants. Chacun peut alors personnaliser le programme ou le rendre plus convivial.
Toute coopération pour des remarques ou des compléments sur cette page est la bienvenue.


Pour toutes remarques concernant cette page, écrire à Philippe Bondon.