Explications sur le Pathfinding.

[Errata]

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

Ils utilisent ca pour obtenir quelque chose de correcte quand tu déplace plein d'unités, mais pour définir le chemin, ca reste les méthodes habituelles , avec une carte et des zones "non utilisable".

[xheyther]

Je pense que c'est possible de faire du path finding avec navier-stockes. Si tu mets des conditions de débit positif et négatif respectivement au point de départ et d'arrivée de ton dépassement, les ligne de courant vont "naturellement" s'établir entre les deux, sur le chemin qui engendrera le moins de perte de charge (comme en vrai avec de l'eau dans ta baignoire).
J'ai pas d'argument qui prouve que ce sera le chemin optimum, mais je vois pas pourquoi ça serait pas le cas.
Je trouve ça plutôt élégant comme utilisation de N-S.

Reste le problème de la résolution, vu qu'on ne sait pas le faire de manière exacte, il faut discrétisé le terrain et tout mais dans le cas d'un jeu je pense que ça améliore les performances et qu'en plus on a pas besoin de beaucoup de précision. D'autant que dans un ordinateur tout est discrétisé

[ducon]

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.

Ça devrait être réglable, ou le réserver à l’ennemi IA.

[Tramb]

On peut croire que le pathfinding est un problème simple si on ouvre un bouquin de théorie des graphes, justement.
Mais quand on rajoute le steering et le flocking, on obtient un "hard problem" bien ouvert

La solution mécaflu de gpg est créative pour gérer des flux de déplacements d'unité, je materai ça à l'occase, tiens.

[Sk-flown]

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.

Et si la base nous emmène sur la mauvaise voie?

(en parlant de Pathfinding ça tombe bien)

[Krobill]

Remettre en question le travail des anciens est salvateur certes. Mais l'ignorer, sous pretexte de ne pas se polluer l'esprit, est juste... Arrogant. Einstein ne devait sûrement pas ignorer les bases de la physique classique quand il a pondu la théorie de la relativité

[_tibo_]

Article très intéressant, merci ! Ça me donne envie de refaire un peu de code, tout ça...

[LPTheKiller]

Merci pour vos réponses, qui sont très intéressantes.

