Explications sur le Pathfinding.

[LPTheKiller]

Parmi toutes les difficultés qui se présentent lors de la réalisation d’un jeu, celle du pathfinding est sans doute loin d’être la plus simple à résoudre.

Profitant de la rubrique DevBlog prévue à cet effet, nous allons parler ici d’un type de pathfinding particulier que j’ai mis au point pour Ronin Blades, un des jeux flash que je développe personnellement.

Qu’est-ce que le pathfinding ? C’est l’ensemble des algorithmes qui vont permettre à l’ordinateur de calculer le chemin que doit emprunter un personnage contrôlé par l’IA pour aller d’un point A à un point B tout en évitant les obstacles et en parcourant la distance la plus petite possible.

Si la plupart des jeux flash, parce qu’ils sont vus de côté ou parce que leur réalisation est primaire, n’ont pas besoin de pathfinding, ce n’était pas le cas de Ronin Blades, qui est vu de haut et présente des environnements contenant des bâtiments et autres obstacles qu’il faut contourner et derrière lesquels il est possible de se cacher.

J’aurais pu me renseigner quelque peu sur le sujet et tenter de copier ou même d’utiliser des algorithmes déjà existants, mais cela aurait été contraire à ma démarche traditionnelle, qui est de tout programmer moi-même.
Ainsi, j’ai dû faire grand usage de mon imagination et de mes connaissances en algo, que j’ai acquises au fil des années de manière autodidacte, et bien sûr en mathématiques.
Et alors qu’il me semble que bon nombre des pathfindings ordinaires se basent sur une grille de cases "ouvertes" ou "bloquées" représentant le terrain, j’ai opté pour une résolution vectorielle du problème, c’est-à-dire en utilisant des formes virtuelles et des équations mathématiques pour détecter les collisions, au lieu de bêtement "tester" les cases d’un grossier damier virtuel.
En l’occurrence, comme je voulais réaliser la chose en un temps raisonnable et ne pas m’embêter de manière exagérée, j’ai décidé que les formes représentant les obstacles seraient toutes des rectangles non inclinés à longueur et largeur variable, largement suffisants pour modéliser l’environnement de Ronin Blades.

Je vous propose ici de détailler comment fonctionne cet algorithme, et quelles en sont les limites.

Étape 1 :
Le principe de base est le suivant : Le plus court chemin reliant les points A et B étant la ligne droite, l’algo va d’abord s’occuper de tester si le chemin direct de A à B est dégagé. Si c’est le cas, évidemment, il ne se posera pas d’autre question et prendra cet itinéraire.
En revanche, si la résolution mathématique détecte une collision de la trajectoire avec un objet bloquant l’accès, il identifiera le côté de l’objet que la trajectoire touche en premier (le côté du haut, du bas, de droite ou de gauche), et il trouvera les deux coins adjacents à ce côté, que nous appelleront C et D.



Étape 2 :
L’algorithme va alors se scinder en deux voies possibles : Passer par C ou passer par D.
Étudions le cas de la voie C.
L’algo va déterminer s’il est possible de se rendre en C directement et sans encombre. Si cela est possible, il va s’y rendre directement. Si, au contraire, il rencontre un nouvel obstacle, il créer un sous-processus qui réitérera l’étape 1 et les suivantes avec ce nouvel obstacle, en tentant de le contourner lui-aussi.
Le sous-processus, qui fonctionne de la même manière que le principal, se chargera de trouver le meilleur itinéraire pour se rendre au point C. Cet itinéraire s’ajoutera simplement à l’itinéraire principal, calculé dans le processus principal, et l’algorithme pourra continuer.





Étape 3 :
A partir du point C, nous allons simplement reprendre l’algorithme depuis l’étape 1 en remplaçant A par C : C'est-à-dire, regarder s’il est possible de se rendre en B depuis le point C, et si l’on rencontre une nouvelle face de l’objet contourné, l’algo va chercher à continuer le contournement en rejoignant un autre des coins de l’objet.






Étape 4 :
Une fois tous les itinéraires possible arrivant à leur but calculés (car sur tous ceux tentés, bon nombre n’aboutissent à rien), le programme se charge de calculer celui qui est le plus court.
(Si aucun chemin n’arrive au but, on choisira le chemin dont le point d’arrivée est le plus proche possible du point B.)


Voici une situation plus complexe schématisée :



