Segmentation fault

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.

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)

Nous 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 :

• Site du projet sur Sourceforge.net
• La page de téléchargement
• Le dépot SVN accessible en ligne
• Les détails pour effectuer un check-out du SVN
• La documentation HTML en ligne

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 !