Au niveau de la réinvention de la roue, je tiens quand même à préciser que les scientifiques passent une bonne partie de leur temps à vérifier et à préciser les résultats des autres. Et donc à refabriquer cette roue, qu'ils ont vu dans la publication scientifique, chez eux.
(Voir à ce propos le Science & Vie qui parlait des arnaques scientifiques, beaucoup plus courantes qu'on peut le croire, où des chercheurs créent des données et résultats sous la pression du stress et des attentes de leurs supérieurs.)

Ensuite, il faut bien vous rendre compte que je n'ai sans doute pas encore le niveau pour me mettre à la pointe de la recherche, en synthétisant tous les travaux précédents, tout simplement parce que je sors à peine de Terminale et que j'entre seulement en école d'ingénieurs dans quelques jours.

Ceci n'était qu'une simple distraction de vacances, un jeu que j'avais envie de faire vite-fait et moi-même.

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.

En fait, il y a beaucoup de choses que je n'ai pas dites, pour alléger l'article. Mais sache que lorsque le joueur disparaît du champ de vision du computer, celui-ci tente uniquement de rejoindre sa dernière position connue. Il ne sait pas où va le joueur ensuite.
Mais s'il entend un bruit, provenant de l'autre côté d'un obstacle, il ira voir ce qu'il se passe dans les environs (il y a introduction d'une approximation, fonction inverse de l'intensité du bruit entendu).
Dans tous les cas il ne sait jamais la position du joueur avant de l'avoir vu.

[Lorenzo77]

Salut,

Il est bien moins gourmand de placer des waypoints au moment de la conception (comme sur les maps d'unreal), ca évite toute la phase de calcul lourd puisque l'IA dans ce cas ce limitera a passer par le moins de point possible entre A et B

[LPTheKiller]

Salut,

Il est bien moins gourmand de placer des waypoints au moment de la conception (comme sur les maps d'unreal), ca évite toute la phase de calcul lourd puisque l'IA dans ce cas ce limitera a passer par le moins de point possible entre A et B

Oui je sais ça a déjà été remarqué
C'est une technique que je connaissais vaguement mais je ne m'étais jamais penché dessus, et il est vrai qu'elle conviendrait assez bien pour mon jeu, du moins sous réserve de quelques perfectionnements, que j'envisage bien.

[titi3]

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.

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.

Merci pour vos éclaircissements En lisant l'article j'étais loin de m'imaginer la complexité du pathfinding pour un jeu simple, c'est dire pour les blockbusters même si les moyens sont différents

[rOut]

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.

A force d'utiliser le GPU pour tout faire (la physique, le pathfinding, etc), la pauvre carte graphique ne va même plus avoir le temps d'afficher les images

[Ravine]

J'ai lu un peu de tout dans ce thread au niveau intervention, et je rejoins les gens qui t'enjoignent a te documenter sur les travaux effectues sur les parcours de graphes. C'est un probleme "classique" d'algorithmique, qui a donne naissance au Djikstra et au A* (et a des cousins comme les BFS et DFS).

Vouloir reflechir par soi meme est louable, et comme dit precedemment, ignorer les decennies de recherche sur le sujet est au mieux idiot, au pire une enorme preuve d'orgueil. Mais rien de mieux pour guerir ca que de se rendre compte du temps perdu a imaginer une solution non optimale quand il existe des solutions meilleures, plus simples (ce qui devrait t'arriver tout le temps si tu t'echines a vouloir reinventer la roue).

2 petits liens au passage qui m'ont bien servi quand j'etais a plancher sur un exercice de pathfind/IA : un article de Gamasutra sur le pathfind (assez court mais tres bien ecrit et clair); et la page du celebre Amit, une espece de reference sur le sujet de l'internet, qui a le merite aussi bien d'aborder les algorithmes de parcours que les methodes de representation de l'espace et les problemes de partitionnement de celui ci.

Cela n'enleve rien au travail effectue, et j'avoue avoir beaucoup aime ton jeu. L'ambiance y est excellente, et on s'y croirait.

[LPTheKiller]

Ce n'est pas du temps perdu. Je le répète, ce n'était qu'à but ludique, et je n'avais pas la tête à aller fouiner dans la de la documentation pour essayer de reprendre des systèmes que je sais par ailleurs pertinemment être meilleurs.
Mon système ne m'a d'ailleurs pris que 4 ou 5 jours (réflexion + implémentation) sur le mois que m'a pris le jeu (à peu près). <= Ces temps sont des temps en période de vacances, c'est à dire que je me suis surtout détendu et j'ai fait autre chose que de la prog.

Merci pour les liens.

[Seboss]

A propos de réinventer la roue bien, pas bien, je pense que du moment qu'on comprend ce qu'on écrit, ça n'a finalement pas beaucoup d'importance.
Trouver la solution soi-même peut être intellectuellement très stimulant, mais je pense que globalement on gagne du temps et on apprend aussi beaucoup en réimplémentant une solution éprouvée.
Méfiez-vous juste du code que vous ne comprenez pas.

[fofo]

(Pour info, c'est pas applicable pour du flash je pense)

T'as l'algo des fourmis, hyper simple mais qui nécessite un langage compilé (ie. Performant) :
Tu définies ta carte en matrices.

Tu codes une routine toute conne (mais qui doit être hyper performante genre en C voir assembleur) :
- Chercher la case adjacente aléatoirement en préférent les cases déjà marquées
- Marquer dans la matrice les cases sur lesquelles tu es passé.
- S'arrêter dés que t'arrive au point B (ou relancer la fourmi du point A)

Lancer les fourmis du point A (ie. Appeler un bon nombre de fois ta routine)

Qu'est ce qui va se passer :
- Initialement toute ta matrice est à 0, les premières fourmis vont partir au hasard.
- Les premières fourmis qui arrivent sont celles qui ont trouvées un chemin plus rapide que leur soeurs,
- Au prochain passage les fourmis auront tendances à préfèrer le chemin déjà marqué par les plus rapides.

Au bout d'un certain temps, tu tues toutes les fourmis (oui c'est sauvage), et tu suits le chemin le plus marqué pas forcément optimal mais plutôt rapide.

Les avantages sont multiples:
- Tu peux fixer un temps maximal pour trouver un chemin, (plus tu laises les fourmis se baladée, plus se sera précis, mais rapidement tu as une tendance plutôt bonne).
- Tu peux peux "pondérer" tes chemins (par ex. Dans l'eau ton gus marche moins vite, donc tu marques moins fort la case ou ta fourmi passe, en ville c'est limité en 50, sur le périph. 130...etc).
Inconvénients:
- Faut un langage performant sinon c'est trèèès long,
- Faut un peu bricoler pour trouver le bon nombre de fourmis, et l'algo pseudo aléatoire.

C'est ce genre d'algo (avec pas mal de mise en cache), qui permet à Mappy et autres google map de trouver des chemins instantanément à travers la France.

ça sert aussi dans les réseaux pour trouver quels routeurs utiliser.

C'est ce que font les fourmis dans la nature pour trouver et ramener de la bouffe :
- Toutes partent au hasard en laissant une trace de phéromone,
- Dés qu'une fourmi trouve de la bouffe, elle la ramène à la maison, en suivant le chemin qui sent le plus les phéromones.

T'as qu'a observer les fourmis elle se suivent très rapidement vers le plus court chemin pour la bouffe.

Edit un lien : http://fr.wikipedia.org/wiki/Algorit...ourmis#Origine

[rOut]

(Pour info, c'est pas applicable pour du flash je pense)

T'as l'algo des fourmis, hyper simple mais qui nécessite un langage compilé (ie. Performant) :
Tu définies ta carte en matrices.

Tu codes une routine toute conne (mais qui doit être hyper performante genre en C voir assembleur) :
- Chercher la case adjacente aléatoirement en préférent les cases déjà marquées
- Marquer dans la matrice les cases sur lesquelles tu es passé.
- S'arrêter dés que t'arrive au point B (ou relancer la fourmi du point A)

Lancer les fourmis du point A (ie. Appeler un bon nombre de fois ta routine)

Qu'est ce qui va se passer :
- Initialement toute ta matrice est à 0, les premières fourmis vont partir au hasard.
- Les premières fourmis qui arrivent sont celles qui ont trouvées un chemin plus rapide que leur soeurs,
- Au prochain passage les fourmis auront tendances à préfèrer le chemin déjà marqué par les plus rapides.

Au bout d'un certain temps, tu tues toutes les fourmis (oui c'est sauvage), et tu suits le chemin le plus marqué pas forcément optimal mais plutôt rapide.

Les avantages sont multiples:
- Tu peux fixer un temps maximal pour trouver un chemin, (plus tu laises les fourmis se baladée, plus se sera précis, mais rapidement tu as une tendance plutôt bonne).
- Tu peux peux "pondérer" tes chemins (par ex. Dans l'eau ton gus marche moins vite, donc tu marques moins fort la case ou ta fourmi passe, en ville c'est limité en 50, sur le périph. 130...etc).
Inconvénients:
- Faut un langage performant sinon c'est trèèès long,
- Faut un peu bricoler pour trouver le bon nombre de fourmis, et l'algo pseudo aléatoire.

C'est ce genre d'algo (avec pas mal de mise en cache), qui permet à Mappy et autres google map de trouver des chemins instantanément à travers la France.

ça sert aussi dans les réseaux pour trouver quels routeurs utiliser.

C'est ce que font les fourmis dans la nature pour trouver et ramener de la bouffe :
- Toutes partent au hasard en laissant une trace de phéromone,
- Dés qu'une fourmi trouve de la bouffe, elle la ramène à la maison, en suivant le chemin qui sent le plus les phéromones.

T'as qu'a observer les fourmis elle se suivent très rapidement vers le plus court chemin pour la bouffe.

Edit un lien : http://fr.wikipedia.org/wiki/Algorit...ourmis#Origine

Ca ne m'étais même pas venu à l'idée. Mais c'est super bien trouvé comme algorithme en fait :aimelesanimaux:

Et puis tu peux toujours mettre à jour tes chemins en temps réel, en ajoutant un peu de variabilité au lieu de suivre bêtement les chemins créés à l'avance.

[LPTheKiller]

Tiens c'est marrant çe truc

Je connaissais ce fonctionnement chez les fourmis mais je savais pas que ça avait été réutilisé en informatique...

Pour le Flash, tout dépend à quelle fréquence l'algo est appelé. Si c'est en continu à chaque frame c'est pas possible, mais si c'est une fois de temps en temps pourquoi pas, je pense que ça peut se faire, on pourrait d'ailleurs étaler les calculs sur plusieurs frames : ça ferait que le perso précise son chemin au fur et à mesure qu'il avance.

Dans un jeu comme le mien, je pense que ça pourrait être envisageable, car le pathfinding n'est pas invoqué en continu (même s'il y a poursuite d'objets dynamiques : C'est soit il le voit et il va tout droit dessus ; soit il le voit pas et il rejoint sa dernière position connue).
Mais la solution me paraît pas du tout optimale. Ca marcherait mieux pour des labyrinthes ou des trucs comme ça.

Je vais réécrire mon pathfinding en utilisant Dijkatruc, en y mélangeant mes algos détections d'obstacles, et en faisant du wayPointing automatique en reprenant mon idée des coins caractéristiques des blocs. Ca devrait super bien marcher.

[Triz']

- Chercher la case adjacente aléatoirement en préférent les cases déjà marquées
- Marquer dans la matrice les cases sur lesquelles tu es passé.
- S'arrêter dés que t'arrive au point B (ou relancer la fourmi du point A)

(...)

- Initialement toute ta matrice est à 0, les premières fourmis vont partir au hasard.
- Les premières fourmis qui arrivent sont celles qui ont trouvées un chemin plus rapide que leur soeurs,
- Au prochain passage les fourmis auront tendances à préfèrer le chemin déjà marqué par les plus rapides.

Au bout d'un certain temps, tu tues toutes les fourmis (oui c'est sauvage), et tu suits le chemin le plus marqué pas forcément optimal mais plutôt rapide.

Faut lancer beaucoup de fourmis alors.

Si une majorité part du mauvais coté au début, le chemin le "plus marqué" fera systématiquement un détour.

Non ?

[ducon]

Ça fait beaucoup de calculs quand tu veux déplacer une seule unité à l’autre bout de la carte.

[LPTheKiller]

Faut lancer beaucoup de fourmis alors.

Si une majorité part du mauvais coté au début, le chemin le "plus marqué" fera systématiquement un détour.

Non ?

Je pense que si tu jauge bien les paramètres, tu peux faire en sorte que ça arrive le moins possible, et que la rapidité d'atteinte de l'objectif renforce assez la meilleure voie pour éclipser les premiers aléas.

[szwip]

Je m'étais déjà amusé avec l'algo des fourmis, mais c'est effectivement très lourd. Et si le nombre d'itération n'est pas infini, on n'est pas assuré d'être sur le chemin optimal. Du coup, on obtient souvent de bon chemin, mais à l'allure un peu erratique.

[rOut]

Avec une implémentation sur le GPU ça doit le faire, ça à l'air de bien se paralléliser.

[SnakesMaster]

Ca me rappelle l'époque où je voulais implémenter l'algo de djikstra juste avec ce que j'avais appris à faire en terminale ES spé maths, sans wikipedia ou autre aide... Ya pas à dire, dessiner ça rend les choses plus simples ! Et je suis pratiquement certain que tu prends le temps de faire de la pédagogie parce que ça t'aides toi à clarifier ton problème !

Quand on peut expliquer sans ambiguité sa problematique à un novice, on rend le probleme bien plus clair pour soi même !