Des screens du jeu en mode debug quand j'ai programmé mon algo :



L’algorithme, assez complexe, se basant sur des appels récursifs de fonctions dans elles-mêmes, et donc sur la création de boucles d’appels fonctionnels, il est nécessaire d’empêcher ces boucles d’être infinies en implémentant diverses vérifications : Par exemple, empêcher l’algorithme de passer deux fois par le même point.




Malgré tout, l’algorithme décrit est limité et ne répond pas à toutes les situations, car je me suis ici contenté de n’en expliquer que les principes fondamentaux.
Par exemple, il est impossible (en n’essayant de rejoindre que les deux coins adjacents au côté touché), de trouver une solution pour sortir d’un cul-de-sac.




Je suis en train de compléter le code afin qu’on puisse sortir d’un cul-de-sac, mais cela n’est pas encore terminé, et même si je sais globalement comment faire, cela risque de prendre un peu de temps (surtout parce que j’ai d’autres projets en cours).









Voilà, j’espère que ceci a éclairé vos esprits avides de connaissance et que vous avez globalement compris. J’ignore si j’ai été assez clair, mais j’espère que vous prendrez dorénavant mieux conscience de la difficulté que représentent le genre de problèmes que pose la programmation d’un jeu, et en particulier celle de l’intelligence artificielle.



Voir la news (1 image, 0 vidéo )

[sukiyaki]

Génial, ça éclairci pas mal de questions
Merci pour les explications !

[Aghora]

Par contre les schémas ne sont pas très clairs, il manque une légende et un commentaire.

[le_guide_michelin]

C'était passionnant à lire, et très instructif. Tout ce travail force le respect.
Mais t'es un grand malade
Tout ce travail. Moi pour en faire le quart, je réclame un salaire. Alors se déchirer le crane pour un jeu gratuit ça me dépasse.
Moi aussi j'ai eu ma période bénévole, à l'époque où j'étais actif dans la communauté mandriva, Amiga (et ouai, y'a des nostalgiques qui travaillent, et développent encore dessus) handicap international.
Mais le système m'a bouffé. Le loyer, les factures, une femme, les emmerdes.... La vie quoi.

A l'époque j'étais respecté, dans ces trois communautés. Maintenant elle m'interdit d'avoir plus d'un PC, et ne me laisse plus que le droit d'aller poster des conneries sur les forums
Ne te laisses pas embrigader comme moi.Le feu sacré brule encore en toi. Fait tout pour le préserver.
TUES TA FEMME AVANT QU'ELLE NE L'ÉTEIGNE

[Mambba]

Oui, les schémas me laissent perplexes o_O" entre les C, les P, les points qu'on sait pas quesqueca veut dire
Bon je suis pas bête et j'ai quand même su remplacer B par P et C par les points qu'on voit sur les dessins, mais c'est pas pour autant que j'ai tout pigé les lignes ... @_@

Mais pas mal les explications

Tout ça me rapelle mes braves personnages qui se payaient les murs dans Baldur's gate & co.

[sepandemic]

Je suis d'accord , le pathfinding est un véritable enfer a programmer et a créer .

Personne n'a idée de cette enfer avant de l'experimenter sois-meme.
Perso j'ai eu ce problème en essayant de développer un petit FPS sous directx .
Cependant il existe 2 possibilités ou "feintes" pour éviter de subir ce calvaire :

A ) la plus facile et rapide est de créer des "hiddent waypoints" ou bien points relais dans la map que L'IA va suivre , c'est le principe le plus repandu dans les jeux "dans half life 2 épisode 1 , en mode commentaire, dans l'hôpital les développeurs exposent ce problème et vous montrent en live dans le niveau les waypoints installés " .

B ) téléporter l'IA pres du joueur dans un angle invisible "detour d'un couloir par exemple" ou le monstre par exemple apparait ou disparait brutalement a coté du joueur, cette technique est utilisé dans les survival horror et les jeux d'actions "GTA" .

Pour le reste , il-y-a l'enfer ; l'algorithme !!!! Mais la il faut être chevronné en programmation pour le créer.
"exemple du jeux F.E.A.R qui utilise un des algorithme de pathfinding les plus élaborés jamais vu".

Quand a ton jeux je te conseil d'utiliser la technique "hiddent waypoints" pour gagner du temps.

Ton article m'a rappelé bien des souvenirs ! Merci !

