Hello les gens, je viens de finir une " étdude compartive" des différents algorythmes de pathfinding, dans le but d´en choisir un pour mon projet tactical Crystal.
Pour ce test, j´ai utilisé un logiciel disponible dans la page d´introduction sur les pathfinding du site Gamasutra; le reste de la procédure de texte est expliqué dans le . txt ainsi que les résultats.

Voici un pack contenant des screenshots de mes résultats et un petit fichier les commentant.
http://mickledingue.free.fr/filrazorback/hsite/Pathfinding.rar

Je lis un article sur le pathfinding en ce moment meme, voici un petit paragrahe interessant:

" * La recherche en largeur ( breadth-first search) est la méthode qui consiste à développer successivement les nœuds d’un même niveau de profondeur ( on s’arrête dès que l’on rencontre un état-but) et au cas où la solution ne serait pas trouvée, à réitérer le processus au niveau de profondeur suivant. Cette recherche est dite algorithmique car elle garantit de trouver une solution, s’il en existe une, pourvu que l’arbre ai un nombre de branches fini. Son inconvénient elle qu’elle consomme non seulement beaucoup de mémoire ( il faut mémoriser tous les nœuds du niveau) mais surtout beaucoup de temps de calcul.
* La recherche en profondeur ( depth-first search) consiste, elle, à explorer un chemin en allant vers les degrés de profondeur croissants. En cas de cul de sac, on effectue un retour en arrière vers le nœud père. Cette méthode est dite non algorithmique à l’état brut ( sans limite de profondeur) car elle peut conduire vers des chemins longs qui n’offriront aucune garantie de succès. Elle est rendue algorithmique grâce à la notion de profondeur limite.
"

Il m´a permis de bien comprendre l´algorythme depth search qui m´echappait

je crois que le plus utilise est le A*
en gros , pour un jeu en tiles , ca correspond à donner une valeur plus ou moins elevee a chaque tile , et l´ordi se debrouille pour trouver le chemin qui " coute" le moins de points .
je crois

Je confirme mais dans le cadre tactical crystal, je ne veux pas d´une ai parfaite, et vu que 6 persos se baladeront en meme temps sur la map, exploitant tous le meme algo; je ne veux pas qu´il s´execute trop lentement;

Maintenant que j´ai un algo qui me plait bien, je vais devoir penser à une maniere de le rendre exploitable avec d´autres personnes qui se baladent: si ils se foncent tous dessus et restent bloqués comme des moules ca ira pas

Apres une courte reflexion je suis arrivée à l´idée suivante, pour gérer le deplacement de personnages:

Operation répétée a chaque pas par chaque personnage:
-Faire considérer aux autres la case d´ou je viens comme pratiquable
-Faire considérer aux autres la case ou je suis comme inpratiquable
-Envoyer mes coordonnées et ma destination ( determinée vie l´algo d´IA)à l´algo de pathfinding
-Utiliser l´algo de pathfinding ( basé sur le breadth tracing favorisant la direction de l´objectif via calcul de distance manhattan)
-Effectuer le premier pas du chemin renvoyé par l´algo
-Mettre à jour mes coordonnées

Le probleme c´est que ca me parait con de calculer tout le chemin pour ne faire qu´un pas, et 6 persos faisant ca en meme temps de risquent ils pas de saturer le cpu?
Qu´en pensez vous

Je précise, pour ceux qui n´auraient pas suivi mes derniers topics, que le jeu est programmé en actionscript ( flash mx 2004) mais que je ne m´interesse ici qu´à la theorie

Je up un coup vu que les gens intelligents du forum trainent dans les parages ce soir

Tu peux peut être regarder du cotés d´algos du genre raycasting vu que t´es persos sont censés être proche de toi et ne pas avoir de gros obstacles avec cul de sac ( des obstacles de fourbes donc) pour les gener.

raycasting? c´est la methode pour gerer l´affiche des moteurs a la doom et wolfenstein je crois non?
tu confonds pas avec robusttracing? auquel cas les resultats du test sur la premiere map du jeu ont été tres mauvais

nan, je sais ce que je dis ( sur ce truc au moins ; ) ) . Peut etre que c´est le meme principe que ton robusttracing.
Le but du jeu est de lancer un rayon entre le départ et l´arrivée et de voir si il y a des obstacles. Auquel cas, tu dévie un peu le rayon. Enfin, c´est le principe

il me semble que c´est ca le robust tracing, telecharge le pack de resultats au debut du topic et regarde le resultat...

La pathfinding est un sujet interressant, mais le plus important est de bien definir de quoi tu as besoin. C´est pas la peine de mettre en place un super algo alors qu´au final t´avais besoin que d´un truc simple.

Donc mets d´abord bien a plat ton probleme et ensuite cherche une solution ( et non pas : Je choisi un algo et je l´applique sur mon jeu).

C´etait justement le principe de mon etude: j´ai recrée une map du jeu dans le programme de gamasutra et j´ai pris ce qui a le le mieux marché;
Sans essais, j´aurai pris le robust tracing, or il ne convenait pas du tout finalement!