Jeu vidéo

Calcul du pathfinding

Ce tutoriel a été publié en 2013 sur la Petite Fabrique de Jeu Vidéo, le blog qui a permis à 82 internautes débutants de réaliser leur premier jeu vidéo, Rose in the Woods.

Génération du terrain

Dans Rose in the Woods, le terrain n'est pas vide : 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 ?

Générer un niveau de jeu avec une grille

Temps total pour cette étape : 35 minutes.

Collisions du personnage

Déplacement du personnage

Mais le fait que moi, je pense que ces rectangles sont des obstacles, ne veut pas dire que Flash le sait. 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.

Détection des obstacles

Temps total pour cette étape : 50 minutes.

Rebonds des projectiles

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

Bug du rebond

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

Bug du rebond

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.

À découvrir

Être testeur de jeux vidéo

Le pathfindin A*

Si le joueur est assez con 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 mon frère, le meilleur programmeur du monde !

Brainstorming

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 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 !

Liste des tutoriels

Découvrez aussi...

Animer un personnage de jeu vidéo

Me connecter
ou
Je suis nouveau !

Mot de passe oublié ?

Votre compte sera automatiquement créé lorsque vous posterez votre premier dessin.

Pour participer, cliquez sur le bouton "Répondre" en bas du topic de votre choix. Le topic Bienvenue aux nouveaux est l'endroit idéal pour commencer !

C'est parti !