IA : Pathfinding et autres mouvements "réalistes" - Page 1

Imaginez un jeu vu de dessus, où l'on déplace un personage dans un labyrinthe de cases en 16x16 (les mouvements sont libres par contre, pas de case par case).

Dans ce labyrinthe se trouvent également des ennemis, et j'aimerais bien qu'ils soient un peu capables de jouer. Autrement dit, qu'ils soient capables de tirer sur le joueur quand ils le "voient", d'aller ramasser des objets à portée, et si possible de trouver leur chemin d'un point à un autre à travers les obstacles et les murs.

Quelle est la méthode la plus rapide pour faire ça, sachant qu'il peut y avoir jusqu'à 20 ennemis en jeu, donc il faudrait éviter un truc trop lent ?

Pour les obstacles et les murs, ils faut faire par pondération de cases je pense.

Pour la vue de chaque ennemis, tu comptes qu'ils soient capables de voir seulement en ligne droite, où aussi "du coin de l'oeil" ?

Pour le pathfinding, il faudrait un truc rapide. Je ne sais pas si l'A* est envisageable, mais de toute façon le seul essai que j'ai fait avec cet algo s'est soldé par un échec.

Pour la detection des ennemis, comme le jeu est vu de dessus, j'aimerais que l'ennemi voit à peu près comme le joueur, c'est à dire également derrière lui. Autrement dit un champ de vision en cercle ou qqchose dans le genre :

OOOVVVOOO
OOVVVVVOO
OVVVVVVVO
OVVVXVVVO
OVVVVVVVO
OOVVVVVOO
OOOVVVOOO

Mais il ne peut tirer que dans 8 directions, donc après avoir "vu" le joueur il faudrait qu'il se repositionne pour être dans une de ces 8 configurations :

OVOOVOOVO
OOVOVOVOO
OOOVVVOOO
VVVVXVVVV
OOOVVVOOO
OOVOVOVOO
OVOOVOOVO

Mais là on retombe dans le problème du pathfinding.

Pour le cercle de vision, tu fais par calcul du carré de la distance (la somme des carrés des différences d'abcisses et d'ordonnées) que tu compares à une constante, le carré de la visibilité, enfin ça c'est la partie la plus simple ...

bob64 envoie moi ton mail par minimesage je pense avoir qqch pour toi

Zdr > Ah oui j'avais oublié de le préciser, désolé : Il ne faut pas que les ennemis puissent voir derrière les murs, donc un carré de distances ça marche pas puisque ça ne prends aucun obstacle en compte

nEUrOne > C'est fait

Tu dis qu'il voit pas plus loin que 3 cases ca fait un truc du genre
00X00
0XXX0
XXXXX
0XXX0
00X00
avec un compteur.
Si la case est un mur, tu fait une pondération de 4 -> il peut pas voir derrière le mur (si le mur est une case)
Sinon, une pondération de 1.
Si y qqn sur une cases, tu fais une pondération de 2, etc

C'est une idée comme ça, j'ai jamais testé ni reflechi au problème, donc si c'est de la merde comme idée, pas la peine de m'incendier

Noeurone> Tu peux pas poster ici ton truc, STP ?

PaXal > Je n'ai pas très bien comprit ta solution : Si la case est un mur -> laquelle ?
Surtout que je n'ai jamais cherché à comprendre le principe de la pondération

pour le pathfinding, demande à pyro

Moi je ne comprend même pas le mot "pondération" alors

Pourquoi tu ne réalises pas tout simplement un balayage en spirale (enfin avec le "mouvement" que tu veux) autour de chaque personnage ?

pondération = chaque case a un poids, une valeur. On se fice une valeur à ne pas dépasser. Ca permet de limiter le champs de vision.

Exemple


Avec Murs
0000000
======
0321230
321X123
03=1230
000=300
0000000

Sans Mur
0003000
0032300
0321230
321X123
0321230
0032300
0003000


Les = sont les murs. Après tu regarde autour de toi, par récurrence.

Une pondération, si je ne me trompe pas, c'est tout simplement associer à chaque case un coefficient, va voir le tuto de nEUrOne sur le pathfinding (sur ti-fr), il l'explique.

Mais à quoi ça sert ?

Il suffit de balayer les cases qui entourent le personnage, à la recherche du joueur !

