GeneticInvasion : des algorithmes évolutionnaires pour un meilleur jeu

45
3
sept.
2011
Jeu

Je m’en vais vous annoncer ici la sortie de version bêta 0.4 du jeu GeneticInvasion, pour lequel j’ai activement participé au développement.

L’idée me trottait dans la tête d’adapter la théorie de Darwin sur l’évolution pour créer un jeu où les ennemis s’adapteraient au comportement du joueur. Les jeux de type tower defense me paraissaient tout adaptés à cela. Aussi je proposais le sujet en tant que projet de fin de semestre à mon école d’ingénieur. J’ai trouvé trois collègues partants pour l’aventure et un tuteur spécialisé dans les algorithmes génétiques.
J’ai donc découvert que j’étais très loin d’être le premier à avoir l’idée d’informatiser la théorie de l’évolution, que c’était tout un domaine de recherche informatique et que cela s’appelait les algorithmes évolutionnaires.

Comment cela fonctionne‐t‐il ?

L’objectif d’un algorithme évolutionnaire est de trouver une bonne solution à un problème en un temps raisonnable ; il ne trouve pas nécessairement la meilleure solution, et pas nécessairement la même à chaque exécution. Comme dit plus haut, le fonctionnement est basé sur la théorie de l’évolution :

  • on génère une population de solutions aléatoires ;
  • on évalue les solutions sur le problème, afin de voir si elles correspondent. En fonction du résultat, on leur donne une note (« fitness » dans le jargon) ;
  • on sélectionne, en fonction du fitness, un certain nombre d’individus pour la reproduction ;
  • on effectue alors les croisements et des mutations aléatoires ;
  • les solutions filles viennent remplacer leurs parents dans la population, et l’on peut de nouveau procéder à une évaluation ;
  • on s’arrête quand un critère de fin a été atteint, qui définit à quel point une solution doit être bonne pour que l’on arrête de chercher.

Il existe de multiples algorithmes de sélection, de croisement (il ne se font pas tous à deux !) et de mutation.

Nous avons donc utilisé une bibliothèque C++ libre gérant les algorithmes évolutionnaires — sérieuse et destinée à la recherche —, afin de développer un jeu de tower defense (elle s’appelle EO pour Evolving Objects).

Le problème :

  • une évaluation = 1 round ;
  • nombre de solutions (ennemis) dans la population : 20 au maximum.

Ce sont des conditions très inhabituelles pour un algorithme évolutionnaire, que l’on utilise habituellement sur une grande population en faisant des tas de générations par seconde.

Après avoir infructueusement essayé de faire fonctionner l’algorithme dans ces conditions, nous avons dû renoncer et faire tourner l’algorithme en parallèle sur des rounds simulés : l’algorithme travaille donc maintenant sur une population de 500 ennemis, même si 20 seulement sont envoyés au joueur. Et pour chaque round réel nous en simulons deux (avant, on avait besoin d’en faire plus, mais suite à l’amélioration de notre choix de fitness, ça évolue suffisamment vite pour n’en faire que deux).

Une fois le projet fini, le jeu n’était pas réellement intéressant à jouer, car nous avions été accaparés par la partie configuration de l’algorithme évolutionnaire et simulation des rounds. J’ai donc travaillé un peu cet été sur l’équilibrage du jeu, et j’ai enfin obtenu quelque chose qui est rigolo à jouer, d’où cette version 0.4. Il y a 3 cartes classées par difficulté, et un système de médailles bronze/argent/or attribuées selon le nombre de rounds tenus.

Veuillez suivre les liens ci‐dessus pour voir une démo du jeu, télécharger les sources, se renseigner sur EO… Si quelqu’un prend le temps de faire une version compilée ou un paquet pour une quelconque distribution, je serai ravi d’héberger ça sur le site officiel.