[edenwars]

Il y'a des cours intéressant sur le site du zero aussi.

http://www.siteduzero.com/tutoriel-3...ng-avec-a.html
http://www.siteduzero.com/tutoriel-3...-dijkstra.html




A voir

[Rodwin]

Pour l'expérimenter actuellement, je te confirme que la solution de la grille (avec les points de passages possibles et impossibles) est effectivement basique. Mais elle a le mérite d'être rapide : ton calcul du chemin le plus court n'est alors qu'un parcours des cases "possibles" entre deux points. S'il faut plus de boucles pour trouver le résultat, ceux-ci sont rapides à atteindre (utilisation d'index sur la grille), et à analyser. De plus, tu peux facilement gérer plusieurs niveaux de possible selon les mêmes cases : les cases visibles (cas de la visibilité limitée à une certaine distance), monter ou descendre d'un niveau (gestion basique de la 3D). Les possibilités sont nombreuses même si les ficelles du calcul sont tellement grosses qu'on dirait des cordes.

[Jeremy]

Je conseille tout de même tout ce qui est théorie des graphes : il y a déjà des gros bourrins qui ont bien galéré sur des algos pas trop dégueulasses. Bon après, il faut arriver à générer le bon graphe.

[LPTheKiller]

Par contre les schémas ne sont pas très clairs, il manque une légende et un commentaire.

Oui, les images sont nulles, en fait c'est parce que j'avais la flemme de faire plein de schémas, j'ai juste pris des screens des représentations qui me servaient à moi pour coder et que je suis seul à pouvoir comprendre.
Je ferai des beaux schémas en remplacement.

C'était passionnant à lire, et très instructif. Tout ce travail force le respect.
Mais t'es un grand malade
Tout ce travail. Moi pour en faire le quart, je réclame un salaire. Alors se déchirer le crane pour un jeu gratuit ça me dépasse.
Moi aussi j'ai eu ma période bénévole, à l'époque où j'étais actif dans la communauté mandriva, Amiga (et ouai, y'a des nostalgiques qui travaillent, et développent encore dessus) handicap international.
Mais le système m'a bouffé. Le loyer, les factures, une femme, les emmerdes.... La vie quoi.

A l'époque j'étais respecté, dans ces trois communautés. Maintenant elle m'interdit d'avoir plus d'un PC, et ne me laisse plus que le droit d'aller poster des conneries sur les forums
Ne te laisses pas embrigader comme moi.Le feu sacré brule encore en toi. Fait tout pour le préserver.
TUES TA FEMME AVANT QU'ELLE NE L'ÉTEIGNE

Merci pour le conseil. Mais je me disais que quand j'aurais terminé le jeu (si je trouve le temps de le terminer) je pourrai le proposer aux gros sites de jeux Flash, qui payent pour leurs jeux.

Et puis sinon c'est surtout par passion et pour apprendre que je le fais. Parce qu'en faisant ça je deviens meilleur, et ça m'aidera plus tard.

En fait pour l'histoire je tire grosso-modo la technique algorithmique d'un moteur de connaissance logique avec analyse structurelle (je sais les termes sont un peu pompeux ^^) que j'étais déjà en train de programmer, et qui m'en avait VRAIMENT fait voir de toutes les couleurs (jamais fait un algo aussi complexe).
J'ai donc repris et simplifié le fonctionnement global de l'analyse structurelle pour implémenter le pathfinding.

Pour l'expérimenter actuellement, je te confirme que la solution de la grille (avec les points de passages possibles et impossibles) est effectivement basique. Mais elle a le mérite d'être rapide : ton calcul du chemin le plus court n'est alors qu'un parcours des cases "possibles" entre deux points. S'il faut plus de boucles pour trouver le résultat, ceux-ci sont rapides à atteindre (utilisation d'index sur la grille), et à analyser. De plus, tu peux facilement gérer plusieurs niveaux de possible selon les mêmes cases : les cases visibles (cas de la visibilité limitée à une certaine distance), monter ou descendre d'un niveau (gestion basique de la 3D). Les possibilités sont nombreuses même si les ficelles du calcul sont tellement grosses qu'on dirait des cordes.

Je sais que ça aurait été beaucoup plus rapide, niveau perf', mais j'avais envie de m'éclater. Et puis mon système est plus souple : il permet de positionner où on veut les objets et les personnages et non seulement alignés sur une grille.

