Algorithmique de la mobilité

↑ Accueil du cours


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:

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 :

  1. La performance de l'algorithme, c'est à dire le temps de survie de la fourmilière
  2. La clarté du code et du rapport
  3. 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).