Jump to content
Sign in to follow this  
daemondragon

IA #1 - le pathfinding (1/2)

Recommended Posts

Bonjour a tous !

Cette suite de tutoriel va vous expliquez comment faire une IA basique pour des pnj
que vous pourrez adapter pour des jeux simples(non ce n'est pas une super grosse IA
de la mort qui tue qui va faire vos problèmes de math toute seule).

Dans la première partie du tutoriel, nous allons voir une partie fondamentale
des IA dans les jeux vidéos : le pathfinding.
Le code du pathfinding était trop long pour être expliqué dans un seul tutoriel,
le premier traitera de la théorie et le deuxième de la pratique.

Le pathfinding, qu'est ce que c'est ?

Le pathfinding c'est le fait de dire a une personne :
tu vas du point A au point B en évitant les obstacles.
(c'est mieux que de se prendre les murs non ? :) )

Pour le pathfinding, nous allons mettre en place un algorithme A*, qui est
très célèbre et qui peut être utilisé un peu partout, surtout dans le jeu
utilisant un système de grille(starcraft, zelda etc...)

A* tiens son nom de la recherche "en étoile" qu'il fait :
pour chaque case, il va regarder celles d'autour qui n'ont pas été déjà exploré et va dire :
celle la elle est plus loin de la case de départ que la précédente.

petite image :

ExplicationAStar.png

Le 0 correspond au début.
Plus on s'éloigne du 0, plus le coût (ou le poids, c'est la même chose) augmente.
Le but, c'est de prendre le chemin, qui possède le plus faible coût.

Par exemple, si vous voulez partir du point (0, 3) -> le 4eme point
tout en haut a gauche, vous n'allez pas partir carrément a gauche, faire X fois
le tour du gros truc noir, non ?
Vous allez simplement prendre le chemin le plus court.

Pour réaliser donc ce merveilleux pathfinding, vous allez donc partir du début
(le point (7, 6)) et regarder autour, si ce bloc n'est pas un mur. Vous augmenter
alors le coût du déplacement pour cette case, puis on refait cela jusqu’à ce qu'on
trouve la fin voulu ou jusqu’à ce qu'il n'y ai plus de possibilité
de passer car tous les blocs ont été explorés, il n'y a donc pas de possibilité
d'aller du point A au point B.
Puis on part de la fin et on passe par les blocs qui ont le plus faible coût.

Pour réaliser cela, on commence par créer une file (oui je parle enfin de code).
Une file est une structure de données qui permet de mettre des variables l'une après l'autre.
La première donnée qui rentre dans la file est la première à sortir.

Pour ceux qui ne savent pas ce que c'est :


Donc ont la créer, cette file et on met, si ce n'est pas des murs, et s'il n'ont pas
été déjà explorés,la position des blocs d’à coté, tout a la fin.
A chaque tour de boucle, ont prend la première position et on refait la même chose.
Pour les minecraftien, c'est comme l'eau qui coule déjà sur la case la plus proche, puis sur celles
plus éloignées.

Quand on a trouvé la fin, la où le pnj par exemple veut aller, on arrête, ou alors quand il n'y a plus
de blocs a explorer, alors le pnj est triste car il ne peut pas y aller.

Si on a trouvé la fin, on met alors dans une pile, (les dernières données qui arrivent dedans
seront les premières à sortir), car le chemin doit être pris dans le sens contraire où l'on va.
On cherche alors, a partir de la fin, la case autour d'elle qui a le plus faible coût,
puis on enregistre sa position et on mets la direction contraire (n'oublier pas que le
pnj va parcourir le chemin dans l'autre sens) dans la pile et on refait ça
jusqu’à ce qu'on trouve le début.

Et voila vous pouvez maintenant, grâce à ces explication créer vous même votre pathfinding, ou alors
attendre le prochain tutoriel qui ne devrait pas tarder a suivre.
En utilisant uniquement le pathfinding et intelligemment vous pouvez déjà créer un planning pour chaque pnj,
ce qui va permettre de rendre une ville plus vivante (je pense surtout au village pnj de zelda qui sont
toujours au même endroit, c'est un peu triste non ?).

Edited by daemondragon
  • Upvote 5

Share this post


Link to post
Share on other sites

Très instructif et assez complet même si à mon avis un petit bout de code pour justifier la catégorie C n'aurait pas fait de tord mais bon je suppose que le 2/2 en comportera.

+1 Rep

Share this post


Link to post
Share on other sites

Je confirme : très bon tutoriel.
J'ai vu que la suite a été postée, mais je ne l'ai pas encore consultée. L'initiative de poster une méthode de conception d'IA est excellente, et vu que plusieurs membres se lancent dans des projets de RPG, ça les aidera !

+1 rep, bravo.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

×
×
  • Create New...