Pathfinding et collisions

Cet article date de 2013 ! Retrouvez une version mise à jour ici.

Aujourd'hui, un article qui envoie du lourd : je vous montre le nouveau prototype, et on fait le point sur les artworks !

Petites modifications

Avant de m'occuper des trucs costauds, j'ai corrigé les quelques petits détails que vous aviez signalés suite au précédent prototype.

Les touches

Les touches fléchées pour le déplacement, ce n'est pas le plus pratique ! Les joueurs ont plutôt l'habitude d'utiliser ZQSD, de façon à avoir les mains bien réparties sur le clavier. J'ai donc rajouté la possibilité de contrôler le personnage avec ZQSD, sans retirer les touches fléchées toutefois !

La taille du jeu

C'est vrai que le jeu était un peu petit. Comme on part avec l'idée de le diffuser gratuitement en ligne (à moins qu'on trouve un moyen de le diffuser "pour de vrai" : ce serait génial, non ?), je suis allée regarder les dimensions maximales acceptées sur Kongregate et Newgrounds, les deux plus gros portails de diffusion gratuite de jeux Flash. Verdict : 800 pixels de large sur Kongregate, et 942 sur Newgrounds. On part donc sur une taille de 800 x 600 pixels.

Autres réglages

Du coup, dans ce grand espace vide, le tir était un peu court : j'ai rallongé sa portée. Et le personnage était un peu grand : je l'ai rapetissé. La question du rebond sur les murs faisait débat, je n'y ai pas touché pour l'instant.

 Temps total pour cette étape : 5 minutes.

Collisions

Notre jeu a une grande composante stratégique. Le terrain n'est pas vide, loin de là : il comporte des obstacles qui vont inciter les ennemis - et le joueur - à passer par tel endroit plutôt qu'à tel autre... En fonction de la nature du terrain, le joueur va donc positionner ses alliés à un endroit plutôt qu'à un autre pour bénéficier d'un bon angle de tir, ou d'un emplacement efficace.

J'ai donc commencé par générer le terrain sous forme d'une grille, afin de pouvoir plus facilement placer les objets. Ensuite, sur cette grille, je positionne les obstacles à partir d'un tableau où je rentre leurs coordonnées (voir ci-contre). De cette façon, je pourrai générer un grand nombre de niveaux simplement en rajoutant des lignes dans mon tableau. Pratique, n'est-ce pas ?

 Temps total pour cette étape : 35 minutes.

Mais le fait que moi, je pense que ces rectangles sont des obstacles, ne veut pas dire que Flash pense que ces rectangles sont des obstacles. Le personnage passe allègrement au travers ! Il faut donc détecter la présence des obstacles, et lui dire de ne pas foncer dedans.

Comment on fait ça ? Eh bien, j'ai opté pour une "projection". En gros, imaginez que, quand vous appuyez sur la touche droite, le personnage tende sa main à 10 pixels sur la droite. S'il ne touche rien, il peut s'y déplacer. S'il touche quelque chose, c'est qu'il est dans le mur : il va alors petit à petit reculer sa main, jusqu'à ne plus rien toucher. Et il va alors se déplacer à cet endroit là, qui est donc l'endroit le plus proche du mur sans rentrer dedans.

Temps total pour cette étape : 50 minutes.

Et là, je me suis retrouvée avec un drôle de problème : les projectiles. Eux aussi doivent entrer en collision avec les murs... et rebondir dessus, puisque nous conservons le rebond !

Et c'est là que j'ai eu mes premiers deux gros bugs. *tadaaam*

Vous savez, ce qui est compliqué, avec un bug, ce n'est pas de le corriger. Le plus compliqué, c'est de comprendre pourquoi il se produit ! Il faut donc reprendre toute la logique du code, essayer d'isoler le bout qui ne fonctionne pas, et trouver d'où vient le problème.

Premier bug : rebonds multiples.

Sous certains angles, la balle rebondit de multiples fois dans l'épaisseur du mur, en quelque sorte.

A quoi c'est dû ? Le programme détecte que la balle est toujours dans une zone de rebond, et il continue de la faire rebondir.

Comment j'ai réglé le problème ? Au lieu de lui dire : "si la balle touche un mur, elle repart dans l'autre sens", je lui ai dit "si la balle touche le mur de droite, elle repart vers la droite ; si elle touche le mur du haut elle repart vers le haut", etc. C'est un peu plus long à écrire, mais ça au moins marche.

Deuxième bug : le coin ne rebondit pas.

Celui-là était plus vicieux. En visant pile le coin d'un obstacle, la balle rentrait à l'intérieur... et rebondissait dedans.

J'ai fini (après force arrachages de cheveux) par comprendre que c'était parce que la balle ne rebondissait que si elle se trouvait pile en face de l'obstacle (pour éviter qu'elle rebondisse sur un obstacle situé à l'autre bout du terrain - si si, c'est possible). Or, quand elle vient du coin, elle n'est ni en face horizontalement, ni en face verticalement. J'ai donc élargi la zone de rebond et... tout a été réglé.

