Teapot Colony Wars : Le premier simulateur de stratégies comportementales pour théières

4 février 2008 – 21:47

Dans le cadre de mes cours de programmation et de modélisation orientée objets, il nous a récemment été demandé de réaliser un projet en binôme. A vrai dire, nous l’avons rendu aujourd’hui… Le but était de modéliser et de concevoir une application simulant l’évolution de colonies d’individus sur un terrain. Le sujet décrivait les règles de la simulation et de fonctionnement du monde dans lequel les colonies seraient amenées à évoluer. L’objectif n’était pas tant de coder une belle interface avec une intelligence artificielle hors du commun, mais plutôt de s’attacher à bien concevoir l’application, en utilisant les techniques habituelles comme le langage UML et les Designs Patterns.

Screenshot du projet

Avec un ami, nous avons eu une idée commune : tant qu’à faire une application de simulation, autant se faire plaisir et la réaliser en 3D. Fans des technologies libres, nous avons donc choisi OpenGL et Glut. Nous avions tous les deux une petite expérience en OpenGL, pour ma part ce fut mon deuxième projet C++/OpenGL, bien que je trouve bien plus complexe que le 1er. Étant donné que nous n’avions pas des talents d’artistes, nous avons choisi de faire simple pour ce qui était de la représentation du monde et des individus. Les adeptes de Glut ou plus généralement de la 3D connaissent probablement la fameuse Théière de l’Utah utilisée dans un certain nombre d’applications 3D. Ce modèle étant déjà présent par défaut dans la bibliothèque GLUT, nous avons décidé de l’utiliser pour représenter les individus de nos colonies. Et nous en avons profité pour baptiser notre projet «Teapot Colony Wars».

Nous avions le choix du langage, et nous avons choisi le C++ non seulement pour sa rapidité, sa portabilité, mais aussi parce que nous souhaitions progresser dans ce domaine. Et tant qu’à faire, nous l’avons développé dans le but de le diffuser sous licence GPL 2, pour qu’il continue à vivre et évoluer si certains veulent le reprendre. De plus, nous avons vraiment eu la volonté de développer un projet en nous rapprochant du monde professionnel, tout en n’utilisant que des logiciels libres. Nous avons utilisé Subversion, un excellent outil de gestion de versions qui nous a bien simplifié la tâche pour le développement, ainsi que Doxygen, pour la génération de la documentation. Le rapport de conception a été réalisé en LaTeX, et la compilation de l’exécutable a été grandement facilité par l’emploi des Autotools (AutoConf, AutoMake, …).

Au final, Teapot Colony Wars, c’est :

  • 96 fichiers sources (uniquement les .h et .cpp)
  • Un diagramme de 45 classes
  • Plus de 9600 lignes de code C++
  • Un délai de 6 semaines pour réaliser le projet (pendant lesquelles nous avons eu des examens…)
  • Plus de 280 heures de travail
  • 268 révisions dans le dépot Subversion
  • Une documentation PDF de 449 pages générée par Doxygen
  • Un rapport de 28 pages décrivant la modélisation et nos choix conceptuels

Nous avons profité de la livraison du projet pour publier la version 1 sur Sourceforge.net. Voici quelques unes des caractéristiques de l’application :

  • Le monde est composé de plusieurs colonies, chacune ayant sa couleur.
  • Chaque colonie peut créer des individus qui possèdent des caractéristiques propres comme sa taille. Une colonie consomme de la nourriture pour créer un individu.
  • Le monde est composé d’une grille de cellules qui ont chacune des propriétés. Certaines sont inaccessibles (murs), d’autres contiennent de la nourriture qui se renouvelle au fur et à mesure de la simulation (certaines sont à renouvellement instantané, mais pas d’autres). Certaines cases sont des couloirs et inaccessibles aux individus trop grands.
  • Les individus évoluent selon certaines stratégies comportementales que la colonie leur impose. Leur but est de trouver de la nourriture et de la ramener à la colonie. Mais à chaque pas, un individu consomme de la nourriture proportionnellement à sa taille.
  • Chaque individu ne peut voir que les 8 cases adjacentes et a une très petite mémoire : il ne peut se souvenir que de la dernière case qu’il a franchie. Mais pour l’aider, il peut déposer des phéromones sur son passage. Chaque colonie définit ainsi 3 phéromones qui ne peuvent être comprises que par ses individus. Chaque phéromone a une durée de vie et se dégrade au fur et à mesure, jusqu’à disparaître.
  • Quand deux individus ennemis se croisent, il y a combat. C’est le plus fort qui gagne ! Le vainqueur peut alors se nourrir du cadavre de ses adversaires.
  • L’utilisateur peut à sa guise faire une offrande en déposant une source de nourriture sur le terrain.
  • Il était demandé de tester deux stratégies différentes pour les individus. Les algorithmes heuristiques, qui peuvent être simples mais souvent imparfaits, et les algorithmes génétiques, consistant à définir des gènes pour les individus et effectuer un brassage génétique de la population en sélectionnant les meilleurs.

