Previously, on this blog :


Fourmis incapables de contourner un obstacle pour atteindre la fourmilière

Pour tenter de faire évoluer la simulation, j'ai commençé par ajouter la gestion des phéromones de danger. J'ai eu un peu de mal à trouver une bonne manière de gérer le comportement des fourmis face à cette phéromone, en particulier en ce qui concerne la "propagation" du message par les différentes fourmis. Le taux d'évaporation de la phéromone en question a aussi été très dur à trouver (il est dépendant de pleins d'autres critères, comme le nombre de fourmis et leur vitesse de déplacement). Il m'est arrivé assez souvent de tomber sur ce genre de résultat (phéromone de danger en rouge):


Crise de panique ! la fourmilière elle même est indiquée comme zone de danger)

Une fois la gestion de cette phéromone supposée correcte, j'ai tenté de suivre (en gros) l'idée de Bidule donnée dans les commentaires du dernier article : les obstacles doivent être considérés comme un danger. La première fourmi qui rencontre l'obstacle marque la zone comme dangereuse, et les fourmis qui arrivent ensuite propagent ce message pour former une sorte de "bulle" d'alerte autour de l'obstacle. L'objectif était que les fourmis qui convoient de la nourriture soient forcées de trouver des chemins alternatifs pour retrouver la base. Le résultat sur lequel je suis tombé m'a réellement étonné :


Fourmis bretonnes ?

Elles se sont toutes concentrées à l'intérieur de la zone de danger !
Incapable de trouver un chemin de retour correct (on voit quelques tentatives en bas de la capture), elles se retrouvent très vite "noyées" dans un espace saturé de phéromones de danger et de nourrriture contradictoires ... sans pouvoir en sortir pour la majorité d'entre elles (il y a quelque chose comme 30 fourmis dans la zone rouge de cette capture !). Un échec. Impossible de les guider par la peur, donc :)

J'ai donc tenté une autre piste, qui me fait revenir au principe de base de la simulation qui nous intéresse : jouer sur l'intelligence du groupe, et pas de l'individu. Plutôt que d'ajouter des capacités aux fourmis (détection et propagation du danger), j'en ai retiré : les déplacements au départ de la source de nourriture sont beaucoup plus aléatoires qu'avant (en ce qui concerne le cap) et surtout ... la production de phéromone de nourriture (bleue, donc) est limitée ! Impossible pour les fourmis de tracer des pistes trop longues, et il leur faut retrouver la fourmilière pour "refaire le plein" de cette phéromone. Cette nouvelle méthode stimule de fait la recherche de nouvelle pistes.



Pour la première fois, j'ai vu un chemin se créer entre la source de nourriture "cachée" et la fourmillière ! (visible au centre, ici)
Cette piste se trouve ensuite automatiquement privilégiée, puisque efficace. Les fourmis qui empruntent ce chemin (qui a été trouvé par une seule fourmi à la base) depuis la source de nourriture arrivent à destination en renforcant la piste existante, puisqu'elles disposent d'assez de phéromones. Sur la capture précédente, on voit qu'une autre piste ("mauvaise", elle) existe. Elle mène directement à l'obstacle ... et elle s'évapore donc petit à petit. On voit clairement sur la capture un groupe conséquent de fourmis qui est arrivé au bout de la piste, et qui se retrouve à avancer au hasard vers la gauche... (longtemps après, elles vont finir par trouver la bonne piste, voire directement la fourmilière). Et ça au lieu de buter bêtement contre l'obstacle comme précédement.

Il faut maintenant que je trouve les bons réglages pour l'ensemble de la simulation, et c'est n'est pas rien ... il y a 16 paramètres différents à tester. Je me suis rédigé vite fait un petit outil qui me sort ce genre de graphs :



Ca va beaucoup m'aider pour trouver la meilleur configuration pour la simulation. Si tout se passe bien, je devrais pouvoir ajouter la gestion des naissances et des morts (de vieillesse et de faim) sans que la simulation ne soit particulièrement perturbée. Au vu de la courbe actuelle, il y a encore beaucoup à faire ! Par exemple ici, la collecte de la totalité de la nourriture demande 36 minutes ("réelles", pas "de calcul"), et se fait de manière trop linéaire ... les sources de nourriture devrait être exploitées beaucoup plus vite après leur découverte. Le graph devrait donc être composé de paliers (autant que de sources de nourriture).

