On m'attend pour les petits fours alors...

·Bonsoir et bonne année à tous, nous revoilà en selle pour un petit billet avant 2008 (en espérant en poster plus l'an prochain). Je vais être en retard à mon réveillon à cause de vous hehe (nan je déconne, je réveillonne sur IRC).

·Commençons avec une petite news de la part d'Adarias, mais pas des moindres.
Voici à quoi ressembleront les portraits des personnages du jeu. J'en profite pour rappeler que toutes les caractéristiques faciales et capillaires du héros du jeu sont laissées au choix du joueur.

Et comme d'hab, des cheveux verts dont la couleur est fixée par le moteur du jeu =)

·Maintenant que vos yeux ont fondu, passons aux choses sérieuses : le code.
J'ai consacré ces derniers temps à continuer mon éditeur de cut-scene et j'ai eu l'occasion de développer l'algorithme de pathfinding que nous allons utiliser dans Partisan. C'est de lui que j'ai décidé de vous parler ce soir.

Un algorithme de pathfinding, c'est quoi ?
C'est un algorithme dont le rôle est de calculer le chemin entre un point A et un point B. C'est essentiel dans un jeu comme Partisan où l'on passe son temps à dire à des unités "va là", "va là-bas" : il faut que les unités trouvent toutes seules le chemin pour s'y rendre et sans gaspiller de points de déplacement.

Bon et concrètement comment ça marche ?
Il existe un assez grad nombre de façons de traiter le problème, si le sujet vous intéresse je vous invite à lire cette page qui répertorie plein d'articles sur le sujet. Je vais ici uniquement expliquer l'algorithme utilisé dans partisan (qui est un dérivé d'A*).
Prenons un exemple concret de situation où l'on a besoin de pathfinding :

Piotr est sur la case rouge et veut se rendre sur la case bleue. Dans cet exemple, on considère qu'il est lourdement équipé et ne peut pas escalader la structure en bois.
L'idée est la suivante : on va déterminer plusieurs pistes de recherche (dans toutes les directions) à partir de la case rouge et toujours suivre celle qui est la plus près du but.
Voilà donc ce qui va se passer, en couleur :

A partir de la case rouge, Piotr peut accéder à la case A (case possible : violet), à la case B(case possible : violet) et à la case derrière lui que j'ai oubliée de mettre en couleur (elle aurait du être violette). Cela fait trois pistes à explorer.
La case A et la case B sont les deux plus près de l'objectif, on va donc s'intéresser à une de ces deux là, par exemple la A (case explorée : vert).
Une fois sur la case A, je peux soit aller à la case C (case possible : violet) soit repartir sur la case rouge, ce qui est sans intêret puisqu'on s'est déjà occupé d'elle.
Les pistes qui me restent sont donc la case B et la case C. La case B étant plus près de l'objectif, on va continuer sa piste (et donc elle devient verte).
Ensuite c'est tout droit jusqu'à la case G (D,E,F et G explorées et donc vertes).
Une fois en G, je peux aller soit en H (la case bleue) soit en I (case possible : violet). La bleue est évidemment plus proche d'elle même que I, on continue donc dans sa direction et tadam...on est arrivé, en ayant fait très peu de calculs inutiles.
Au final, les cases vertes sur le schéma sont celles que l'on a analysées et les violettes sont les pistes encore en stock.
L'avantage de cet algorithme est qu'il s'adapte à toutes les situations, même aux labyrinthes les plus compliqués (sauf qu'il n'y en a pas dans Partisan) tout en restant simple à comprendre.

Une petite note à propos des structures en bois : l'algorithme du jeu est en fait plus compliqué que celui que j'ai décrit. Selon les capacités de saut du personnage considéré il peut ou non escalader certaines cases et surtout il peut ou non sauter au dessus de précipices. Ainsi, l'algorithme trouvera qu'un personnage doué en saut tout intêret à sauter de toit en toit plutot que d'emprunter des échelles.

Voili voilou, j'éspère que cette petite introduction au grand problème du pathfinding vous aura intéréssé et je profite de cette petite conclusion pour vous souhaiter de nouveau une bonne année (et un joyeux noël en retard).