Les commandes souris et clavier du simulateur sont les suivantes :

  • Pavé numérique (4, 6 8, 2) : déplacements horizontaux et verticaux
  • Molette ou touches + et – : zoom
  • Maintien de Ctrl et défilement de la molette (ou + et -) : inclinaison verticale
  • Maintien de Ctrl + Clic gauche ou droit : rotation à gauche ou à droite
  • Espace : Activer / enlever le mode pause
  • Clic gauche : effectuer une itération
  • Étoile (*) : donner une offrande aux individus, qui apparaîtra sur le curseur de sélection (tore en bleu clair)

Screenshot du projetNous sommes globalement très satisfaits de ce projet, car nous avons pu finir dans les temps, même si nous aurions aimé rajouter quelques fonctionnalités supplémentaires. Mais cela restera tout à fait possible étant donné la grande extensibilité de notre application. En effet, grâce à un usage intensif de toutes les techniques propres à la modélisation orientée objet, comme le polymorphisme et les designs patterns, nous avons construit un ensemble de classes génériques, qui peuvent s’apparenter à un framework. Il est ainsi tout à fait possible de rajouter à moindre coût des nouvelles cases, des nouveaux types d’individus, changer leur représentation (pour ceux qui n’aiment pas les théières…), changer le système de combat, et même pourquoi pas rajouter de nouveaux mouvements (comme le saut ou la téléportation).

Si cela vous intéresse, vous pouvez télécharger la version 1.0 du projet, tel que nous l’avons rendu à nous professeurs. Les sources sont disponibles, ainsi que les exécutables pour Linux et Windows. Attention toutefois pour ce dernier, il semble que la portabilité soit encore un tout petit peu imparfaite ; en effet nous n’avons pas encore eu le temps de changer quelques détails qui peuvent bloquer la génération de l’exécutable selon le compilateur utilisé. Mais nous allons bientôt remédier à cela…

Voici les liens pour accéder aux ressources du projet :

Pour lancer l’application sous Windows, vous avez juste à lancer l’exécutable. Sous Linux, pensez toutefois à lancer l’application en mode console pour éviter les surprises ; en effet, il faut que le dossier de textures se trouve dans le dossier courant.

Pour compiler le projet sous Linux, assurez-vous de disposer des bibliothèques pour le développement d’application graphiques, en particulier Glut. Décompressez l’archive dans un répertoire, puis tapez les instructions suivantes :

$ ./configure --prefix=$HOME
$ make
$ make install

L’application s’installera automatiquement dans votre homedir, dans le dossier bin. Si la documentation vous tente, vous pouvez générer le HTML et les fichiers LaTeX en tapant :

$ doxygen Doxyfile

Ensuite, placez-vous dans le dossier doc/latex et tapez simplement :

$ make

Le PDF résultat se nomme «refman.pdf» et sera généré dans le dossier courant. Bonne lecture…