Temps total pour cette étape : 50 minutes.

Pathfinding

Si le joueur est assez c*n pour faire foncer son personnage droit dans le mur, c'est son problème. Mais les ennemis, eux, doivent contourner les obstacles et trouver un chemin jusqu'à leur objectif. C'est-à-dire qu'ils doivent avoir un système de pathfinding.

En fait, c'est là que j'ai eu envie de pleurer.

Le pathfinding (ou "recherche de chemin"), c'est un des grands problèmes "classiques" de l'intelligence artificielle. Comme je ne suis pas une brutasse de la programmation, mais un game designer qui a appris à programmer par nécessité, j'avais jusque là tout fait pour l'éviter... et j'avais réussi. Mais là, plus le choix ! Alors j'ai fait comme pour n'importe quel domaine créatif où on cherche des idées : une recherche sur Internet, et un brainstorming avec Ensis, mon frère, le meilleur programmeur du monde !

Avec son aide, j'ai trouvé l'outil qu'il me fallait. C'est une méthode de calcul qui s'appelle l'algorithme A* (prononcez "A star"), pas si compliqué que ça et très efficace. Je vous explique vite fait comment ça marche ?

Pathfinding avec l'algorithme A*

C'est même assez rigolo comme méthode. Pour vous amuser avec, je vous conseille ce site où vous pouvez dessiner des obstacles (voire même un labyrinthe !) et voir l'ordinateur calculer le chemin jusqu'à l'objectif. Notez que les calculs ont été fortement ralentis pour que vous puissiez les voir : en vrai, tous ces calculs ne prennent qu'une fraction de seconde !

Après, à programmer, c'est beaucoup moins facile. J'ai même fait crasher cinq fois le programme (en priant à chaque fois pour que la sauvegarde ne soit pas corrompue !). Pourquoi ? A cause de ce qu'on appelle une boucle infinie, le cauchemar des programmeurs. J'explique.

A un moment dans le programme, je lui écris :