Ah oué je comprends mieux la pondération mais ça doit être ultra-lent, non ? Parceque si je veux faire ça pour une vaintaine de persos...

Le pathfinding c'est pas compliqué dans ce cas très simple :
Tu initialises une liste avec la case où se trouve le type, et tu mets toutes les cases du jeu à -1. A chaque étape, tu regardes toutes les cases autour de celles qui sont dans ta liste et non visitées (égales à -1), tu les marques avec la distance (nombre d'itérations) de la case de départ et tu les rajoutes dans ta liste, et tu recommences. Le jour où tu tombes sur ta case destination, tu n'as plus qu'à reconstruire le trajet à l'envers en allant vers des cases avec un marquage plus petit.

Pour une implémentation, le source de UMAX http://leiber.free.fr/programmation/umax/source.zip, regarde le fichier Vehicule.cpp.

En y réfléchissant, c'est une grosse simplification de l'algorithme de parcours de graphes de... merde, comme il s'appelle déjà ?

dijkstra ?

Sinon, ton lien est mort.

Il y a maleureusement un problème : Si il faut tester toutes les cases au petit bonheur la chance, ça va être très long, non ?

Au fait, que se passe-t-il dans ce cas là :

###########
#[9]4444444[/9][7]5[/7][4]6[/4]#
#[10]33[/10]#[10]333[/10][9]4[/9][7]5[/7][4]6[/4]#
#[11]22[/11]#[11]22[/11][10]3[/10][9]4[/9][7]5[/7][4]6[/4]#
#[12]11[/12]#[12]1[/12][b]A[/b][10]3[/10][9]4[/9][7]5[/7][4]6[/4]#
#[13]00[/13]#[12]1[/12][11]2[/11][10]3[/10][9]4[/9][7]5[/7][4]6[/4]#
#[13]0[/13][b]P[/b]###[10]3[/10][9]4[/9][7]5[/7][4]6[/4]#
#[13]000[/13][12]1[/12][11]2[/11][10]3[/10][9]4[/9][7]5[/7][4]6[/4]#
###########

Le P est le perso et le A sont point d'arrivée.
Une fois qu'on arriva à l'opération : "Le jour où tu tombes sur ta case destination, tu n'as plus qu'à reconstruire le trajet à l'envers en allant vers des cases avec un marquage plus petit"

Au niveau du A, le marquage le plus petit est 1 mais il est dirigé dans un cul-de sac !
À ce moment, il faudrait revenir en arrière d'un cran et repondérer la case 0 avec une plus grosse valeur et recommencer. Non ?

On parle des valeurs cumulées à partir du point de départ.

C'est pas ce que j'ai fait ?

Il faut tenir compte des murs quand on calcule le coût du mouvement!

Ah oui. Pas con.

bob>
si tu veux je peux t'aider car mon projet en 1ere annee etait exactement ca : recherche et planification d'un plus court chemin, avec l'elaboration de 4 algo (du tres debile à l'algo de folie gérant des clés/portes/murs)

Et Coup de bol, c en C

Par contre c codé pour PC (Win ou UNIX) :/

Bah on peut dire que tu combe bien !!!!!!!!!!!!!

En plus comme tu as plein d'algo peut-être saurait-tu quoi prendre, sachant que je préfererais la vitesse à l'intelligence (du moment que les bot sont à peu près capables de trouver un chemin, c'est parfait )

Dijkstra ! C'est ça, j'ai passé toute la soirée à chercher !

Sinon, cet algo est très rapide, au maximum quelques ms sur un aussi petit terrain, et le plus simple à mon avis.

Pour mon lien, je sais plus, allez sur http://leiber.free.fr/programmation/umax/index.html.

Et quand j'ai dit la distance au point de départ, ça correspond en fait au nombre d'itérations qu'il a fallut pour y arriver, comme dit Kevin.

Dijkstra c'était bien l'algo de cet abruti de Pyroangel ?

FL > Merci, v voir ça de suite

Le lien vers le prog marche, mais pas celui vers la source

Fait ch****, l'accès internet à la maison est encore mort, mon site a des problèmes et je ne peux pas le mettre à jour. Pour le source, reessaie, j'ai réussi tant bien que mal à corriger le lien du bureau.

ok c'est bon, merci je regarde ça dès que j'ai le temps