Fourmis : les obstacles

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 !


Publié

dans

par

Étiquettes :

Commentaires

14 réponses à “Fourmis : les obstacles”

  1. Avatar de DindonPoilu
    DindonPoilu

    A quand les obstacles dynamiques ? 🙂

  2. Avatar de Llyd
    Llyd

    Obstacles 0wnzor3d !!§§

    Bien joué, le coup du "tiens si elles se bloquent, c’est ptete qu’elles sont trop intelligentes". Cette intelligence de groupe est intéressante a voir mise en oeuvre.

    D’ailleurs, quand j’y pense, ton prog donne un comportement assez "évolué", mais niveau codage reste assez court et concis. Alors pourquoi on a toujours ces fps peuplés de dégénérés mentaux et d’autistes au derniers degré ? Comment se fait-il qu’une équipe avec des moyens et des outils nous pondent des trucs si minables, alors que toi, sur un truc gratos et presque seul, tu nous pond des trucs comme ca ?

    Je sais que "quand on a pas de pétrole, on a des idées" (et niveau idées, tu t’en sors bien jtrouve 🙂 ) mais plus t’avance dans ton projet, plus j’ai l’impression que niveau IA dans les jeux commerciaux, c’est plus "quand on a pas d’idées, on a du pétrole"

  3. Avatar de NecroDragon
    NecroDragon

    @Llyd : à mon avis, ca vient du fait que les FPS se passent en 3D, ce qui doit rajouter pas mal de complexité

  4. Avatar de Wooden
    Wooden

    T’es-tu informé sur les connaissances que l’on a sur les fourmis et leurs manières de communiquer, de prendre conscience de leur envirronnement et de structurer leurs actions collectives pour faire ce programme ? Est-ce juste un but informatique ?

  5. Avatar de Géhèm
    Géhèm

    Questinon totalement conne: tu mets toutes tes sources à la disposition, du, euh, "public" ? Sinon, t’as pas une idée d’un endroit où trouver ce genre d’algos, pour se mettre en douceur à l’IA ?

  6. Avatar de DindonPoilu
    DindonPoilu

    Llyd, Xfennec n’est pas le premier à programmer une colonie de fourmis. Sans vouloir diminuer son mérite ça se fait depuis super longtemps et c’est assez simple pour constituer un bon sujet pour un projet dans une école d’ingé par ex.
    Faire une IA pour un fps ça n’a rien à voir niveau complexité. Déjà les ennemis sont moins nombreux donc l’intelligence doit plus être cognitive que réactive. Faut doter les créatures de capacités de planification, de prévision des comportements de l’adversaire, de crédibilité au niveau des animations, etc. Et on est limités par les ressources de l’ordi qui est déjà pas mal occupé à afficher des graphimses neskgen.

  7. Avatar de Llyd
    Llyd

    @NecroDragon : Soit j’ai encore rien suivi, soit il bosse en 3D… en tout cas le moteur utilisé (Raydium je crois) est un moteur 3d.

    @DindonPoilu : je suis d’accord avec toi, mais c’est pas non plus les mêmes moyens. Un jeu se dev’ en plusieurs mois maintenant, et on doit bien avoir au moins 2 personnes a l’IA (enfin j’espere). Et si on compare la quantite/complexité du travail et les résultats, je pense que Xfennec s’en sort bien mieux. Apres reste a savoir si un comportement individuel est plus facile a coder qu’une intelligence de groupe, mais je dirais que rien qu’au niveau conception, ca me parait plus simple.

  8. Avatar de Xfennec
    Xfennec

    Wooden : J’ai effectivement passé quelques heures à me renseigner sur le sujet. Maintenant, il est clair que l’objectif du projet est bien de réaliser un "divertissement" pour Scopitone 2007 : j’ai réalisé plein d’approximations (comme les phéromones "orientées", par exemple), et tout ce que je souhaite, c’est que le résultat de la simulation, une fois ramenée en 3D et en temps réel, soit visuellement crédible. Je suis plus intéressé par les interactions entre le "joueur" et la simulation que par le réalisme scientifique de cette dernière 🙂

    Géhèm : Comme l’explique DindonPoilu, la création d’algos autour des concepts des colonies de fourmis existe depuis plus de 15 ans maintenant (1989 selon Wikipedia). Tu vas probablement trouver des tonnes de sources autour du sujet. Le code source du projet dont je parle ici est libre, ceci dit.

    En ce qui concerne le débat sur la qualité douteuse de l’IA dans une majorité des FPS, pour moi le problème n’est absolument pas technique … la 3D ne pouvant être qu’un prétexte. A mon sens, le simple fait que les RTS existent et puissent se jouer en solo est une preuve de ça … la complexité des règles du jeu des RTS est autrement plus poussée que sur un FPS, sans compter qu’il est très facile de contourner les limitations de l’IA dans un FPS (en rendant les tirs de l’IA très précis, par exemple).

    Non, je pense sincérement que les développeur **ne veulent pas** avoir des IA bien développées dans leurs FPS, pour une raison que j’ignore. Je suis pas développeur pro de jeux vidéo, je n’ai aucune formation particulière dans le domaine de l’IA, et pourtant lorsque j’ai eu a réaliser un certain nombre d’IA pour mes jeux (et voire même pour d’autres types d’applications, de rares fois), je ne me suis jamais retrouvé face à des problèmes insurmontables … Et la documentation sur le sujet est gigantesque. Définitivement, les IA de merde sont voulues.

  9. Avatar de NecroDragon
    NecroDragon

    @Llyd : oui mais là son programme est dans un référenciel 2D, à moins que les fourmis ne puissent escalader les objets et que j’ai mal compris

  10. Avatar de Xfennec
    Xfennec

    NecroDragon : il est très facile de projeter un monde 3D sur un plan (c’est ce qui va se passer ici), voire plusieurs. Les "falaises" doivent juste êtres considérés comme des obstacles. Je parie ma chemise que la quasi totalités des FPS font de même.

  11. Avatar de DindonPoilu
    DindonPoilu

    Dans un rts on lutte à armes égales contre l’ordinateur (une armée contre une armée), mais dans un fps on est seul contre tous. Si les ennemis sont trop intelligents dans un fps, on est foutu.

  12. Avatar de Wooden
    Wooden

    Ok, Xfennec.
    Ça me fait penser à un concours au Japon – dont honteusement j’ai oublié le nom – où les participants doivent coder une intelligence artificielle qui devra affronter une autre intelligence artificielle (celle d’un autre participant). La bataille a lieu entre deux groupes d’anti-corps composés d’une certaine hiérarchie un peu comme aux échecs à l’intérieur d’un patient malade.
    Je me souviens plus si le but premier est de tuer le roi adverse ou de soigner le patient par contre. Je chercherai si j’ai le temps.

    Sinon, pour l’IA dans les jeux video, il doit bien y avoir quelques problèmes techniques.
    Ça marche souvent comme ça dans un domaine: au début c’est facile, on avance rapidement, on développe rapidement mais après, c’est de plus en plus difficile de révolutionner le secteur, d’avancer de façon significative. Et je suppose que c’est d’autant plus vrai pour la pensée, qui reste un phénomène inexpliqué par la science.
    J’avais lu que l’on pensait pouvoir simuler un cerveau humain avec un ordinateur quantique de 100 qbits. Cela correspond à une puissance hors norme.

    Et puis, peut être quelques considérations marketing. A quoi sert de développer l’IA si on peut vendre seulement avec beaucoup de polygones ?

  13. Avatar de QQQ
    QQQ

    Trop bien ce blog!

    Désolé Xfennec j’ai pas eu (pris) le temps de te répondre sous ton forum mais je t’ai bien compris. Pour l’instant je vais me contenter de suivre l’évolution de ton boulot via ce blog.

    plus’

  14. Avatar de handsome
    handsome

    L’ia d’un FPS est autrement plus compliqué qu’une entité qui tombe face à un obstacle ou pas (un "non" ou un "oui") pour schématiser. Un pnj est censé réagir en fonction des actions , certes limitées par le jeu, mais toujours trés nombreuses d’un être humain, qui est un générateur de chaos assez balèze. L’Ia de FEAR est franchement bien même si pas parfaite.
    Et, ouais, je pense aussi que les devellopeurs s’abstiennent souvent de develloper qqe chose de vraiment poussé: ils privilégient l’action bien bourrine, et rien de tel que des hordes d’ennemis débiles qui rushent sous les balles pour ça.
    Des fps avec une vraie AI réaliste, ça pourrait vite être chiant: on retrouverait des phénomènes de camping comme avec les vrais humains Online, comme dans les vraies guerres quoi.
    Ou alors ça amènerait une ère où les héros de fps ne devraient plus systèmatiquement progresser chez les méchants, mais au contraire, *empècher* la progression des méchants, qui là, se devraient d’être agressifs et donc, un peu "cons", puisqu’ils devraient prendre de gros risques que le joueur ne manquera pas de punir assez vite vu ses über armes à über dégats et sa über Santé 10 fois plus importantes que l’ennemi…

    L’ia de Gears of War est pas trop mal par exemple, et souvent, on se retrouve face à un ennemi qui planque comme un porc et se penche de son cover toutes les 30 secondes pour balancer une rafale pendant moins d’une seconde et se recacher direct pour 30 secondes: c’est parfois *trés* lourd.

Laisser un commentaire