Exploration par des fourmis

Travail à rendre

Avant le vendredi 20 décembre à 23h59

Par courriel à arnaud.casteigts@labri.fr, jason.schoeters@labri.fr, et remi.laplace@labri.fr:

Un fichier .tar.xz de votre projet Intellij qui fonctionne quand on le décompresse (testez avant d'envoyer!). Attention, les .zip ne passent pas le filtre du serveur mail, tandis que nous avons testé .tar.xz qui fonctionne.
Un rapport de 2 pages maximum décrivant votre stratégie algorithmique (et tout autre élément jugé pertinent).

Certains éléments seront peut-être ajoutés au sujet (ou modifiés à la marge) entre les deux semaines. Si tel est le cas, nous les indiquerons en gras lors de la deuxième semaine.

Résumé

Nous considérons un environnement dans lequel nous déposons une reine fourmi. Cette reine va produire des fourmis, qui devront aller explorer, chercher à manger, creuser des tunnels... et communiquer ! Le but général est de maximiser la durée de vie de la fourmilière tout en respectant un certain nombre de contraintes.

Le projet est à réaliser en monôme ou binôme. Les objectifs sont marqués avec un niveau 1, 2 ou 3 indiquant leur priorité: ne perdez pas de temps sur les objectifs de niveau 3 (voire 2) avant de vous assurer une base solide d'objectifs de niveau 1. Tentez d'aller aussi loin que possible, les extensions au projet sont de plus en plus libres à mesure que l'énoncé progresse.

Evaluation

Les trois composantes suivantes seront évaluées :

La performance de l'algorithme, c'est à dire le temps de survie de la fourmilière
La clarté du code et du rapport
Les idées mises en oeuvres

Le point 3 est distingué du point 1 pour récompenser les belles idées qui éventuellement ne seraient pas payantes.

Présentation du scénario

L'espace dans lequel nous allons travailler est un espace à deux dimensions qui représente un plan vertical du terrain (voir la figure ci-dessus). Dans cet espace, la coordonnée x correspond à l'axe horizontal et la coordonnée y à l'axe vertical. L'espace est discrétisé sous forme de cellules (la classe Cell). Chaque déplacement de fourmi peut durer un certain nombre de rondes, en fonction du type de terrain. On utilisera pour ces déplacements la classe WaypointNode que nous connaissons déjà. À chaque cellule, une fourmi peut avoir accès aux 8 cellules alentours par une API dédiée.

Sur leur chemin, les fourmis peuvent capter des phéromones que les autres fourmis ont laissé, ou en déposer elles-mêmes. L'objectif est de découvrir de nouvelles sources de nourriture et les exploiter pour ramener de la nourriture à la reine, qui peut convertir cette nourriture en fourmis. Les fourmis ont une durée de vie limitée, à part la reine, qui meure si elle n'a plus rien à manger. Il est donc essentiel de découvrir de nouvelles sources de nourritures régulièrement.

Description du travail à faire (point par point)

Récuperez l'archive zip du projet. Dézippez et lancez ce projet avec IntelliJ. La classe principale est AntHillMain. Le package ui s'occupe de l'affichage (comme le fond d'image, ou encore les tunnels creusés).

A (niveau 1) : Considérez la classe de noeud AntNode. Au départ, les fourmis ne savent se déplacer qu'à gauche et à droite, de façon aléatoire. Faites en sorte que les fourmis se déplacent également en utilisant l'axe vertical, toujours de façon aléatoire. Utilisez la classe WaypointNode pour rendre le déplacement plus fluide. À tout moment, une fourmi n'a connaissance que de son environnement immédiat, à savoir les cellules adjacentes à sa cellule courante (ainsi que cette dernière).
B (niveau 2) : Il faudra également de la nourriture pour la colonie de fourmis, c'est à dire FoodNode, qui contient entre 10 et 20 points de nourriture. Considérez la classe FoodSpawner qui permet de placer de la nourriture aux endroits aléatoirement au cours de l'exécution du programme. Modifiez cette classe pour qu'elle place plus de nourriture en bas qu'en haut de l'environnement.
C (niveau 1) : Il manque maintenant les méthodes nécessaires aux fourmis pour trouver et ramener de la nourriture :
1. porter de la nourriture, avec une fonction takeFood(), qui doit alors baisser la quantité du noeud FoodNode.
2. déposer de la nourriture, avec une fonction dropFood(), qui augmente donc le stock de nourriture de la reine (si la fourmi le dépose à la reine). Une fourmi ne peut porter que 1 seul bout de nourriture. Une image différente est disponible ici pour changer l'apparence des fourmis portant de la nourriture.
D (niveau 2) : Jusqu'à là, les fourmis étaient libres de se déplacer comme ils le souhaitent dans l'environnement. Pour être réaliste, il faudra d'abord creuser des tunnels avant de pouvoir se déplacer. À chaque endroit où les fourmis veulent bouger, vérifier d'abord si il y a déjà un tunnel de creusé. Dans le cas contraire, la fourmi peut décider ou pas de creuser ce tunnel, ce qui devrait prendre un temps fixe (disons 1000 onClock()).
E (niveau 3) : Faites varier le temps qu'il faut pour creuser un tunnel. Il ne faut que 100 onClock() pour creuser un tunnel proche de la surface, tandis qu'il en faut 1000000 pour en creuser un au point le plus profond. Plusieurs fourmis peuvent creuser un même tunnel, ce qui doit diviser d'autant le temps nécessaire. Modifiez la méthode initializeQueen dans la classe AntHillMain pour qu'elle soit mise en place plus vers la surface.
F (niveau 1) : Faites en sorte que les fourmis (ainsi que la nourriture) aient une durée de vie limitée, c'est à dire, qu'elles disparaissent de notre environnement après une certaine durée (la fonction die() sera utile pour ceci). La reine n'a pas besoin d'un tel traitement, sachant que les reines fourmis peuvent vivre jusqu'à 37 ans ! Par contre, la reine meurt quand elle n'a plus de nourriture. Ceci sera l'événement à éviter dans la suite !
G (niveau 2) : Optimiser l'algorithme des fourmis, dans le but de faire survivre la colonie indéfiniment. Faites ceci en utilisant des phéromones (potentiellement de plusieurs types, par exemple un phéromone nourriture pour désigner un trajet vers la nourriture, un autre phéromone reine pour mener à la reine, etc.). Les phéromones sont déposés par des fourmis (supposons au maximum 0.1 par fourmis par onClock()) sur des endroits de l'environnement. Sur une case, il ne peut y avoir qu'un taux maximum de 1 de phéromone (et un minimum de 0). Ces phéromones doivent disparaitre au cours du temps (disons de 0.1 au cours de 10000 onClock()). En aucun cas, les phéromones peuvent comporter plus d'information que ceci.
H (niveau 3) : Modifier de plus en plus les paramètres (durée de vie d'une fourmi, temps avant que FoodSpawner produise de la nourriture, etc.) pour désavantager de plus en plus votre colonie.
I (niveau 3) : Ajouter des obstacles que les fourmis (ou leur nourriture) ne peuvent pas traverser.