Un site internet du projet verra peut-être le jour au courant de l’année, si je trouve un peu de temps à y consacrer. N’hésitez pas à me faire part de tous vos commentaires sur ce projet. Profitez de sa licence et faites le vivre !

  1. 7 réponses à “Teapot Colony Wars : Le premier simulateur de stratégies comportementales pour théières”

  2. Un rapport de 28 pages seulement pour un si gros (?) projet !?

    Ouaou. Du gros boulot tout de même. Chapeau !

    Par Saelyx le 14 février 2008

  3. Tiens, ils font les design patterns à l’INSA maintenant. Tant mieux, ce n’est pas trop tôt.

    Tiens, un très bon cours de design patterns ici :
    http://st.inf.tu-dresden.de/content/index.php?node=teaching&leaf=1&subject=108

    Tu y vois plein de choses, notamment les patterns du Gang of Four mais bien d’autres choses.

    Je me souviens avoir passé des soirées entières au niveau des exos, mais crois-moi, ça me sert énormément maintenant. (Je gère un projet en Java pour la boîte où je bosse.) Et c’est vrai que Java est sûrement un bien meilleur langage que C++ pour faire de l’objet, dans le sens où avec C++ tu restes très près du niveau hardware, et puis c’est quand même un peu l’ancêtre… En entreprise Java ou .Net est maintenant bien plus recherché.

    Cela dit bravo pour ton projet !

    ++,

    « - ».

    Par "-" le 23 février 2008

  4. Merci ! Je regarderai ça… Je savais pas qu’il n’y avait pas de cours sur les DP avant à l’INSA.

    Sinon pour ce qui est du combat Java / C++, personnellement je préfère le C++. Même s’il est plus bas-niveau, plus difficile à utiliser, et nécessite une bonne connaissance des mécanismes internes (gestion mémoire…) il est carrément plus efficace. Il est peut-être plus vieux, mais il n’a pas perdu une ride :) Et puis il faut avouer que pour la 3D et OpenGL, c’est carrément plus adapté.

    Pour ce qui est du .Net, j’en parle même pas, étant donné que je suis favorable aux technos libres et portables.

    Et puis bon, comme ce qui m’intéresse est plutôt le domaine technique et plus précisément la sécurité, j’ai plutôt tendance à préférer le bas-niveau, étant donné qu’il y a plus de contrôle sur ce que l’on fait… Et au pire, si jamais je ne trouve aucun emploi dans ce domaine là, je serais contraint de faire du Java, ce qui n’est pas bien dur quand on maîtrise le C++ !

    En tout cas, content d’avoir eu de tes news, depuis le temps ! Au plaisir…

    Par Emilien Girault le 23 février 2008

  5. Pour être honnête, ne te fais pas d’illusions. En Java tu as aussi de la gestion mémoire… et d’ailleurs c’est un piège à ce niveau car le programmeur naïf va croire que ce n’est pas le cas.
    Exemple : applique le pattern Observer entre ton modèle et un JFrame, ferme le JFrame sans faire un removeObserver au moment de la fermeture du JFrame : une jolie fuite mémoire en perspective… Il y a plein d’autres exemples comme ça.

    Quant à .Net, j’y suis aussi très hostile, d’autant que c’est Microsoft. Sache que Gnome dépend de .Net depuis la version 2.16, enfin plus précisément de Mono. Mais ce n’est pas étonnant puisque GNOme’s Microsoft Environment. C’est pour ça que saymoinbienque KDE. ;-)

    « - ».

    Par "-" le 23 février 2008

  6. Je n’ai pas dit qu’il n’y avait pas de gestion mémoire en Java, mais faut quand même admettre qu’il y en a carrément moins qu’en C++, vu qu’il y a un garbage collector. Et puis on pourra jamais empêcher les développeurs de programmer avec leurs pieds. ;)

    Pour Gnome et Mono, ça me surprend ! Enfin comme j’utilise aussi KDE, à vrai dire ça ne me dérange pas.

    Par Emilien Girault le 24 février 2008

  7. Cool d’avoir mis les liens vers le projet sur ton blog. Je tape « teapot colony war » sous google pour récupérer une copie du projet et je tombe direct sur ton blog, avec tous les liens utiles à porté de clic… :)

    En tout cas, ça me rappelle de bons souvenirs tout ça. On remet ça quand tu veux ;)

    @++

    Par Léo le 17 mars 2009

  8. Eh oui grâce à moi l’esprit des théières vivra éternellement :)
    Pour la v2, on pourra peut-être envisager de faire tourner ça sur un supercalculateur (MPI power!) dans la salle de réalité virtuelle de l’Irisa…

    Par Emilien Girault le 17 mars 2009

Désolé, les commentaires sont fermés pour le moment.