Développement XNA pour la XBox et le PC
186
La recherche sur l’intelligence artificielle évolue rapidement. De nos jours, un champion
du monde d’échecs se fait battre par un ordinateur. Peut-être que dans un avenir proche,
les choses vont prendre une dimension encore plus grande. Des scientifiques travaillent
sur un système capable de représenter des pensées en images, d’autres ont créé un robot
qui fonctionne avec un cerveau contrôlé par des neurones de rat. Le futur présenté dans
les films de science-fiction de ces 30 dernières années semble arriver bien plus vite que
n’importe qui aurait pu l’imaginer.
XNA ne propose pas de classes ou de fonctions prêtes à l’emploi en rapport avec n’importe
quel domaine de l’intelligence artificielle. C’est à vous, développeur, de programmer
pour les jeux les algorithmes qui vous intéressent.
Comprendre le pathfinding
En programmation de jeu vidéo, on appelle pathfinding (recherche de chemin, en français)
le processus de détermination du chemin entre un point de départ et un point d’arrivée.
Le tableau 9-1 présente quelques algorithmes de recherche de chemin.
Les domaines d’application du pathfinding sont nombreux et variés : GPS, robotique, réseaux
informatiques, jeux vidéo etc. Dans tous ces domaines, le processus de détermination du
chemin à emprunter est essentiel.
Ainsi, si on considère les jeux de stratégie, des milliers de personnages peuvent se déplacer
en même temps : l’ordinateur ou la console effectue sans relâche des calculs pour
permettre aux différentes entités de se déplacer. Il faut donc trouver un moyen rapide
d’effectuer ces calculs tout en conservant des résultats pertinents. Soyez cependant vigilant :
si la solution que vous mettez en place ne retourne pas des résultats assez rapidement, le
jeu sera saccadé. En vous reportant au tableau précédent, vous trouverez facilement quel
algorithme est adapté aux jeux vidéo.
Effectivement, il s’agit de A*. Dans la suite de ce chapitre, nous nous intéresserons à son
principe de fonctionnement, puis à sa mise en œuvre en C# avec XNA. Attention, il a été
question de performances quelques lignes plus tôt : l’algorithme tel qu’il est présenté ici
est loin d’être vraiment utilisable dans une grosse production. Il y a beaucoup de choses
à améliorer pour réduire le temps nécessaire à son exécution. Cependant, ce chapitre
n’est qu’une introduction à la recherche de chemin. Si vous vous intéressez aux bonnes
Tableau 9-1 Algorithmes de recherche de chemin
Nom
Description
Dijkstra
Il retourne le meilleur chemin. Il est utilisé par exemple dans certains protocoles de
routage réseau.
Viterbi
Il permet de corriger les erreurs survenues lors d’une transmission via un canal bruité.
A* (prononcez « A Star »)
Il ne retourne pas forcément la meilleure solution, mais c’est un bon compromis entre
pertinence du résultat et coût du calcul.
=Labat FM.book Page 186 Vendredi, 19. juin 2009 4:01 16
186
La recherche sur l’intelligence artificielle évolue rapidement. De nos jours, un champion
du monde d’échecs se fait battre par un ordinateur. Peut-être que dans un avenir proche,
les choses vont prendre une dimension encore plus grande. Des scientifiques travaillent
sur un système capable de représenter des pensées en images, d’autres ont créé un robot
qui fonctionne avec un cerveau contrôlé par des neurones de rat. Le futur présenté dans
les films de science-fiction de ces 30 dernières années semble arriver bien plus vite que
n’importe qui aurait pu l’imaginer.
XNA ne propose pas de classes ou de fonctions prêtes à l’emploi en rapport avec n’importe
quel domaine de l’intelligence artificielle. C’est à vous, développeur, de programmer
pour les jeux les algorithmes qui vous intéressent.
Comprendre le pathfinding
En programmation de jeu vidéo, on appelle pathfinding (recherche de chemin, en français)
le processus de détermination du chemin entre un point de départ et un point d’arrivée.
Le tableau 9-1 présente quelques algorithmes de recherche de chemin.
Les domaines d’application du pathfinding sont nombreux et variés : GPS, robotique, réseaux
informatiques, jeux vidéo etc. Dans tous ces domaines, le processus de détermination du
chemin à emprunter est essentiel.
Ainsi, si on considère les jeux de stratégie, des milliers de personnages peuvent se déplacer
en même temps : l’ordinateur ou la console effectue sans relâche des calculs pour
permettre aux différentes entités de se déplacer. Il faut donc trouver un moyen rapide
d’effectuer ces calculs tout en conservant des résultats pertinents. Soyez cependant vigilant :
si la solution que vous mettez en place ne retourne pas des résultats assez rapidement, le
jeu sera saccadé. En vous reportant au tableau précédent, vous trouverez facilement quel
algorithme est adapté aux jeux vidéo.
Effectivement, il s’agit de A*. Dans la suite de ce chapitre, nous nous intéresserons à son
principe de fonctionnement, puis à sa mise en œuvre en C# avec XNA. Attention, il a été
question de performances quelques lignes plus tôt : l’algorithme tel qu’il est présenté ici
est loin d’être vraiment utilisable dans une grosse production. Il y a beaucoup de choses
à améliorer pour réduire le temps nécessaire à son exécution. Cependant, ce chapitre
n’est qu’une introduction à la recherche de chemin. Si vous vous intéressez aux bonnes
Tableau 9-1 Algorithmes de recherche de chemin
Nom
Description
Dijkstra
Il retourne le meilleur chemin. Il est utilisé par exemple dans certains protocoles de
routage réseau.
Viterbi
Il permet de corriger les erreurs survenues lors d’une transmission via un canal bruité.
A* (prononcez « A Star »)
Il ne retourne pas forcément la meilleure solution, mais c’est un bon compromis entre
pertinence du résultat et coût du calcul.
=Labat FM.book Page 186 Vendredi, 19. juin 2009 4:01 16