La fourmi de Langton est un automate simple qui fonctionne dans une grille en 2D.
Chaque case de la grille peut être soit blanche, soit noire, et une fourmi est posée sur une de ces cases.
La fourmi va réagir différemment en fonction de la couleur de la cellule où elle est.
Ici, sur une case noire, elle va tourner à gauche.
Puis elle va changer la couleur de la case.
Et finalement elle va avancer jusqu'à la case suivante.
Si la fourmi démarre sur une case blanche, elle exécutera les mêmes actions, mais elle tournera vers la droite au
lieu de la gauche.
Pour la grille, on va simplement utiliser l'écran lui-même.
Chaque pixel représentera une case, et sa couleur sera noire ou blanche en fonction des règles.
On va commencer par initialiser l'écran et le remplir de pixels noirs.
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define BLACK Color(0, 0, 0)
#define WHITE Color(255, 255, 255)
int main(int argc, char* argv[])
{
// init the window
gfx.init("Langton's ant", SCREEN_WIDTH, SCREEN_HEIGHT);
gfx.init2D();
gfx.clearScreen(BLACK);
Ensuite, pour la fourmi, on aura besoin de sa position en x et en y et de sa direction.
Pour la direction on va utiliser un entier qui pourra prendre les valeurs suivantes:
- 0: la fourmi est tournée vers le haut
- 1: la fourmi est tournée vers la droite
- 2: la fourmi est tournée vers le bas
- 3: la fourmi est tournée vers la gauche
De cette façon, si on veut tourner la fourmi de 90 degrés vers la droite, on a juste à ajouter 1 à cette valeur,
et bien sur, pour tourner à gauche, on va soustraire 1.
Il faudra juste qu'on fasse attention aux cas limites comme soustraire 1 quand la valeur est 0, mais on verra ça
plus tard.
int x = SCREEN_WIDTH / 2;
int y = SCREEN_HEIGHT / 2;
int dir = 0; // direction 0=up, 1=right, 2=down, 3=left
Ensuite, dans notre boucle principale, on teste si la fourmi est à l'intérieur de l'écran
// wait till the end
while (sys.isQuitRequested() == false)
{
// if we are on the screen
if (x >= 0 && x < SCREEN_WIDTH &&
y >= 0 && y < SCREEN_HEIGHT)
{
On récupère la couleur du pixel où est la fourmi
// get current color
Color c = gfx.getPixel(x, y);
On teste cette valeur pour tourner la fourmi et on change la couleur du pixel.
// turn and change color
if (c.argb == BLACK.argb)
{
dir = (dir - 1 + 4) % 4; // turn left
gfx.setPixel(x, y, WHITE);
}
else
{
dir = (dir + 1) % 4; // turn right
gfx.setPixel(x, y, BLACK);
}
Remarquez que pour les rotations on prend un modulo 4, parce que l'on veut une valeur entre 0 et 3.
Dans le cas où on tourne à droite, quand dir = 3, si on ajoute 1, on obtient 4, mais à cause du modulo, cette valeur
devient 0.
Dans le cas où on tourne à gauche, si dir = 0, on a un problème, parce que si on veut soustraire 1, on obtient -1.
En fonction du langage que vous utilisez, le modulo d'un nombre négatif ne donnera peut-être pas le même résultat,
et je ne sais même pas ce que ça devrait donner en C.
Alors pour éviter les problèmes, j'ai ajouté 4. Comme on prend le modulo, ajouter 4 ne change pas la valeur du
résultat.
Maintenant que notre fourmi a tourné, on va la faire avancer. Ici, on teste simplement chaque cas.
// move forward
if (dir == 0)
{
y--; // up
}
else if (dir == 1)
{
x++; // right
}
else if (dir == 2)
{
y++; // down
}
else
{
x--; // left
}
}
Et on termine la boucle principale
sys.processEvents();
gfx.render();
sys.wait(2);
}
gfx.quit();
return EXIT_SUCCESS;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Regardons ce qui se passe quand on lance ce programme.
Au début la fourmi semble de déplacer aléatoirement en dessinant un motif complexe.
Puis, à un certain point, elle commence à répéter le même motif, dessinant une ligne qui continue indéfiniment.
On appelle ça une autoroute (on verra pourquoi plus tard).
Cet automate semble toujours finir par construire une autoroute quand il trouve une zone pleine de blanc ou de
noir.
Et vous pouvez modifier ce programme pour ajouter des pixels blancs au centre de l'écran. Quel que soit le motif
que vous utiliserez, tôt ou tard la fourmi s'échappera de cette zone et construira son autoroute.
C'est assez inattendu pour une chose avec des règles aussi simples, mais il semble que quelles que soient les
conditions initiales, la fourmi arrive à "ordonner" les pixels jusqu'à ce qu'elle atteigne une configuration où
elle peut construire son autoroute.
Maintenant regardons ce qui se passe si on a plus d'une fourmi.
On va utiliser des tableaux pour les variables x, y et dir et chaque fourmi aura une couleur différente.
int x[10];
int y[10];
int dir[10];
Color col[10];
On initialise ces valeurs aléatoirement.
srand(time(NULL));
for (int i = 0; i < 10; ++i)
{
x[i] = rand() % SCREEN_WIDTH;
y[i] = rand() % SCREEN_HEIGHT;
dir[i] = rand() % 4;
col[i] = Color(rand() & 0xff, rand() & 0xff, rand() & 0xff);
}
Et on les traite dans la boucle principale.
while (sys.isQuitRequested() == false)
{
for (int i = 0; i < 10; ++i)
lang(x[i], y[i], dir[i], col[i]);
sys.processEvents();
gfx.render();
sys.wait(2);
}
La fonction lang() contient le code qu'on a déjà vu avec seulement une petite modification pour la couleur.
void lang(int &x, int &y, int &dir, Color& col)
{
// if we are on the screen
if (x >= 0 && x < SCREEN_WIDTH &&
y >= 0 && y < SCREEN_HEIGHT)
{
// get current color
Color c = gfx.getPixel(x, y);
// turn and change color
if (c.argb == BLACK.argb)
{
dir = (dir - 1 + 4) % 4; // turn left
gfx.setPixel(x, y, col);
}
else
{
dir = (dir + 1) % 4; // turn right
gfx.setPixel(x, y, BLACK);
}
// move forward
if (dir == 0)
{
y--; // up
}
else if (dir == 1)
{
x++; // right
}
else if (dir == 2)
{
y++; // down
}
else
{
x--; // left
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Si vous lancez ce programme plusieurs fois, vous verrez des comportements intéressants.
Alors que la plupart des fourmis atteignent rapidement le bord de l'écran et s'arrêtent, parfois les interactions
entre 2 fourmis les font entrer dans un cycle complexe et elle ne s'échappent jamais de l'écran.
Après avoir touché les pixels d'une autre fourmi, certaines fourmis vont décider de se retourner et de défaire tous
les pixels qu'elles ont dessiné.
Et quand une fourmi rencontre une autoroute tracée par une autre fourmi, la plupart du temps elle va la suivre à
grande vitesse.
C'est probablement de là que vient le nom "autoroute".
Jusqu'à maintenant on a seulement joué avec des fourmis qui vivent dans un monde qui ne peut prendre que 2
couleurs. Mais peut-on ajouter plus de couleurs à cet automate ?
D'abord souvenons nous que les actions des fourmis sont liées aux couleurs.
On avait 2 couleurs (noir ou blanc) et la fourmi avait 2 actions (tourner à gauche ou tourner à droite).
Si on garde ces 2 actions, on peut définir le comportement de la fourmi quand on a plus de couleurs avec une chaîne
de caractères.
On va utilisere la lettre "L" pour gauche (left en anglais) et "R" pour droite (right en anglais).
Par exemple la chaîne "RLR" définira les règles pour une fourmi avec 3 couleurs. la première lettre donne l'action
quand la fourmi est sur un pixel de couleur 0, la deuxième lettre pour la couleur 1, et la troisième pour la
couleur 2.
Alors on va avoir une règle qui définit le nombre de couleurs de l'automate.
char rule[] = "RLR";
int nbColors = strlen(rule);
On va utiliser une palette pour ces couleurs. Elle sera initialisée avec des couleurs aléatoires à part la couleur
0 qui sera noire.
Color* palette;
// init palette
srand(time(NULL));
palette = new Color[nbColors];
palette[0] = Color(0, 0, 0);
for (int i = 1; i < nbColors; i++)
{
palette[i] = Color(rand() % 256,
rand() % 256,
rand() % 256);
}
Comme ça ne serait pas facile de retrouver le numéro d'une couleur à partir de sa valeur RVB comme on le faisait
avec le blanc et le noir, on va stocker ces numéros dans un tableau qui sera initialisé avec des 0.
int world[SCREEN_WIDTH][SCREEN_HEIGHT];
// init world
for (int yy = 0; yy < SCREEN_HEIGHT; yy++)
for (int xx = 0; xx < SCREEN_WIDTH; xx++)
world[xx][yy] = 0;
Ensuite, dans la boucle principale, on va d'abord récupérer la couleur où la fourmi est
// wait till the end
while (sys.isQuitRequested() == false)
{
// if we are on the screen
if (x >= 0 && x < SCREEN_WIDTH &&
y >= 0 && y < SCREEN_HEIGHT)
{
// get current color
int c = world[x][y];
On décide de tourner à gauche ou à droite en fonction de la lettre de la règle qui correspond à cette couleur:
// turn
if (rule[c] == 'R')
{
dir = (dir + 1) % 4; // turn right
}
else
{
dir = (dir - 1 + 4) % 4; // turn left
}
Pour changer la couleur de la case, dans le monde bicolore on transformait une cellule noire en blanche et vice
versa.
Maintenant on va mettre la case à la couleur suivante dans la palette.
// change color
c = (c + 1) % nbColors;
world[x][y] = c;
gfx.setPixel(x, y, palette[c]);
Et on avance...
// move forward
if (dir == 0)
{
y--; // up
}
else if (dir == 1)
{
x++; // right
}
else if (dir == 2)
{
y++; // down
}
else
{
x--; // left
}
}
Download source code
Download executable for Windows
Comme les fourmis sont plus complexes maintenant, on va obtenir différents résultats en fonction de la règle qu'on a
mise dans ce programme.
La règle "RLR" va produire un motif aléatoire, mais la fourmi ne construira jamais d'autoroute.
La règle "RLLR" crée une structure carrée avec des motif complexes à l'intérieur.
La règle "RLRRRRLLLR" crée un autre carré qui a l'air plus simple.
La règle "RLRRRRLLLR" est probablement la plus étrange. Elle produit une forme triangulaire qui grossit et se
déplace vers le bas.
Vidéo: Fourmi de Langton en processing