tant que (cette condition n'est pas remplie)

{

         calcule le chemin ;

}

Or, si la condition n'est jamais remplie, le programme va calculer le chemin à l'infini. Du coup, toute la puissance du programme est mobilisée sur des calculs à répétition... et Flash plante.

Heureusement, après de longues phases de débug, j'ai fini par corriger ça. Vous savez combien de temps j'ai mis pour le pathfinding ?

Temps total pour cette étape : 5 heures !

Testez le nouveau prototype !

Si je fais des prototypes, c'est pour que vous puissiez les tester !

Maintenant que le proto fait plus de 640 pixels de large, il ne rentrera plus sur le blog. Vous devrez donc le tester en cliquant sur ce lien.

Je sais qu'il y a encore un petit souci : quand l'ennemi arrive à l'emplacement du personnage, il perd la boule. C'est sur ma liste des bugs à débugger, inutile de me le signaler.

Le point sur les artworks

Avant de vous abandonner pour le week-end, on fait quand même un petit bilan sur l'avancée des artworks.

• l'univers de l'archipel peine à avancer, faute de gens pour y travailler. Vous savez qu'on ne gardera qu'un univers au final, donc soit vous vous motivez à bosser dessus, soit vous rejoignez un autre projet - votre talent y sera bienvenu !
• l'univers du Summer Camp avance doucement. Vous avez réussi à vous mettre plus ou moins d'accord sur un personnage, mais êtes en train de laisser les décors de côté ! Rééquilibrez la donne pour que cet univers soit viable.
• l'univers du héros qui veut toucher le ciel est actuellement celui qui marche le mieux. Le personnage principal avance mais n'est pas encore tranché, les ennemis sont intéressants mais manquent de simplicité, et surtout des premières recherches pour les décors vraiment au poil !

Je détaille un peu plus :

(Je n'ai pas pris tous les artworks proposés, seulement ceux qui m'ont paru correspondre aux critères. Si vos propositions n'ont pas été retenues, ne vous sentez pas rejeté : essayez de comprendre ce qui a mieux fonctionné dans les autres propositions et venez les enrichir !)

Artworks réalisés par Alcides, HadH, milou, PiliPili et Sacha

Pour le personnage, la tendance va à un garçon portant un bonnet en forme de citron (extra !) et habillé en scout. On aura une dominante orange dans ses vêtements, qui permettra de bien le repérer dans un décor plutôt nocturne, donc sombre.

Travaillez ce personnage en petit (30 - 40 pixels de haut) et fixez son aspect définitif.

Artworks réalisés par Besloth, Lother et milou

Sur les ennemis, vous avez prévu des personnages simples (c'est bien !) mais c'est encore très timide. Il vous manque une idée directrice, une patte graphique qui puisse s'appliquer à tous les personnages. Revenez aux sources et puisez l'inspiration dans les planches de recherches !

Artworks réalisés par Besloth et milou

Et sur les décors, c'est clair, vous boudez. Besloth a commencé des recherches intéressantes (campement, marécage et sous-bois) mais elle a besoin de votre aide ! Il est temps de vous y mettre...!

Artworks réalisés par Chouf, Flowiine, PiliPili, Pitch, Stoff, Vaëll et Yooiou

Dans le château qui touche le ciel, deux nettes tendances pour les personnages : soit un astronaute avec la tête dans une bulle (c'est assez joli !), soit un jeune personnage habillé en pilote d'avion, avec de grosses goggles. L'un et l'autre sont assez unisexes.

Au niveau de la couleur, les couleurs vives (personnage avec l'étoile, personnage blond) me semble intéressant car elles devraient nettement se démarquer des arrière-plans aux couleurs naturelles (bleu sombre au sous-sol, gris dans les étages et blanc dans la tour).

Continuez vos recherches dans ces deux directions, et mettez-vous d'accord sur un personnage définitif !

Artworks réalisés par ADJ et Axel

Sur les ennemis, ça manque de candidats ! On a une tendance "nature maléfique" pour les niveaux inférieurs et "créatures de papier" pour les niveaux supérieurs, mais rien n'est encore bien défini. Il faut d'autres personnes pour travailler sur ces thèmes !

Attention, vous avez tendance à prévoir des monstres avec des animations très complexes ! Évitez autant que possible les mouvement sinueux et les déformations. Prévoyez des créatures simples. N'oubliez pas que nous avons peu d'animateurs en "stock"...

Artworks réalisés par mister poulet, Stroff et Vaëll 

Et enfin, sur les environnements, je ne peux que saluer la performance !

Je vous invite d'abord à vous pencher sur les croquis de gauche qui, s'ils ne correspondent pas du tout au jeu tel que nous le verrons, apportent deux excellentes idées. Tout d'abord, faire apparaître les ennemis non par des portes, mais dans les flaques au beau milieu du terrain de jeu. Ainsi, plus il y a de flaques, moins on a d'espace "sûr" ! Ensuite, les statues qui servent d'obstacles et qui pourront représenter nos généreux donateurs sur Ulule qui ont souhaité figurer dans le jeu.

Sur le côté droit de la planche, les environnements tels qu'ils seront dans le jeu avancent très vite ! Il y a encore un peu de travail pour qu'on distingue mieux les obstacles du sol, mais c'est très beau et très prometteur !

Notez que le 2e environnement comporte des ennemis (plante carnivore, araignée) également très intéressants. 

Et pour terminer...

...surprise ! Nous avons ici assez de matériel pour faire un petit test d'intégration...!

Bon week-end les loupiots, soyez sages !