Veuillez pardonner toute erreur ou approximation commise au cours de cette dépêche, je suis encore loin d’être expert en algorithmes évolutionnaires, nous n’en avons vu que les grandes lignes.

  • # coquille

    Posté par (page perso) . Évalué à  8 .

    hum, l'équipe de modération a mal compris, j'avais écrit "ennemis/solutions" parce que chaque ennemi est une solution, ils ont traduit ça par "nombre d’ennemis par solution dans la population".

    Si un modérateur peut corriger? (quelque chose comme "nombre de solutions (ennemis) dans la population")

    Cela dit, en effet une autre approche possible aurait été de considérer l'ensemble des ennemis comme une solution, ce serait possible maintenant que les évaluations sur font par simulation de manière asynchrone. (on évaluerait différents ensembles de 20 ennemis)
    Ce serait intéressant parce qu'on pourrait converger vers des salves d'ennemis avec des rôles : des gros lents devant et des petits rapides derrière, par exemple.
    Mais par contre on s'éloignerait du coté "l'espèce évolue en réaction à vos défenses" puisque qu'on ne ferait plus évoluer des individus mais des ensemble d'individus, on s'éloigne donc un peu de la théorie de Darwin.

    • [^] # Re: coquille

      Posté par (page perso) . Évalué à  3 .

      on s'éloignerait du coté "l'espèce évolue en réaction à vos défenses" puisque qu'on ne ferait plus évoluer des individus mais des ensemble d'individus

      En revanche ça pourrait être plus marrant pour le jeu. Comme si un général ennemi intelligent modifiait ses troupes.

      "La liberté est à l'homme ce que les ailes sont à l'oiseau" Jean-Pierre Rosnay

      • [^] # Re: coquille

        Posté par . Évalué à  8 .

        Ah, on prévoit un mod 'intelligent design' pour une prochaine version ? ;)

    • [^] # Re: coquille

      Posté par . Évalué à  4 .

      Si un modérateur peut corriger? (quelque chose comme "nombre de solutions (ennemis) dans la population")

      Fait.

  • # Téléchargements

    Posté par . Évalué à  2 .

    Tout d'abord félicitations pour le travail, la vidéo à l'air génial. Par contre, il n'y a aucun fichier sur la page de téléchargement.

    • [^] # Re: Téléchargements

      Posté par (page perso) . Évalué à  6 .

      Oui, d'où mon appel "Si quelqu’un prend le temps de faire une version compilée ou un paquet pour une quelconque distribution, je serai ravi d’héberger ça sur le site officiel."

      On a pas fait de version binaire, il faut aller dans l'onglet source, télécharger les sources et compiler à la main. (d'où le lien vers les instructions de compilation dans la dépêche)

      Promis, pour la prochaine version, on fait un make install qui fonctionne pour pouvoir faire des paquets plus facilement.(Je ferais un paquet aur dès que le make install fonctionne)

      • [^] # Re: Téléchargements

        Posté par (page perso) . Évalué à  6 .

        Juste une remarque.
        Comme vous semblez utiliser CMake comme outils de build.
        Essayer CPack pour construire des paquets binaires,
        une fois que les règles d'install sont OK, un coup
        de

        cpack -G RPM devrait construire un RPM
        cpack -G DEB un paquet debian
        cpack -G TGZ une archive binaire dans un TGZ etc...

        ça dépend des outils installés sur la machine de dév
        et de quelques variables CPACK_xxx à rajouter dans le CMakeLists.txt
        principal mais ensuite c'est assez simple.
        cf: http://www.cmake.org/Wiki/CMake:Packaging_With_CPack#Using_CPack_with_CMake

    • [^] # Re: Téléchargements

      Posté par . Évalué à  5 .

      Ok, il faut aller à source, un petit tar.gz ça aurait été cool.

      • [^] # Compilation sur Ubuntu (devrait être compatible Debian)

        Posté par (page perso) . Évalué à  2 .

        Sur Ubuntu (peut-être sur Debian aussi), pour compiler il faut installer :
        libsfml-dev (dans les dépôts)
        libglui-dev (dans les dépôts)
        la lib eo : http://eodev.sourceforge.net/ possède un .deb pour la version 1.2 à l'heure de ce message

        Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

      • [^] # Re: Téléchargements

        Posté par . Évalué à  2 .

        oui, c'est plus facile de faire des paquets sources (par exemple pour AUR). J'utilise Archlinux, comme l'auteur apparemment, et j'ai installé les diverses dépendances, néanmoins ça ne compile pas :

                     from /tmp/genetic-invasion-master/src/game/Application.cc:22:
        
        

        /usr/include/eo/apply.h:92:0: attention : #pragma omp parallel ignoré [-Wunknown-pragmas]
        /usr/include/eo/apply.h:110:0: attention : #pragma omp parallel ignoré [-Wunknown-pragmas]
        In file included from /tmp/genetic-invasion-master/src/game/Game.hh:30:0,
        from /tmp/genetic-invasion-master/src/game/Application.hh:28,
        from /tmp/genetic-invasion-master/src/game/Application.cc:22:
        /tmp/genetic-invasion-master/src/game/Controls.hh:45:9: erreur: ‘Key’ in namespace ‘sf’ does not name a type
        /.../
        /tmp/genetic-invasion-master/src/game/Game.hh:56:36: erreur: ‘class sf::Rect’ has no member named ‘Right’

        etc.

        un binaire statique, compilé avec une vieille distribution (genre Debian), ça serait pratique pour voir rapidement le jeu.

        Parfois, les 15 minutes passés à chercher comment compiler le truc, ça peut aussi faire partie du jeu...

        Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

        • [^] # Re: Téléchargements

          Posté par (page perso) . Évalué à  3 .

          J'ai fait un paquet aur :-)
          On dépend de la SFML dans sa version 1.6 et non 2.0 qui est dans les dépôts arch (alors que la 2.0 est encore en beta, mais la 1.6 est plus maintenue, un beau foutoir…)

          Il te faut donc user de la ArchRollbackMachine pour downgrader sfml. (et peut-être glew aussi)
          Ça se passe là : http://arm.konnichi.com/search/index.php?a=32&q=sfml&core=1&extra=1&community=1

          Ensuite tu peux installer le tout nouveau paquet aur.

          • [^] # Re: Téléchargements

            Posté par . Évalué à  3 .

            super, ça fonctionne bien. Le concept est très intéressant.

            J'adore vraiment la musique, du coup j'ai téléchargé l'album sur son site (dommage, il me semble que jamendo ne propose maintenant plus qu'en torrent, mais sans seeder donc impossible à télécharger, l'auteur propose un autre torrent qui fonctionne).

            Pour le jeu, c'est pas évident, et un peu frustrant de les voir marcher sur l'herbe pour venir nous bouffer, alors qu'au début ils ne le faisaient pas :)

            Quelques remarques comme ça :

            • parfois ça va un peu vite pour comprendre tout ce qui se passe. Vu que ça un peu une vocation pédagogique, ça serait bien de pouvoir optionnellement modifier l'allure des attaques et la vitesse des ennemis (quitte à synchroniser avec la vitesse des tirs pour ne pas pénaliser l'attaquant)

            • j'adore la musique (ah oui je l'ai déjà dit...)

            • j'aime bien les graphismes pixellisés (surtout avec la musique, que j'adore, cela dit en passant) en revanche je trouve que ça manque un peu de parti pris, par exemple je trouve un peu dommage de mélanger des graphismes avec de gros pixels et de plus petits pixels, à la rigueur ça fait un peu « pas fini », il serait donc de bon ton, soit de passer tout en pixels plus fin (comme les monstres), soit de simplifier les monstres. Éventuellement d'adapter les couleurs pour que cela contraste plus. Idem pour les polices.

            • Ça serait bien d'avoir une aide en ligne, la signification des tours en particulier

            En tout cas, bravo pour ce travail !

            Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

            • [^] # Re: Téléchargements

              Posté par (page perso) . Évalué à  4 .

              Ils ne marchent pas sur l'herbe, ils volent :P

              Pour l'explication en ligne des tours effectivement, je tâcherai d'ajouter ça dans la partie documentation du site officiel. (en attendant, voir mon commentaire plus bas)

              Pour le fait de pouvoir ralentir le jeu je sais pas trop, c'est un peu triché quand même :D
              Par contre à terme il faudrait un tutoriel sympa qui explique comment jouer toussa. Mais c'est super relou à développer un tutoriel.

              • [^] # Re: Téléchargements

                Posté par . Évalué à  2 .

                j'ai continué à jouer, c'est bien amusant.

                Encore quelques remarques :

                pour faire une herbe plus sympathique, il faudrait forcément avoir plus que 3 tuiles pour l'herbe / le chemin / la roche. Je ne sais pas trop comment ça se fait d'habitude, prévoir par exemple une tuile herbeuse avec 1 côté de roche, une autre avec 2 côtés, puis 3 côtés de roche etc, avec diverses rotations possibles. Ça va être plus compliqué à programmer.

                Pour les ennemis, je trouve qu'il est difficile de les distinguer, et surtout de comprendre du premier coup d'oeil leur fonction. Certains volent, d'autres rampent uniquement sur les chemins, mais les troisièmes, qu'ont-ils de particulier ?

                Si ça vous intéresse, je veux bien essayer de regarder pour faire des graphismes en pixel-art, avec vos conseils et direction.

                Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

                • [^] # Re: Téléchargements

                  Posté par (page perso) . Évalué à  2 .

                  La couleur des ennemis dépend de leur vitesse.
                  Le skin dépend de la taille (pour les terrestres, les volants ont tous le même)

                  Effectivement avoir une map plus jolie serait cool mais nécessite beaucoup de code et de réflexion pour avoir un système pratique.
                  Faudrait que je lise sur le sujet, je sais qu'il y a des explications qui traînent sur le net.

                  Si tu veux t'essayer au pixel art, il nous faut un logo pour remplacer celui affiché dans le menu principal.
                  Il me faudrait aussi des médailles bronze/argent/or à afficher dans le menu à coté du nom du niveau.
                  J'aimerai garder les skins des ennemis je les aime bien, ils viennent de là : http://opengameart.org/content/colorize-enemies#comment-7040
                  Le skin des gros ennemis est pas top, je le remplacerai si le gars répond à mon appel à colorisation pour le nouveau sprite (voir commentaires sur le lien ci dessus)
                  Pour la map je crois que tu pourras pas faire grand chose tant que coté code on aura pas un truc permettant de mieux gérer les bords de tiles et les variations parmi plusieurs tiles d'un même type.

                  • [^] # Re: Téléchargements

                    Posté par . Évalué à  3 .

                    J'avais envie de tester des sprites style insectes, voici ce que j'ai fait :
                    Titre de l'image

                    J'ai réalisé des tourelles mais elles ne sont pas super, j'ai fait un logo pour le menu principal mais c'est à partir des sprites d'insectes, voici l'archive avec les images modifiées :
                    http://dl.free.fr/mPstmGRqi

                    Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

                    • [^] # Re: Téléchargements

                      Posté par . Évalué à  3 .

                      j'ai remarqué qu'on pouvait augmenter la résolution de l'herbe en passant en 32x32 comme pour les sprites, mais du coup ça modifie les réactions du jeu et le placement des tourelles

                      Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

            • [^] # Re: Téléchargements

              Posté par . Évalué à  1 .

              Pour tous ceux qui apprécient les musiques 8bit et jamendo, je conseille :
              NESessity - The Heartbits
              Kangaroo Musique - The Alan Sugar Trash Orchestra

              • [^] # Re: Téléchargements

                Posté par . Évalué à  2 .

                c'est super NESessity...

                savez-vous s'il y a moyen de faire un téléchargement direct en OGG sur jamendo ? Leur bittorrent ne fonctionnent pas du tout, ils pourraient au moins seeder les fichiers d'origine.

                Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

                • [^] # Re: Téléchargements

                  Posté par (page perso) . Évalué à  3 .

                  Oui : http://userscripts.org/scripts/show/48019
                  C'est un script greasemonkey qui remplace le bouton télécharger de jamendo par celui pour chopper le ogg en direct download.

                  Pour ceux qui est des deux albums postés, j'écouterai mais la licence n'est pas libre donc je pourrais pas les utiliser dans mes jeux :P

  • # Eo fail

    Posté par (page perso) . Évalué à  4 .

    Bon, je n'arrive pas a compiler EO (et apparemment c'est une erreur dans le code), donc je ne pourrais pas tester. Mais au vu de la vidéo ça a l'air assez intéressant.

    Connais-tu d'autres jeux qui « apprennent » ?

    Il existe deux catégories de gens : ceux qui divisent les gens en deux catégories et les autres.

    • [^] # Re: Eo fail

      Posté par (page perso) . Évalué à  3 .

      Non je n'en connais pas d'autre.
      À part peut-être sur des jeux de plateaux comme les échecs.

      À l'origine je pensais que le concept serait très facile à adapter à tous les jeux avec un fonctionnement par vagues, comme par exemple les survivals horror.
      Mais au final comme on a du simuler des rounds pour s'en sortir c'est une mauvaise nouvelle : on ne peut pas simuler de round sur un survival horror. (Je pense par exemple à violetland, ou à des FPS comme killing floor (non-libre))

      Pour le soucis de compilation d'EO, peux-tu remonter le bug si c'en est un?
      (L'auteur des geekscottes travaille sur EO en plus :P)
      Note : EO propose des paquets 64bits pour debian, et est également disponible dans aur.

    • [^] # Re: Eo fail

      Posté par (page perso) . Évalué à  2 .

      Connais-tu d'autres jeux qui « apprennent » ?

      Dark Reign, si je me souviens bien avait une IA qui apprenait et qui s'adaptait au comportement du joueur.

      • [^] # Re: Eo fail

        Posté par . Évalué à  3 .

        Dark Reign était sympa, mais il a beaucoup souffert de la proximité (temporelle) de la sortie de Starcraft (premier du nom). C'est dommage, il était plutôt bien foutu (rien à voir avec DarkReign 2, d'ailleurs).

        • [^] # Re: Eo fail

          Posté par (page perso) . Évalué à  2 .

          Ah moi je pensais plutôt que c'était à cause de la sortie de Total Annihilation qu'il a eu moins de succès.

          • [^] # Re: Eo fail

            Posté par . Évalué à  2 .

            Si je me souviens bien, TA est sorti avant et a effectivement mis la barre assez haut. Mais Dark Reign, bien que ne proposant pas de vrai 3D, ne s'en sortait pas si mal de ce point de vue (l'artillerie n'était pas si mal foutue et tenait compte du relief, notamment).

            Par contre, la déferlante Starcraft a fait qu'assez rapidement, n'a plus existé qu'un seul RTS...

      • [^] # Re: Eo fail

        Posté par (page perso) . Évalué à  3 .

        Spring RTS (également libre) a certaine AI qui apprennent d'une partie a une autre, certaines gardent des cartes en niveau de gris selon là ou il y a eu des impacts de tirs. Cela fait deux trois que je n'y ai pas joué mais je me souviens encore avoir été surpris de voir au bout de la deuxième partie, l'ordinateur contourner ma ligne de défense habituelle (oui moi je n'apprends pas) et faire évolué la composition de ses escadrons.

    • [^] # Re: Eo fail

      Posté par (page perso) . Évalué à  1 .

      Conflict Zone et son moteur DirectIA (sorti en 2001).

  • # Question naïve

    Posté par (page perso) . Évalué à  4 .

    de quelqu'un qui n'a pas joué :
    Est-ce que l'emploi d'un IA utilisant un algorithme génétique pose les mêmes problèmes que l'évolution réelle ? C'est-à-dire optimisation du comportement pour une situation, au dépend de la polyvalence ? Au risque qu'un joueur malin choisisse volontairement de changer radicalement de comportement pour balayer des adversaires trop spécialisé. Un peu comme ce qui se produit quand on introduit des rats dans une île peuplée uniquement d'oiseaux ?

    • [^] # Re: Question naïve

      Posté par (page perso) . Évalué à  4 .

      Oui, ça pose le même genre de soucis dans le jeu, si on laisse les ennemis passer sans poser de tours le premier round, les générations suivantes seront lentes. (Plus un ennemi est lent plus il inflige de dégâts, donc l'évolution favorise les ennemis les plus lents parmi ceux qui vont jusqu'au bout)

      Il me semble qu'avec les derniers réglages en terme de mutation, l'évolution finira quand même assez vite par repartir dans le bon sens une fois que le joueur pose des tours.

      C'était aussi une des choses inhabituelles pour un algorithme évolutionnaire : avoir un problème qui change au court du temps. Ça oblige à avoir un haut taux de mutation pour avoir la diversité nécessaire à l'adaptation au nouveau problème.

      Cela dit cet effet de bord reste difficilement exploitable dans le jeu, par contre si le jeu permettait de détruire des tours, on pourrait vite voir des stratégies de joueurs tordues permettant d'orienter l'évolution dans le mauvais sens.

      • [^] # Re: Question naïve

        Posté par . Évalué à  2 .

        J'allais le dire, la gestion des ressources (argent généralement dans un tower defense) est un garde fou à ce genre de truc non ?

        • [^] # Re: Question naïve

          Posté par (page perso) . Évalué à  2 .

          Non, c'est surtout le fait de ne pas pouvoir détruire les tours qui sert de garde fou.
          On ne peut pas remplacer toutes ses tours par d'autres, ou toutes les enlever pour perturber l'IA.

          Je pense que si on pouvait détruire/remplacer des tours, alors il faudrait effectivement regarder du coté des crédits pour limiter les débordements.

      • [^] # Re: Question naïve

        Posté par . Évalué à  2 .

        Pour avoir lu sur le sujet, j'ai compris que la codage des chromosomes est primordial. L'important est d'avoir des solutions partiels. Par exemple, dans le cas simpliste de trouver le chemin d'un labyrinthe, on peut avoir 3 codages différents de chromosomes :un truc bête qui donne une direction par case du labyrinthe, une série de direction depuis l'entrée (droite-gauche-tout droit), une direction selon la forme locale du labyrinthe.

        Le meilleur codage est le codage stupide. Parce que si on prend la moitié du chromosome, dans la version stupide, on a bien une moitié de solution. Dans le cas de la série, une mutation change complètement la direction prise. idem dans la reconnaissance local.

        Les chromosomes peuvent aussi avoir de zones qui peuvent être désactivé mais conserve une ancienne solution utile si l'environnement change.

        "La liberté de tout dire, n'a d'ennemis, que ceux qui veulent se réserver, le droit de tout faire"

  • # Test

    Posté par . Évalué à  2 .

    Voilà, j'ai testé le jeu (sous slackware64-current) et je tiens à préciser que je ne connaissais pas du tout ce genre de jeux. Ça se joue bien et c'est asses addictif. On voit réellement l'AI évoluer au cours du jeu. Par contre, j'ai l'impression que sur les 3 types de tours, il n'y a que la première qui fonctionne. C'est domage car l'adversaire évolue lui :)

    J'ai réussi à aller jusqu'au niveau 18 sur la carte rocks mais je n'ai pas vraiment trouvé la stratégie. Je fais des paquets de tours d'abord près de l'entrée, puis petit à petit vers la sortie.

    • [^] # Re: Test

      Posté par (page perso) . Évalué à  2 .

      Explication sur les 3 types de tours:
      - La jaune est la plus simple : elle coûte 100 crédits, tire sur tout ce qui bouge, plutôt lente.
      - Celle a une bouche est une tourelle de proximité : Elle touche au contact, elle touche à tous les coups, mais uniquement les ennemis terrestres. Elle recharge lentement. Elle coute 200 crédits
      - La dernière est la tourelle anti-air : Elle tire uniquement sur ce qui vole, ses projectiles sont rapides et sa cadence de tir est élevée. Forcément les projectiles font individuellement moins de dégât. Elle coute 200 crédits.

      Passe ta souris sur une tourelle déjà posée pour voir sa portée.

      Regarde dans le fichier src/Turret.cc si tu veux voir les valeurs exactes. (dégât, portée, …, c'est en haut du fichier, normalement c'est suffisamment commenté.)

      18 tours sur rocks c'est vachement bien, moi je plafonne à 16 en général. T'es pas loin de la médaille d'or qui est à 20 rounds.
      Ma stratégie consiste à faire un labyrynthe de tours jaunes pour avoir les terrestres, ensuite ça évolue vers du volant et je blinde en tours anti-air un peu de partout. Mais bon, ça marche pas terrible xD

      • [^] # Re: Test (spoil)

        Posté par . Évalué à  2 .

        ok, merci.

        Alors du coup, voilà ma stratégie pour finir niv. 36 à path et 33 à rock (encore un aprèm à rien faire) :
        -construire sa défense au milieu de la carte comme ça les méchant ne développent pas leurs vitesses
        -au-début que des jaunes (5-6)
        -puis une ou deux tour anti-air pour éviter qu'ils se développent là dedans
        -petit à petit construire un chemin d'hérissons
        -blinder la carte d'anti-air et de jaune près des hérissons

        Bref, il faut vraiment tenir compte de l'évolution de l'ennemie. Vraiment cool.

        • [^] # Re: Test (spoil)

          Posté par (page perso) . Évalué à  4 .

          Wow, 33 et 36, ok, faut que je m'entraine.
          Et du coup ptet que je prévois d'autre niveaux de difficulté.

          Note : Si tu atteins le round 50 le jeu t'accusera de tricher.

          • [^] # Re: Test (spoil)

            Posté par . Évalué à  8 .

            Au niveau 54 il te dit que tu as changer le code source :)

            • [^] # Re: Test (spoil)

              Posté par (page perso) . Évalué à  3 .

              Hum, effectivement, je viens de tester, ya un gros bug dans l'évolution de la vitesse si on ne met pas de tours près du spawn.

              Il va falloir retoucher la simulation ou la fitness. (plutôt la simulation je pense)

              Attends toi à ne plus pouvoir utiliser la même astuce dans la prochaine version :-P

              • [^] # Re: Test (spoil)

                Posté par . Évalué à  2 .

                En même temps, c'est normal. S'il n'y a pas de tours près du spawn, ce ne sont pas les plus rapides qui vont le plus loin et la vitesse ne joue pas un rôle important.

                Attends toi à ne plus pouvoir utiliser la même astuce dans la prochaine version :-P

                Du coup, je ne te donnerais pas mes autres astuces :)

                Par contre, j'ai essayé de faire un paquet pour slackware, mais le soucis c'est qu'il n'y a pas evo et qu'il a l'air pénible à empaqueter.

                Voici the quick and dirty way pour une installation sous slackware :
                - installer SFML depuis slackbuilds.org (sbopkg -i SFML)
                - télécharger eo, créer un package avec src2pkg EO-1.2.0.zip et l'installer.
                - suivre les instructions sur GeneticInvasion

                Cette installation a été testée sous la version 64-current.

                • [^] # Re: Test (spoil)

                  Posté par (page perso) . Évalué à  2 .

                  Toute technique permettant de dépasser le niveau 50 est à considérer comme un bug :P

                  Et non ce n'est pas normal qu'il n'évolue pas vers plus rapide, plus un ennemi est rapide moins il reste longtemps exposé au feu des tours et donc normalement il va plus loin. Il faut que je relise le code de la simulation, il y a un soucis quelque part.

                  Les ennemis sont évalués indépendamment dans la simulation, donc ya pas d'effet de bord du type "les plus rapides prennent les coups à la place des plus lents"

                  • [^] # Re: Test (spoil)

                    Posté par . Évalué à  1 .

                    Ne t'inquiète pas, ils évoluent vers plus rapide.

                    C'est juste qu'au début ce ne sont pas les plus rapides qui vont le plus loin c'est même le contraire. Comme les tours sont loin, ce sont d'abord les plus rapides qui y arrivent et qui se font dégommer en premier. Pendant que les tours sont occupées par les petits, les plus gros et plus lent peuvent aller plus loin. Enfin, c'est comme ça que j'ai réfléchi.

                    Par contre, je pars d'un postulat qui est peut-être faux, c'est qu'il y a évolution à partir du round précédent.

                    • [^] # Re: Test (spoil)

                      Posté par (page perso) . Évalué à  2 .

                      Non, l'évolution est faite sur une simulation en parallèle.
                      Dans la simulation, les ennemis sont évalués individuellement. Donc "Pendant que les tours sont occupées par les petits, les plus gros et plus lent peuvent aller plus loin.", ça ne fonctionne pas.

                      L'évolution n'est pas basée sur le résultat des rounds mais celui des simulations. (Et ça a beaucoup amélioré les choses, durant un vrai round l'ordre de passage compte beaucoup, les gros protègent les petits, les rapides se font dégommer en premier, …)

                  • [^] # Re: Test (spoil)

                    Posté par (page perso) . Évalué à  4 .

                    Toute technique permettant de dépasser le niveau 50 est à considérer comme un bug :P

                    Alors j'en ai trouvé un de très sérieux. Dans tous mes essais, soit je ne dépasse pas les niveau 10 à 15, soit plus aucun ennemi n'arrive à franchir mes défenses et ceci indéfiniment. En général, les chiffres qui s'affichent sur la droite sont toujours les mêmes. L'algorithme semblant hésité entre deux solutions sensiblement équivalentes de mon point de vue. Sa se termine avec le terrain rempli de tours et une coupure de courant, un bug de l'interface ou un arrêt manuel du programme. Il faudrait peut-être envisager de limiter le niveau qui peut être atteint ?

                    Un des problèmes que j'ai rencontré est la dépendance (apparente ?) du jeu à la fréquence du processeur. Cela semblait quasiment injouable quand je laissais les cœurs sur "ondemand". En forçant un cœur à 3 GHz, le jeu a soudain gagné grandement en jouabilité. Je me demande si l'issu d'un round dépend ou non de la capacité de calcul ou d'affichage de la machine ?

                    Enfin, une dernière remarque : si j'ai pris beaucoup de plaisir à jouer, il me semble que le problème que l'algorithme tente d'optimiser et les solutions qu'il choisi ne sont pas assez claire pour le joueur. Peut-être faudrait-il ralentir le rythme pour laisser plus de temps d'observation, donner plus d'informations au joueur, etc. De la sorte cela permettrait de jouer vraiment avec l'algorithme pour essayer de le piéger. Tel que, si je n'avais pas lu la nouvelle j'aurais seulement eu l'impression d'affronter des vagues d'adversaires aléatoires de plus en plus puissants …

                    En tous cas joli travail. Bravo.

                    • [^] # Re: Test (spoil)

                      Posté par (page perso) . Évalué à  2 .

                      Hum, je suppose que ce n'est pas avec la dernière version du git?
                      La dernière version du git, personne ne m'a encore rapporté avoir dépassé le niveau 50.

                      Ya aucune raison que le jeu dépende de la vitesse du processeur, à moins que celui ci ne soit vraiment très lent. Si c'est un vrai bug faudra qu'on investigue, je vois pas du tout d'où ça peut venir.

                      Pour finir l'objectif est quand même de faire un tower defence, le joueur se défend contre des vagues d'ennemis qui évoluent, il n'est pas censé comprendre toutes les subtilités de l'algorithme.

                      • [^] # Re: Test (spoil)

                        Posté par (page perso) . Évalué à  2 .

                        J'ai pris la version d'hier avec git …
                        Mon processeur est un phenom X4, avec une puce graphique intégrée.

                        • [^] # Re: Test (spoil)

                          Posté par (page perso) . Évalué à  2 .

                          Finalement j'avais tort : en prenant la version git du jour d'hui — qui rend les choses sensiblement plus compliquée — après 150 tours tous strictement identiques l'algorithme a fini par se débloquer au 208ème. Les logs indiquent tout de même zéro survivant de l'étape 46 à la 191ème. Peut-être est-ce en partie ce qui explique que l'algorithme ai eu tant de mal a trouver une solution ?

                          • [^] # Re: Test (spoil)

                            Posté par (page perso) . Évalué à  3 .

                            Oui effectivement d'autres personnes m'ont signalé pourvoir dépasser le round 50 sur le premier niveau, même avec la dernière version :-/
                            Il va falloir que je ré-examine la simulation, visiblement elle a encore quelques soucis.

                            Je sais pas quand j'aurai le temps de regarder ça, ça demande pas mal de debug mais je trouverais peut-être la motivation pour le faire prochainement. J'ai zarmakuizz qui fait des tests intensifs et me tient au courant ^^

                            PS : en attendant, jouez sur les 3 autres niveaux :-P

                            • [^] # Re: Test (spoil)

                              Posté par (page perso) . Évalué à  2 .

                              En l'occurrence c'était le niveau rocks. Le 3 ? De toutes façons il me semble qu'il n'est pas nécessairement pertinent d'augmenter encore le niveau de difficulté. Cela rendrait le jeu peu accessible. Et comme rapidement le joueur n'a plus aucune action possible, et même bien avant cela arrive l'instant où il ne reste plus aucun choix stratégique à réaliser, le mieux serait peut-être d'arrêter la partie après un certain nombre de rounds ? À moins d'enrichir les possibilités côté joueur ?

                              digression :
                              Il me semblait qu'il était possible d'envoyer un message privé à un autre utilisateur sur l'ancienne version de linuxfr ? Mais je suis incapable de retrouver cette possibilité !

            • [^] # Re: Test (spoil)

              Posté par . Évalué à  2 .

              s/changer/changé/g …

              Je me suis mélangé avec "tu as dû changer" …

        • [^] # Re: Test (spoil)

          Posté par (page perso) . Évalué à  3 .

          Une nouvelle version est disponible sur le git. Je n'arrive plus à dépasser le niveau 30 avec cette technique maintenant.

          Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

          • [^] # Re: Test (spoil)

            Posté par . Évalué à  1 .

            Ah oui, c'est bien plus dur. Dès le niveau 5 certains monstres arrivent à éviter les tours …

          • [^] # Re: Test (spoil)

            Posté par (page perso) . Évalué à  2 .

            Ouais, j'en suis plutôt satisfait.
            J'arrive encore à avoir l'or sur Leet, Rock et Emptiness (que j'ai du coup mis comme niveau 4).
            Faut que je retest Path mais je pense que ça va aussi.

            N'hésitez pas à faire des maps! (pour l'instant l'éditeur de map c'est vim :P)

          • [^] # Re: Test (spoil)

            Posté par (page perso) . Évalué à  3 .

            Niveau 163 en Leet, même avant j'atteignais pas ce score. \o/

            Technique similaire, la différence se trouve dans la gestion de l'argent (et donc des placements de tours).

            Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

          • [^] # Re: Test (spoil)

            Posté par (page perso) . Évalué à  2 .

            Test sur le niveau 4 Emptiness :
            Ben je vais laisser tourner le PC toute la nuit et on verra bien, là c'est à 184 et les ennemis n'ont toujours pas pu approcher le QG d'une distance de 5-6 cases en diagonale. Oh, 192. 193. 194… L'attente prend plus de temps que la ronde avec le x3. :)

            À mon avis ce niveau est plus facile que le 3 Rock.

            Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

            • [^] # Re: Test (spoil)

              Posté par (page perso) . Évalué à  2 .

              Finalement j'ai arrêté vers les 348, la situation changeait pas, et c'est pas écologique de faire mouliner un PC la nuit juste pour atteindre le 999.

              Stratégie assez simple donc je la dirai sur irc à MCMic.

              Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/

  • # CPack

    Posté par . Évalué à  4 .

    Concernant la génération de packages :
    Je viens de zieuter le dépôt, et je vois que vous utilisez CMake.
    Un simple :

    include(CPack)

    Dans ton CMakeLists.txt principal devrait te permettre de générer des .deb et des .rpm (au moins pour l'architecture sur laquelle tu compiles).

    Si ça peut aider ^^

    • [^] # Re: CPack

      Posté par (page perso) . Évalué à  2 .

      Voilà, le make install fonctionne, j'ai donc voulu tester cette histoire de cpack, ça râle :
      CMake Error at /home/mcmic/dev/GeneticInvasion/cmake_install.cmake:71 (FILE):
      file Internal CMake error when trying to open file:
      /home/mcmic/dev/GeneticInvasion/install_manifest.txt for writing.

      Je suis censé le créer moi ce fichier? Je met quoi dedans?
      Je trouve pas d'info sur le sujet sur les pages du wiki cmake qui causent de cpack.

      • [^] # Re: CPack

        Posté par . Évalué à  1 .

        Si j'en crois ce Lien , tu peux jouer sur la variable CPACK_SET_DESTDIR.

  • # Graphismes

    Posté par (page perso) . Évalué à  4 .

    Les graphismes type NES c'est un choix de style graphique ?

    • [^] # Re: Graphismes

      Posté par (page perso) . Évalué à  3 .

      Oui.
      On a fait avec ce qu'on a trouvé sur OpenGameArt (pas de graphiste dans l'équipe), moi j'aime bien le rendu au final.

      Le seul soucis c'est les tiles qui composent la map, notamment la rupture trop brute entre l'herbe et la terre. Mais c'est difficile de faire un système qui fait des bords jolis et qui rend bien dans les virages.
      Quoi qu'il arrive, même si ces tiles sont un jour remplacé, ce sera par d'autres tiles tout aussi pixelisés ;-)

      • [^] # Re: Graphismes

        Posté par (page perso) . Évalué à  3 .

        J'aime bien le style graphisme typé NES, même si perfectible comme dit dans un autre commentaire. Le retro-gaming est bien dans l'air du temps ; j'avais vu des images d'un jeu indépendant (et dont le nom m'échappe), où au fur et à mesure des upgrades les graphismes passent du 8-bits monochrome style GameBoy au 8-Bits style NES, puis 16-bits etc... Vu le peu de sprites de GeneticInvasion ça serait imaginable.
        On peut aussi imaginer avoir plusieurs front-ends. Si vous en faîtes un en 3D je veux bien faire vos graphismes (je me débrouille bien avec Blender).

        Bonne continuation.

  • # dépendances gentoo

    Posté par (page perso) . Évalué à  3 .

    Pour les gentooeux qui ont la flemme de chercher :
    Dépendances :
    * sci-mathematics/eo (dans l'overlay dev-zero)
    * media-libs/libsfml

  • # binaire statique ?

    Posté par . Évalué à  9 .

    Personne n'a fait de gros binaires statiques, pour les faignants qui ne veulent pas se farcir les dépendances ?

    "La liberté de tout dire, n'a d'ennemis, que ceux qui veulent se réserver, le droit de tout faire"

  • # préfixe de compilation

    Posté par . Évalué à  1 .

    Ça serait cool de supporter CMAKE_INSTALL_PREFIX pour les gens qui veulent builder sans polluer leur /usr/local... Si j'en crois la doc avec cmake c'est utilisé tout seul si tu utilises les macros FIND_*()

    • [^] # Re: préfixe de compilation

      Posté par (page perso) . Évalué à  2 .

      Heu, c'est le cas dans la dernière version git.
      Ou alors j'ai raté?

      • [^] # Re: préfixe de compilation

        Posté par . Évalué à  1 .

        JE suis une quiche en cmake, mais j'ai dû ajouter les lignes suivantes pour que cela fonctionne:

        diff --git a/CMakeLists.txt b/CMakeLists.txt
        index 3536250..7f2726b 100644
        --- a/CMakeLists.txt
        +++ b/CMakeLists.txt
        @@ -13,6 +13,8 @@ include_directories(/usr/include/eo)
         include_directories(/usr/include/eo/es)
         include_directories(/usr/local/include/eo)
         include_directories(/usr/local/include/eo/es)
        +include_directories(/opt/genetic/include/eo)
        +include_directories(/opt/genetic/include/eo/es)
         include_directories(src)
         
         SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY "A Tower Defence game that uses evolutionary algorithm")
        @@ -50,6 +52,7 @@ add_executable(GeneticInvasion
         add_executable(Test
             Test/Test.cpp)
         target_link_libraries(GeneticInvasion
        +    -L/opt/genetic/lib
             ${SFML_LIBRARY}
             ga
             eo
        
        

        Évidemment c'est tout pourri. Ou alors j'ai foiré quelque chose?

        Ceci dit, sympa le jeu, même si ça a tendance à faire crasher nouveau.

        • [^] # Re: préfixe de compilation

          Posté par (page perso) . Évalué à  2 .

          Ben ya pas de module cmake pour EO, donc notre gestion de EO dans le cmake est minimale.
          Il faudrait faire un beau module cmake pour EO qui râle s'il le trouve pas et indique où il le trouve s'il le trouve. (comme on a pour la SFML)

          Je sais pas si c'est facile à faire.

          • [^] # Re: préfixe de compilation

            Posté par . Évalué à  1 .

            Il n'y a pas d'équivalent à AC_CHECK_LIBRARY?

            Avec les autotools ce genre de chose est triviale. La moindre des choses serait de pouvoir gérer un préfixe de compilation et aller y chercher les librairies (càd tester si libfoo.so existe et éventuellement s'il contient un symbole donné)

  • # IA vs IA

    Posté par . Évalué à  4 .

    Personne ne s'est lancé dans la réalisation d'une IA (éventuellement une qui évolue également) pour jouer les défenseurs contre l'IA initiale ?

    Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

  • # Step by step

    Posté par (page perso) . Évalué à  1 .

    Personne ne l'avait faite, je me dévoue pour la gloire de ma WiiBoard qui prend la poussière.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.