[P1ng0uin]

Je vois pas trop l'intérêt de programmer en récursif: niveau perf c'est lourd.

En restant sur ton idée initiale (chemin le plus court sinon contournement)...

Je partirai plutôt en itératif avec un tableau de amorces de chemin qui se remplit au fur et à mesure des étapes et des longueurs mises à jour à chaque étape. Dès que tu as un chemin qui aboutit, tu "tues" toutes les amorces de chemin qui présentent une longueur supérieure à ton chemin complet. Tu construit ta boucle de manière à ce que la longueur de tes amorces soit strictemeny croissante d'une itération à l'autre. A chaque boucle tu mets à jour la longueur la plus courte pour chemin ayant abouti et tu dégages tout ce qui est supérieur. Comme ça tu n'as pas besoin de calculer tous les chemins jusqu'au bout.

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

[Rodwin]

Oui, mais pour construire tes vecteurs, tu places bien les points à relier sur une grille, ou me trompe-je ?

[Seboss]

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

Dans un contexte dans lequel on travaille en délai et coût restreint, je suis d'accord. Mais quand la démarche est auto-didactique, pourquoi pas ?
Merci pour cet article, je n'aurais pas été fâché de voir un peu de pseudo-code par contre

[LPTheKiller]

Voilà j'ai mis des nouveaux schémas.

Je vois pas trop l'intérêt de programmer en récursif: niveau perf c'est lourd.

En restant sur ton idée initiale (chemin le plus court sinon contournement)...

Je partirai plutôt en itératif avec un tableau de amorces de chemin qui se remplit au fur et à mesure des étapes et des longueurs mises à jour à chaque étape. Dès que tu as un chemin qui aboutit, tu "tues" toutes les amorces de chemin qui présentent une longueur supérieure à ton chemin complet. Tu construit ta boucle de manière à ce que la longueur de tes amorces soit strictemeny croissante d'une itération à l'autre. A chaque boucle tu mets à jour la longueur la plus courte pour chemin ayant abouti et tu dégages tout ce qui est supérieur. Comme ça tu n'as pas besoin de calculer tous les chemins jusqu'au bout.

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

Comme je l'ai dit j'avais pas envie de m'emmerder, donc j'ai fait au plus simple et intuitif. J'ai pensé à ta méthode avec un tableau qui se remplirait mais c'était plus dur à débuguer, car tous les chemins sont calculés en même temps petit à petit. Mais c'est sans doute pas mal pour les perfs. Remarques que rien ne m'empêche dans ma technique de tuer les amorces trop longues au fur et à mesure, ni de commencer par les chemins potentiellement les plus court.

Réinventer la roue n'a pas l'air très utile, mais c'est très formateur. Qu'y a-t-il de mieux pour s'initier à la recherche ? Surtout que si on y arrive vraiment pas, on peut toujours aller s'aider des solutions qui ont déjà été trouvées.

Oui, mais pour construire tes vecteurs, tu places bien les points à relier sur une grille, ou me trompe-je ?