Je vais tenter d'automatiser la recherche des meilleurs critères (sorte d'algo génétique, toutes proportions gardées). Pour l'heure, au pieu !

La première étape du projet Scopitone 2007 était la validation du tracking laser. Mon laser à deux balles d'euro ayant rendu l'âme lors des derniers tests, j'ai regardé ce qui existait de plus puissant, en particulier chez http://wickedlasers.com/ (merci Mathieu). Allez jeter un oeil : ce sont des malades ... Leurs lasers sont monstrueux, capables de pointer à 30 Km, crâmer certaines matières, d'allumer des feux, ...


En fait, rien d'exploitable pour nous (j'imagine pas laisser de telles choses dans les mains du public de l'attraction, qui va probablement être aussi composé d'enfant ...), ce qui fait que je suis retombé dans des puissances raisonnables avec un bête laser 5mW (rouge) acheté sur eBay (ce sera toujours mieux que mon machin de même pas 3mW).

Bref, le tracking ne devrait pas poser de problèmes a priori, il est donc temps de se lancer dans l'étape suivante : la simulation des fourmis.



Je me suis donc lancé dans l'écriture d'un prototype du simulateur, histoire de vérifier que le concept était viable (et plus prosaïquement pour vérifier que je suis capable d'écrire un truc pareil). Le monde se compose d'un espace carré de taille variable (256x256 cases pour les tests actuels) dans lequel évoluent les fourmis. Chaque foumi est caractérisée par un certain nombre d'états (position, tâche en cours, direction, nourriture transportée, ...) et est capable d'un certain nombre d'actions (très connes, comme les vrais fourmis). L'idée de base étant de vérifier (et simuler) qu'un ensemble d'êtres individuellements très limités peuvent faire émerger une intelligence de groupe, ce qui, soit dit en passant, se trouve être (à mon sens) le strict inverse de l'homme (intelligence individuelle forte, mais qui tourne à la connerie pure lorsqu'elle est mise en groupe : files d'attente à la Poste, bouchons sur le périph', ... les exemples ne manquent pas).

Au delà des fourmis, le monde est aussi composé de nourriture (répartie plus ou moins aléatoirement par blocs dans le monde) et, à terme, d'obstacles.

