Introduction au projet

Ce projet s'inspire des travaux de Christopher Langton, un scientifique américain qui travaille sur la vie artificielle, et plus particulièrement d'un automate cellulaire connu sous le nom de "fourmi de Langton". On trouvera sur Wikipédia une introduction au sujet.

Notions sur les automates cellulaires

Un automate cellulaire évolue en fonction d'un diagramme constitué de noeuds "états" et d'arcs "transitions". A chaque pas de temps, des règles sont appliquées simultanément à tous les automates qui modifient leur comportement en conséquence. L'un des automates cellulaires les plus célèbres est celui du "jeu de la vie".

L'automate de Langton

Comme de nombreux automates cellulaires, celui de Langton a un comportement déterministe élémentaire. Sur une grille bidimensionnelle constituée de cases blanches ou noires, la fourmi se déplace d'une case dans n'importe quelle direction selon les deux règles suivantes :

• si la fourmi est sur une case noire, elle tourne de 90° vers la droite, change la couleur de la case en blanc et avance d'une case,
• si la fourmi est sur une case blanche, elle tourne de 90° vers la gauche, change la couleur de la case en noir et avance d'une case.

Analyse et conception

La décomposition en trois parties est naturelle.

Le terrain est constitué d'une grille rectangulaire à pas fixe. Il doit mémoriser son état (pour l'affichage et par soucis d'incrémentalité) ce qui se fait aisément en stockant dans une structure de liste les cases de couleur. Il faut donc prévoir d'ajouter et de retirer des informations de cette liste. La forme que revêt chaque information est un tuple de trois éléments : l'abscisse et l'ordonnée de la case de couleur ainsi que la couleur (qui peut être différente de noir, voir ci-après pour l'extension au projet initial). Enfin, le terrain est susceptible de fournir quelques informations utiles dont la répartition statistique du nombre de cases par couleur.

Une fourmi est caractérisée de façon général par une couleur et un comportement, comme expliqué ci-dessus dans le projet initial. Mais il faut aussi modéliser ses mouvements ce qui se fait par la prise en compte des informations de position et d'orientation. La position doit être conforme au modèle fourni par le terrain. L'orientation peut être modélisée par une lettre associée à un point cardinal (N pour nord, E pour est, S pour sud et O pour ouest).

Enfin, le module principal procède à différentes initialisations puis se charge de mettre à jour l'affichage de l'évolution de la situation pour un nombre de pas donné.

Extension du projet

L'extension naturelle de l'idée originale consiste à gérer plusieurs couleurs de fourmis.

A chaque cycle d'affichage il faudra donc mettre à jour le comportement de chaque fourmi en fonction de la couleur de la case dans laquelle elle rentre. Cela implique de donner une direction de déplacement pour chaque couleur, en plus du cas de la case vide (i.e sans couleur). Ainsi, pour 4 fourmis, on code le comportement de chaque fourmi par l'intermédiaire d'une chaîne de 5 caractères associée, par exemple GDGGD (par convention la première lettre code le comportement d'une fourmi dans le cas d'une case vide puis chaque lettre code le comportement de la fourmi en fonction de la couleur de la case rencontrée). A noter que le comportement d'une fourmi quand elle rentre dans une case à sa couleur ne doit jamais être identique à celui d'une case vide.

Ceci étant, le comportement fondamental d'une fourmi vis à vis de la couleur des cases ne change pas : si elle rentre dans une case vide elle met la case à sa couleur sinon elle efface la case (qui devient une case vide) quelle que soit sa couleur.

Consignes

Modularité et protection des données

Une attention particulière doit être accordée à ce point. Le projet est subdivisé en trois modules : terrain, fourmi et main, ce dernier comprenant le programme principal et des éléments de l'interface utilisateur (chaque module comportant le même préfixe, par exemple langton_).

Pour chaque module, on peut indiquer que certaines variables et fonctions sont d'un usage interne au module. Pour cela, on préfixera leur nom d'un underscore (_), ce qui signifie dans la philosophie ouverte du langage que l'on ne souhaite pas qu'elles soient visibles (et donc directement utilisables) dans les autres modules. Cette "protection" n'est effective que si l'on effectue une importation au niveau de l'espace des noms global. Exemple :

# module1
_x = 0

def _f():
  pass

# module principal
from module1 import *

_f()  # NameError: name '_f' is not defined

Test unitaire

Au moins un module (à l'exception du module principal) doit comporter un test unitaire vérifiant l'ensemble de ses fonctionnalités. Exemple :

# module 1
def _f():
  pass

def g():
  pass

# tests unitaires
if __name__ == '__main__':
  _f()  # test de la fonction "privee" _f
  g()  # test de la fonction "publique" g

Débogage

L'option -O de l'interprète Python, associée à la variable interne __debug__, offre un moyen de commutation des messages de débogage. Exemple :

# desactive par l'option -O
if __debug__:
  print("mode debug : python lance sans -O")
else:
  print("python lance avec l'option -O")

Les modules

Le module terrain doit comporter au minimum les fonctions suivantes :

• affichage graphique du terrain initial, constitué d'une grille matérialisant les positions possibles des automates cellulaires,
• affichage graphique d'un carré de taille fixe à la position (x, y) et de couleur col,
• gestion interne des informations associées (manipulation de la liste des cases occupées),
• modification de l'état d'une case (occupée ou libre),
• information statistique de répartition des cases occupées.

Le module fourmi doit comporter au minimum les fonctions suivantes :

• vérification de la conformité des motifs gérant les comportements,
• placement des fourmis sur le terrain de façon uniforme en fonction du nombre de fourmis,
• fonction retournant la nouvelle orientation d'une fourmi en fonction du mouvement (gauche ou droite) et de la direction de ce dernier,
• déplacement d'une fourmi donnée,
• animation de toutes les fourmis.

Le module principal permet d'initialiser le jeu et de mettre à jour les données et l'affichage. Pour cela un module pocketgl en version Python 3.x est mis à disposition. Il permet d'ouvrir une fenêtre graphique, d'afficher des primitives graphiques (point, segment, rectangle, cercle, polygone, texte et image) et de mettre à jour l'affichage. Un exemple d'utilisation est donné à titre de test unitaire dans le fichier lui-même. Pour information, son utilisation repose sur les modules tkinter (fourni par défaut avec le langage Python) et PIL (un "fork" de Pillow pour Python 3.x).

Au lancement de l'application, l'utilisateur doit donner le nom du fichier définissant le comportement de chaque automate cellulaire fourmi. Par exemple pour 4 fourmis :

GDGDG
GDDDG
DDDGD
GDGDD

Le nom du fichier sera soit communiqué en ligne de commandes au lancement du programme, par exemple : ./langton_main fourmi01, soit demandé durant l'exécution du programme.

Ensuite, le programme lance la simulation proprement dite pour un nombre de pas fixé par convention et accompagnée d'informations sur la répartition de chaque couleur présente et l'évolution du pas au fil du temps.

Options

Différentes options au choix peuvent compléter le projet.

• considérer que les bords de la grille sont adjacents deux à deux : le bord haut avec le bord bas et le bord gauche avec le bord droit, ainsi par exemple, une fourmi qui sort par la droite doit poursuivre son chemin à gauche de la grille ; dans ce cas la grille est topologiquement équivalente à un tore.
• proposer les motifs qui spécifient le comportement de chaque fourmi comme paramètre de l'application (exemple : ./langton_main GDGDG GDDDG DDDGD GDGDD).
• ajout d'obstacles inamovibles placés aléatoirement. Si une foumi "entre" dans une case avec obstacle, elle doit faire demi-tour et revenir dans la case précédente (donc avec une direction opposée à celle qu'elle avait avant de rencontrer l'obstacle), ceci sans effacer l'obstacle.