Non, en fait je prend les coordonnées des points A et B, et de tous les coins ses obstacles et je résous toutes les collisions mathématiquement (intersection de segments, c'est assez basique).
Et pour le calcul des coordonnées des coins, qui sont éloignés des vrais coins de l'obstacle, elle se fait en prenant en compte la largeur de l'ennemi.


---------- Post ajouté à 23h31 ----------

Merci pour cet article, je n'aurais pas été fâché de voir un peu de pseudo-code par contre

Ok si tu veux je posterai du code, mais demain.

[szwip]

L'idée de départ d'utiliser le vectoriel et de détecté les murs et les angles s'y rapportant est bonne : le chemin optimal passe forcément par les angles des rectangles. Par contre au niveau de l'algo tu est en train de réinventé des choses qui existent. C'est vrai que c'est formateur, mais ce n'est pas le plus efficace.

Pour ton problème tu devrais regarder du côté de l'algorithme "A*". Il est assez simple à mettre en oeuvre et t'évitera les tests de boucle infinie et de cul de sac, qui sont en quelque sorte naturellement gérés par l'algo

[yuushiro]

Trés interéssante cette approche.
J'avais un peu plongé dans l'algo A* mais le seul gros soucis de cet algorithme c'est l'évaluation optimale d'un chemin. On peut sous-évaluer ou sur-évaluer mais ça nuit quand même grandement sur les performances. Parfois on se retrouve pratiquement à explorer autant la zone qu'avec un vieux coup de Djikstra.

Sinon, en faisait un peu de géométrie algo en info, j'ai pu percevoir d'autres manières pour faire du pathfinding. En fait en utilisant tout ce qui est triangulation de delaunay et diagramme de voronoi, etc.

On reviendrait a definir des surfaces praticables où non. Aprés c'est certain que de cette manière le chemin obtenu n'est peut-être pas le plus rapide.

Je me demande donc si en combinant A* sur cette carte minimale obtenue à partir de delaunay&voronoi on pourrait ainsi obtenir quelque chose qui donne un résultat assez bon avec des perfs pas trop moisies.

[rOut]

D'après ce que j'ai pu lire, A* ou Dijkstra sont clairement les agorithmes optimals à l'heure qu'il est, pour trouver le chemin le plus court dans un graphe pondéré. A* marchant mieux en général que Dijkstra, mais moins bien dans certains cas particuliers (cul de sac typiquement).

Il est donc à peu près inutile d'essayer de trouver un meilleur algorithme, effectivement, la théorie des graphes est un sujet battu et rebattu depuis des dizaines d'années, et les meilleurs mathématiciens se sont déjà arrachés les cheveux dessus.

Par contre, et c'est finalement la ou la démarche de LPTheKiller est intéressante, c'est au niveau de la création du graphe, sur lequel on va appliquer l'algorithme, que tout se fait. Dans Half Life par exemple, ils ont choisir de créer un graphe grossier avec des waypoints placés à la main, d'autres utilisent une grille régulière qui marchent bien pour des jeux à base de blocs de tailles identiques et carrés ou rectangulaires. Ici par contre, tu as essaies de créer un graphe dynamiquement, au fur et à mesure de la recherche, par rapport à l'environnement qui entoure les objets. Au final, le graphe sur lequel tu appliques Dijkstra inconsciemment, c'est celui formé par tes points A, B, C, D et par les distances qui les séparent. D'ailleurs, tu remarqueras qu'en créant ton graphe dynamiquement, tu fais des choix initialement qui peuvent s'avérer mauvais par la suite : Dans ton exemple un peu plus complexe avec les deux carrés, il choisit C comme premier coin, mais ensuite le détour effectué à cause du deuxième carré aurait rendu le choix de D plus intéressant en fin de compte.

Si ça t'intéresse, tu devrais regarder aussi du coté des théories du partitionnement de l'espace (Diagrammes de Voronoi par exemple, enfin, c'est vaste comme sujet), parce que ca permet potentiellement de diviser ton univers en une grille, plus forcément carrée, prenant en compte les contraintes de l'environnement et les obstacles, de manière à obtenir ensuite un graphe suffisamment grossier pour que l'algorithme soit rapide et suffisamment précis tout de même pour pouvoir calculer n'importe quel itinéraire.

[rOut]

...

Bon bah voilà, il doit être tard parce que je n'avais même pas vu...

Enfin, juste pour dire que le partionnement de l'espace (Voronoi, Delaunay...) et un algo de type A* ne sont pas du tout concurrentiels mais plutôt complémentaires. Voronoy et Delaunay te permettant de créer un graphe assez optimisé, et A* te permettant de calculer le plus court chemin dessus.

[Sk-flown]

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

Je ne suis pas d'accord.

Oui je sais c'est très constructif comme approche.

[xheyther]

Il fallait dire :
Je suis pas d'accord, réinventer la roue, dans le cadre de l'apprentissage de la programmation et de la création d'un premier jeu, c'est instructif et rend meilleur un développeur.

L'important c'est pas de jamais réinventer la roue, c'est de le faire une fois pour voir comment ça marche, et ensuite d'utiliser des trucs plus élaborés (ou même vraiment compliqués)qu'il aurait fallut loooongtemps à réinventer.

[yuushiro]

@rOut : C'est tout à fait là où je voulais en venir.

Sinon pour les histoires de cul de sac concernant l'algo de LPTheKiller, il pourrait être judicieux aussi de faire une sorte de précalc pour définir des polygones convexes. De cette manière on peut éviter d'explorer les culs de sac, mais je ne sais pas si il veut vraiment éviter de les explorer.

[titi3]

Passionnant, tu dois en utiliser des tranquillisants après avoir coder ce genre de choses

Par contre question: en général dans les STR (Company of Heroes), le pathfinding est assez lamentable (surtout pour les blindés dans le cas de CoH), selon toi c'est dû à la complexité de l'environnement ou codage avec des gants de boxe ou mauvais algorithme ou... ?

[P1ng0uin]

J'ai pensé à ta méthode avec un tableau qui se remplirait mais c'était plus dur à débuguer, car tous les chemins sont calculés en même temps petit à petit.

Plus lourd à débugger, sûrement (à chaque étape on fait avancer tous les chemins), plus compliqué je ne pense pas, en général le récursif est abominable à débugguer.

Pour l'optimisation, la solution itérative reste meilleure. En récursif tu calcules toutes chemin les uns après les autres, donc si t'as pas de bol tu vas commencer par calculer les chemins les plus long. Dans la solution itérative, tu identifies en premier les chemins les plus rapides à calculer (moins d'étapes/points de contournement le + rapidement) ce qui permet de commencer à éliminer plus vite.

La solution récursive peut être plus rapide en terme de calcul suivant la map, notamment si le chemin le plus court est parmi les premiers, mais bon avoir du bol, la solution itérative est quand même a priori plus propre.

Sinon en général, le récursif c'est très beau intellectuellement mais en terme de perfs c'est le mal.

Dans le cas d'espèce, le djikstra est loin de tout résoudre puisqu'il faut quand même créer l'arbre ce qui, si on part du "tout géométrique" reste quand même un gros boulot.

Pour les culs de sac, je penserai à un système genre si l'angle est obtu, renvoyer au suivant.

Réinventer la roue n'a pas l'air très utile, mais c'est très formateur. Qu'y a-t-il de mieux pour s'initier à la recherche ? Surtout que si on y arrive vraiment pas, on peut toujours aller s'aider des solutions qui ont déjà été trouvées.

Disons que ça peut former le caractère, mais en général on se donne beaucoup de mal, et puis, sauf si on est un génie, on se rend compte qu'on a quand même plusieurs générations de retard sur les solutions éprouvées et que t'as passé du temps à bosser sur des systèmes soit dépassés, soit à coté de la plaque. Mais ça tanne le cuir.

Peut être plus intéressant de regarder les solutions complexes genre Djikstra et d'en extrapoler les principes à d'autres problèmes. D'essayer de s'approprier des outils plus sophistiqués.

L'algo c'est quand même de plus en plus un boulot de pointe réservé aux théoriciens, l'informatique "moderne" c'est quand même de plus de la normalisation /normalisation/intégration de briques algo/logicielles et que le recours aux algo "maison" est plus un facteur de complexité/erreur qu'autre chose.

PS: mes messages ont peut être l'air un peu définitifs, mais bon c'est juste pour le plaisir de la discussions, hein, tu fais ce que tu veux et y a pas de mal à expérimenter juste pour voir, been here done that.

[xheyther]

Passionnant, tu dois en utiliser des tranquillisants après avoir coder ce genre de choses

Par contre question: en général dans les STR (Company of Heroes), le pathfinding est assez lamentable (surtout pour les blindés dans le cas de CoH), selon toi c'est dû à la complexité de l'environnement ou codage avec des gants de boxe ou mauvais algorithme ou... ?

Je pense que c'est un choix délibérré : les programmeurs sont en général suffisamment intelligent pour implémenter un algorithme correct, surtout s'il s'agit juste de repomper un algo super connu.

Quand tu as des dizaines, voir des centaines ou des milliers de chemin à calculer et à recalculer à chaque itération de la boucle du jeu (l'environnement change à chaque fois : les autres unités peuvent constituer des obstacles), ben tu implémentes un algorithme mauvais mais peu complexe pour ne par consacrer trop de ressources uniquement à ce problème.

Peut être qu'un jour on verra des algo qui exploiteront les GPGPU vu que c'est quand même des truc facilement parallélisable.

[ducon]

Je pense que ces algorithmes sont un peu artificiels : ils font comme si le personnage connaissait l’univers comme sa poche, comme s’il savait que derrière l’énorme immeuble se trouve un gouffre à contourner… ils oublient que bien souvent, on optimise son parcours à partir des données perceptibles, pas à partir du monde entier (ton dentier ?)
En plus, dans le cas de poursuite du joueur, cela suppose que le personnage sait exactement où il est (comme dans Doom), comme s'il disposait de la vision de Superman.
J’aime assez l’idée de petites modifications aléatoires des chemins.

[Herrmann Goulag]

Bon, j'ai suivi les instructions du guide-michelin, j'ai tué ma femme.
Que dois-je faire ensuite?

[P1ng0uin]

les programmeurs sont en général suffisamment intelligent pour implémenter un algorithme correct, surtout s'il s'agit juste de repomper un algo super connu.

Quand tu as des dizaines, voir des centaines ou des milliers de chemin à calculer et à recalculer à chaque itération de la boucle du jeu

Ouep en général, les situations sont souvent très complexes, les algos "parfaits" sont trop lourds à implémenter en temps réels, donc ils emploient des algos simplifiés ou employant des artifices (commes des waypoints pré-positionnés par les levels-designers...) pour un résultat qui sans être parfait donne un résultat satisfaisant dans des temps raisonnables. Ce sont ces bricolages qui sont réalisés avec plus ou moins de talent.

[HellBoy]

Il fallait dire :
Je suis pas d'accord, réinventer la roue, dans le cadre de l'apprentissage de la programmation et de la création d'un premier jeu, c'est instructif et rend meilleur un développeur.

L'important c'est pas de jamais réinventer la roue, c'est de le faire une fois pour voir comment ça marche, et ensuite d'utiliser des trucs plus élaborés (ou même vraiment compliqués)qu'il aurait fallut loooongtemps à réinventer.

Ou encore plus complexe (utilisé par gpg pour Supreme commander 2) :

http://en.wikipedia.org/wiki/Fluid_mechanics
http://en.wikipedia.org/wiki/Navier-Stokes_equations

Admirez les déplacement ultra fluide des unités sans aucune collision :

http://www.youtube.com/watch?v=CMvsjn8KDS0

[Krobill]

Qu'y a-t-il de mieux pour s'initier à la recherche ? Surtout que si on y arrive vraiment pas, on peut toujours aller s'aider des solutions qui ont déjà été trouvées.

Je loue la démarche intellectuelle personnelle qui consiste à se dépatouiller tout seul comme un grand mais comme P1ng0uin, je reste sceptique sur son utilité réelle. En effet si on veut faire un parallèle avec la 'Recherche' comme dans 'recherche scientifique', il ne faut pas oublier que la Recherche, c'est avant tout un gros travail de documentation et de bibliographie. Tous les chercheurs dans un domaine tâchent d'assimiler ce qu'on fait leurs aînés plutôt que de le redémontrer. C'est le seul moyen d'espérer aller plus loin avant le terme de la courte vie qu'est la notre.
Sinon la démarche récursive est un vrai performance killer pour du Flash. Le moindre appel de fonction y coûte fort cher et au coude à coude avec l'instanciation c'est l'un des points auquel il faut en général faire le plus attention pour conserver de bonne perfs.
Mais voilà, tout ceci n'engage que moi, et je comprends tout même la volonté du 'j'essaie de tout faire moi même pour apprendre'.

[rOut]

Je pense que ces algorithmes sont un peu artificiels : ils font comme si le personnage connaissait l’univers comme sa poche, comme s’il savait que derrière l’énorme immeuble se trouve un gouffre à contourner… ils oublient que bien souvent, on optimise son parcours à partir des données perceptibles, pas à partir du monde entier (ton dentier ?)
En plus, dans le cas de poursuite du joueur, cela suppose que le personnage sait exactement où il est (comme dans Doom), comme s'il disposait de la vision de Superman.
J’aime assez l’idée de petites modifications aléatoires des chemins.

Je pensais justement hier à un algorithme différent qui se baserai sur la perception des personnages Mais bon, ça risque de donner des situations ou ils ne choisissent absolument pas le bon chemin, et même si c'est beaucoup plus réaliste, on va te dire ensuite "Ouais, ton pathfinding il est pourrave, ils arrivent même pas à trouver un chemin correct". Le but des jeux vidéso est de s'amuser, pas de faire un truc super réaliste.

Imagine les unités d'un STR qui essaient de traverser une forêt, lorsque tu cliques de l'autre coté, puis se paument dedans et n'en ressortent jamais. Ca te ferait sacrément rager en tant que joueur, et tu blamerais les dev qui codent avec leurs pieds.