L'interaction entre le monde et le fourmis se fait principalement au travers des fameuses phéromones, sorte d'odeurs laissées par les fourmis sous certaines conditions (on parle de "communication par le terrain"). Dans la simulation, les phéromones sont "orientées", pour indiquer dans quel sens suivre la piste, par exemple (je pense que cette approximation de la réalité ne change pas trop la cohérence de la simulation, tout en m'épargnant beaucoup de code ...). Les seules phéromones gérées actuellement sont celles liées à la nourriture : une fourmi qui a trouvé (par hasard) une source de nourriture laisse derrière elle une piste lors du retour, qui se fait, à priori comme pour les vrai fourmi, par un cap (déteminé par exemple en fonction de la position du soleil) approximatif. Les autres fourmis qui croisent cette piste peuvent donc remonter à la source de la nourriture. La piste sert aussi pour le retour à la "base", ensuite. A terme, les phéromones de " danger" sont prévues.

Dans l'état actuel des choses, les fourmi de la simulation sont tout à fait capables de s'organiser pour rappatrier la nourriture. Voilà par exemple une situation typique de la simulation actuelle :


En vert, la nourriture, en blanc les fourmis, en bleu les phéromones (intensité de la couleur proportionnelle à l'intensité des phéromones), la "base" des fourmis est au centre de l'écran (invisible ici)

Les deux sources de nourriture sont exploitées, sans pour autant concentrer toutes les troupes, ce qui permet la découverte d'éventuelles nouvelles sources de nourriture ou de menaces. J'insiste sur le fait que ce résultat est obtenu avec une simulation qui n'agit que localement (sur chaque fourmi). A aucun moment, un truc du genre "if(assez de fourmis qui ramènent de la bouffe) then (barrez-vous en chercher autre part)" n'est présent dans le code. Cette organisation (même simple ici) émerge du groupe. En d'autres termes, je n'ai pas programmé cette solution, elle est née lors de l'execution du programme. En définitive, mon rôle ici est de programmer le cerveau de chacune de ces fourmis ('vache, j'adore cette phrase ! :)

En l'absence d'obstacles, la simulation actuelle est quasi "parfaite", au sens ou la nourriture est très vite rappatriée, et dans des conditions parfaites (les autres fourmis cherchant d'autres sources et/ou veillent à la sécurité du groupe en patrouillant). En revanche, dès qu'on ajoute des obstacles, les choses tournent mal ...



La distribution est très mauvaise (source du haut exploitée à 70%, celle du bas à même pas 10%), la veille est fortement réduite (risque d'attaque, incapacité à découvrir vite de nouvelles sources de nourriture), et on retrouve une très forte concentration de fourmis (plus d'une 15aine sur une population de 30 !) bloquée sur le chemin du retour ! (puisque l'ostacle est juste sous la base). N'allez pas croire que le problème vient de la gestion des obstacles : sans nourriture les fourmis sont tout à fait capables de détecter qu'elles sont bloquées et agissent en conséquence. Le problème ici est qu'elles sont tellement dépendantes des pistes de phéromones pour le retour vers la "base", que même lorsqu'elles cherchent à s'écarter de l'obstacle (qu'elles ont donc bien détecté), elles sont de nouveau attiré vers celui ci par la très forte concentration de phéromone qui y règne.

Et c'est sur ce constat que je vais me coucher ! :)
A suivre ...

J'ai donc effectué quelques tests préliminaires pour la tracking de cible laser.
J'utilise pour ces tests une webcam Philips SPC900NC. Cette webcam se trouve être particulièrement douée dans les environnements sombres. Pour des raisons de vitesse de traitement d'image, la capture est réalisée en 320x240 24bpp à 30 FPS.


Le vidéoproj' est un NEC VT58 (super lumineux, image gigantesque), merci Quiris.

En ce qui concerne le tracking, j'utilise une méthode toute bête, que j'ai envie de nommer "distance au rouge".
Explications :
L'impact du laser est rouge, l'idée est donc de rechercher les "points chauds" rouges dans l'image à chaque nouvelle image.


Scène de référence pour le test de l'algo

Si on se limite à extraire la composante rouge de l'image, le résultat n'est pas du tout le bon (un blanc pétant possède un rouge très élevé, sans pour autant être un point d'intérêt rouge, bien sûr)


Composante rouge

Jetez un oeil au rideau jaune, sous ma main, au fond : il est encore parfaitement visible ... mais n'est pas rouge.
J'applique donc une formule toute bête qui consiste à mesurer la "distance" entre la composante rouge et les composantes vertes et bleues (pondérées). En pratique, il semble même que la composante bleue soit à peine même nécessaire pour la pertinence de ce calcul (probable problème avec le mauve ?). Le résultat est bien sur multiplié par la "luminosité" du pixel, pour qu'un pixel rouge clair soit plus représentatif qu'un rouge plus prononcé, mais plus sombre.

On arrive au résultat suivant :

"Distance au rouge" (résultat amplifié pour la présentation)

Les rideaux ne sont plus là, et seules les parties ... roses restent (faute de rouge).

Il ne restait plus qu'a mettre tout ça en pratique :


Le vidéoproj' affichait une image caratéristique d'une scène Raydium en extérieur, avec même quelques éléments rouges :


... et voilà le rendu auquel on arrive, sans réglages particluliers :

crade ... mais de nuit, avec une webcam !

Le problème ici, c'est que mon petit laser acheté 2 euros au coin de la rue et dont les piles sont en fin de vie ... eh bien il passe inaperçu !
J'ai donc fouillé la documentation de l'API Video4Linux du driver PWC de Luc Saillard pour la webcam, dans laquelle on trouve deux réglages intéressants : la balance automatique des blancs et le "temps d'ouverture". En désactivant la balance auto (remplacée par une valeur fixe empirique) et en réduisant fortement le temps d'ouverture depuis l'application, on arrive à un résultat beaucoup plus intéressant à traiter :


Si vous cherchez, l'impact du laser est visible sur cette image

L'image n'est pas "trop" sombre, mais belle et bien équilibrée. J'en ai profité pour baisser la luminosité du vidéoprojecteur pour augmenter le contraste avec l'impact du laser.

Si on active le filtre de distance au rouge, voilà le résultat :

(contraste et luminosité de la capture amplifiées pour la présentation)

Le pointeur ressort fortement de l'image, le tracking devient très simple !


Abstract Numeric Art

En bref, les résultats sont assez corrects, même si les tests doivent maintenant êtres poussés sur une scène de la simulation. Autre point, la qualité du laser compte beaucoup, et là notre marge de manoeuvre est énorme ... Si vous connaissez des lasers (rouges) bien puissants, n'hésitez pas.

A suivre !

Le festival Scopitone est un jeune festival de musique et d'arts numériques sur Nantes (2002, 2004, 2005 et 2006) qui grandit à une vitesse assez impressionnante. Pour vous donner une idée, voilà un morceau de la prog' de cet été pour le lieu de nuit (orienté musique, donc) :
Coldcut, Laurent Garnier, Bugge Wesseltof, Emilie Simon, Erik Truffaz, Le Peuple de l'Herbe, Kid Loco, Amon Tobin, Asian Dub Foudation, Troublemakers, Zenzile, ...



Nous ("CQFD") avons eu l'occasion de participer par trois fois à ce festival, sur le lieu de jour (orienté arts numériques), pour exposer Raydium (le moteur 3D dont il est question dans ce blog, pour ceux qui suivent pas). Nous disposions alors d'un stand dans l'espace "associations" pendant les deux jours du festival, et ces différentes rencontres avec un public plus que varié ont toujours été particulièrement intéressantes. Quelques articles sur ce blog parlaient déjà de ce sujet :

- Moteur 3D / Moteur de jeu : Comment présenter les concepts au quidam moyen ? (Scopitone 2004)
- Raydium : des images et peu de mots (Scopitone 2005)



Eh bien nous avons l'opportunité de participer à nouveau au festival de l'année prochaine (septembre / octobre 2007 ?), et d'une manière complétement différente, cette fois !
Au choix :
- Projection vidéo en temps réel derrière les artistes musicaux du lieu de nuit sur d'immenses écrans sur et autour de la scène (!)
- Création d'une animation complète , dans une pièce complétement dédiée à notre ... "oeuvre".


lieu de nuit ...


... ou lieu de jour ?

Même si la première option est très (très) tentante, nous avons décidé (lors d'une réunion hier) d'opter pour la seconde, en particulier car nous sommes très peu confiants entre notre capacité à faire des trucs graphiquements sympathiques (et projeter un truc tout laid devant une foule de 4000 personnes, bof). La décision n'est ceci dit pas définitive (quel groupe de musique ? quel style graphique ? abstrait ? réaliste ? quel genre d'intéractions temps réel ? ...), nous allons parler de ça avec eux bientot.

Le thème qui ressort après réflexion : l'interaction entre le public et un monde autonome.
Techniquement, nous allons projeter sur une "table" une simulation de vie, utilisant une colonie de fourmis et un petit écosystème (nourriture, végétation, phéromones). L'interaction consiste à venir perturber la colonie, en déplacant des objets de la scène (roches), nourriture, en effacant les traces des fourmis, voire même en tuant les fourmis. Nous pensions permettre aux gens d'interagir directement sur la table, à la main, mais nous n'avons pas trouvé de solution technique efficace à ce problème (en connaissez-vous ?).

Je m'oriente donc vers une solution à base de pointeur laser :

... avec un système de tracking utilisant une webcam. Le système reste très naturel pour le public (on vise directement la table), permet de tracker plusieurs "cibles" en même temps, ne coute quasi rien, et demande un calibrage relativement simple (sensibilité et "mapping" des coordonnées de la webcam vers celles de la table).



Tout est à faire ! Je vais tenter de mettre à jour ce blog tout au long de l'évolution du projet. En espérant qu'on arrive au bout, et que ça ressemble effectivement au projet présenté ici :)