Localisation & déplacements

Pour ce premier making-of, je vais vous présenter un des premiers problèmes que j'ai traités : afficher et déplacer un personnage dans une scène.

Présentation du problème

Dans tous les embryons de jeux que j'avais développés jusqu'à maintenant, on était dans un cadre vu de dessus et contrôlé avec les flèches du clavier (ou ZQSD), dans un style proche des premiers Zelda ou plutôt des premiers Pokémon (puisque le personnage était carrément « lié » à une grille, un déplacement ne pouvant s'arrêter que pile sur une des cases, pas entre deux). Bref, en terme de programmation, ça se ramenait assez vite à décaler un indice X et un indice Y dans un tableau à deux entrées qui représente la grille, rien de bien méchant.

Ici, c'est un peu plus compliqué : on se place dans une scène 2D mais qui représente un environnement 3D vu de côté. Les déplacements sont gérés à la souris : on clique à un endroit et le personnage doit s'y rendre. Si on clique sur autre chose que le sol, le personnage doit se rendre le plus près possible du clic tout en restant sur le sol...

Représenter le sol

La première tâche est de représenter le sol. Le décors est représenté par une image unique (faite avec Inkscape comme pour mes BD habituelles). L'idée est d'utiliser une seconde image, invisible celle-ci, qui représente un « masque » du sol. La personne qui joue clique sur un endroit du décors, mais le moteur en interne va regarder où se trouve ce clic sur le masque : si c'est un pixel blanc, c'est un point de sol et on considère les coordonnées du pointeur comme les coordonnées « cibles » du personnage ; si c'est un pixel noir, c'est un mur (ou autre élément de décors), on calcule donc le pixel blanc le plus proche qui sera les coordonnées « cibles » du personnage.

Le masque du sol est légèrement contracté... pour prendre en compte la taille des pieds du personnage ! En effet, j'utilise le point au milieu du bord bas de l'image du personnage comme repère de position, et il faut donc éviter que le bout de ses chaussures ne s'affiche sur une plinthe...

Un peu de profondeur

Comme notre empilement d'images 2D est censé représenter un environnement 3D avec une certaine profondeur, j'ai ajouté un système pour que ce masque de sol encode également une notion de distance « à la caméra » : plus cette distance est grande, plus le personnage va être affiché petit, pour simuler un effet de profondeur. En pratique, j'utilise donc un dégradé de gris pour le sol et une couleur neutre (arbitrairement bleue) pour les zones inaccessibles :

Lorsqu'on clic, si on se trouve sur un pixel non-sol (bleu maintenant), on cherche le pixel de sol (non-bleu) le plus proche, ça ne change pas. Ce qui change, c'est qu'on va maintenant utiliser la teinte de gris du pixel sol (soit celui cliqué, soit celui calculé si on avait cliqué sur du bleu) pour calculer dynamiquement la distance à la caméra et donc la taille du personnage. On donne, via un fichier de config, une valeur de profondeur maximale correspondant au blanc, une autre minimale correspondant au noir, et on fait une bête règle de 3 pour trouver la valeur à partir de la teinte de gris cliquée.

Certes, ici la différence de taille est légère, mais on peut imaginer des scènes avec beaucoup plus de profondeur :

Bon, ici, Sophie a un peu l'air de glisser sur le sol parce que je n'ai pas encore bien réglé la vitesse de marche pour ce genre de profondeur, mais l'idée est là.

Cette profondeur va aussi nous permettre de gérer les occlusions, à savoir : quel objet est devant quel autre par rapport à la caméra. Si Sophie marche au fond de la scène, il faut que le meuble bureau soit affiché devant elle, mais si elle marche devant, il doit être affiché derrière. En pratique, on donne une profondeur fixe à chaque objet de la scène tandis que la profondeur du personnage est calculée dynamiquement.

Trouver le chemin

Tout ça c'est bien beau, mais maintenant qu'on sait où le personnage doit aller, à quelle taille l'afficher et devant ou derrière quels objets, il faut savoir par où passer. La ligne droite est le plus court chemin, oui mais une ligne droite 2D dans l'image peut très bien croiser le chemin d'un objet infranchissable... ou même d'un mur dans l'environnement 3D simulé !

On va donc d'abord représenter les bords de la zone de sol accessible par un graphe, calculé à l'exécution à partir de la bordure de la zone non-bleue :

Lorsque la personne qui joue clique quelque part, on ajoute deux sommets au graphe : celui de la position courante du personnage, et celui de la position cible (encore une fois, soit le point cliqué si on a cliqué sur du sol, soit le point de sol le plus proche du clic sur un mur). On relie ces deux sommets à tous les sommets « visibles » du bord (ceux qu'on peut relier sans croiser une autre arête du graph) :

Et maintenant, il ne reste plus qu'à appliquer un algorithme de calcul du plus court chemin dans un graphe comme il en existe depuis des décennies : celui que j'utilise est le plus grand classique du genre, l'algorithme de Dikjstra (qui date de 1959, quand même). Il existe des algorithmes plus efficaces, notamment si on a un graphe très grand (typiquement, dans vos GPS, on fait des trucs beaucoup plus malins). Là, même avec une scène complexe, on aura rarement plus de quelques dizaines de sommets, c'est peanuts, donc Dijkstra suffit amplement.

L'algorithme nous renvoie la liste des arêtes qu'on doit parcourir pour aller du point de départ au point d'arrivée, et il n'y a plus qu'à la suivre !

Tout cela se fait très rapidement : de ce que j'ai mesuré dans mon jeu sur mon petit PC portable, on est autour de 0,3 ms par clic. Sachant que le jeu tourne à 60 images par secondes, il faut que chaque image soit générée en moins de 16 ms : on peut donc tranquillement calculer le plus court chemin entre deux images sans que cela n'impacte visuellement le jeu (ça ne va pas « laguer »). Si on clique ailleurs pendant un déplacement, aucun problème, on oublie le chemin précédent, on met à jour le point de départ en utilisant la nouvelle position du personnage, et on refait le même calcul !

Une des limitations de l'implémentation actuelle est le cas où une zone ne serait ni visible depuis le sommet de départ ni depuis le sommet d'arrivée : dans ce cas-là, le personnage serait obligé de suivre la bordure dans cette zone. Pour corriger ça, on pourrait imaginer ajouter d'autres arêtes dans le graphe de base, mais pour l'instant l'implémentation actuelle suffit.

Ça marche, elle marche !

Une fois qu'on sait où notre personnage doit aller et par où il doit passer, il faut encore l'animer, car on ne voudrait pas faire « juste » glisser une image (si notre personnage était R2D2, ça pourrait sans doute se faire, remarquez).

Mais ça, je vous en parlerai dans un prochain making-of qui sera donc plus orienté « graphismes ». Merci de votre attention !