Voir la version complète : le pathfinding...
salu a tous
voila je me penche un peu ( en amateur ) sur le PATHFINDING.
mon but pour le moment est simple aller d un point A a un point B avec un mur entre les 2. j ai un petit code pas tout a fait et un peu bancal mais au moins j arrive a faire deplacer mon carré en contournant le mur.
j ai trouver tout un tas d article sur internet qui explique le pathfinding A star, mais j ai du mal a coder les diverces solution proposées. d'autant que certains donnent des solutions recurcves et que d autres les deconceillent fortement... je sais pas trop sur quel pied dancer.
http://www.lalex.com/blog/archives/200309/49-traduction-article-sur-pathfinding.html
http://www.vieartificielle.com/article/?id=161
est ce que quelqu'un a une connaissance dans se domaine, ou pourrait simplement m'indiquer des tutos ou plein de truc sur ce sujet ?
merci :00000023:
... dsl je sais pas si c'est bien la place de se topic mais je voyais pas ou le mettre sinon
Si tu es interressé, j'ai quelques sources d'algos A*. Contacte moi en PM pour que je t'envoie les fichiers.
tyrion42
19/04/2005, 15h10
Un récapitulatif qui est très bien fichu, il parle des différents modes, d'options (recherche partiel, ...), sur une note de 1 à 10, je lui donne 9 :D
http://theory.stanford.edu/~amitp/GameProgramming/
merci pour les reponces..
ahhh l article est en anglais ca ma me faire enore plus mal au cerveau :00000013: :00000013: :00000013: ( mais ou j ai mis mon dico d anglais...^^)
Un article sur le GCN, tant qu'à faire ;)
http://www.games-creators.org/index.php/Introduction_au_pathfinding
Et pour le principe de l'impémentation, c'est comme un parcours d'arbre en largeur, avec une liste (avec priorités pour Dijkstra et A*)
Je crois qu'il faut rester réaliste et ne pas aborder l'algorithme du A* directement, sans autres notions :)
Il faut bien comprendre que cet algorithme est une amélioration "intuitive" d'autres algorithmes.
Commence par étudier la théorie des arbres, des recherches de plus court chemin (cf parcours en largeur), ensuite vois l'algorithme de dijkstra et comprends le bien avant d'étudier le A*
Oui je pense aussi que lui conseiller A* sans savoir quel est son niveau de progra peut-etre un peu dure :)
C'est vrai que savoir par ou commencer n'est pas chose facile .
Si tu "débute" en programmation , je te conseil comme mon prédécesseur de te renseigner sur les arbre ( pas trop dans le détail si tu n'a aps le temps ) mais au moins de voir comment ca marche .
Aprés, la notion de graphe vient d'elle meme .
Enfin , si tu veut t'attaquer a l'implémentation de A*, je te conseil un article de gamedev ( c'est celui que j'ai utilisé pour coder une version peu performante certe, hideuse niveau code, mais fonctionel de A* il y a quelques mois ) ( je te retrouverais le liens si tu ne le voit pas ).
Mais avant ca, il va tout de meme te faloir quelques bases concernant :
- savoir choisir / utiliser les conteneu de la STL correctement .
Bon courage :)
Moi j'ai utilisé un autre article qui expliquait bien pour coder A* en Python. J'ai pas tout compris mais j'ai simplement traduit le pseudo-code qu'ils mettent à la fin :00000025: . Bon au final, j'ai un truc pas trop crade mais qui met 20 secondes sur mon P4 avec une carte de 100*100. Mais quelques centiemmes sur une carte 10*10. Pour un jeu, je pense pouvoir diviser le temps de l'algo, en le faisant rechercher à chaque boucle par exemple 3 cases, plutot que tout le chemin. Mon algo aura finit avant même que l'unité soit à la moitié du chemin.
Moi j'ai utilisé un autre article qui expliquait bien pour coder A* en Python. J'ai pas tout compris mais j'ai simplement traduit le pseudo-code qu'ils mettent à la fin :00000025: . Bon au final, j'ai un truc pas trop crade mais qui met 20 secondes sur mon P4 avec une carte de 100*100. Mais quelques centiemmes sur une carte 10*10. Pour un jeu, je pense pouvoir diviser le temps de l'algo, en le faisant rechercher à chaque boucle par exemple 3 cases, plutot que tout le chemin. Mon algo aura finit avant même que l'unité soit à la moitié du chemin.
Il me semble que pour un jeu, on utilise la recherche de chemin dans des threads mais pas sûr.
Ah oui tiens bonne idée. merci :00000025:
Lenolian
08/07/2005, 10h57
Une autre optimisation est de faire un pathfinding avec différente granularités.
Lors de la demande de déplacement, l'algorithme utilise une vision grossière de la carte et détermine rapidement un itinéraire général pour l'unité. Lors de l'itération suivante, l'algorithme est relancé mais cette fois pour une petite partie de l'itinéraire et va trouver un chemin précis sur cet endroit la carte.
Par exemple pour cherche son chemin dans un dongeon qui est constitué de différentes pièces. Le premier passage de l'algorithme va trouver quelles pièces il faut traverser pour atteindre l'objectif. Lors de la prochaine réactualisation de l'IA, l'algorithme va maintenant chaerche le meilleur chemin à l'intérieur de la prémière pièce, et ainsi de suite pour chaque pièce jusqu'à l'objectif.
L'avantage c'est que la recherche de chemin est distribué sur plusieurs frames donc elle a moins d'impact sur le frame rate, et de plus comme à chaque recherche le nombre de possibilité est réduit l'algorithme va plus vite.
Une autre optimisation est de faire un pathfinding avec différente granularités.
Lors de la demande de déplacement, l'algorithme utilise une vision grossière de la carte et détermine rapidement un itinéraire général pour l'unité. Lors de l'itération suivante, l'algorithme est relancé mais cette fois pour une petite partie de l'itinéraire et va trouver un chemin précis sur cet endroit la carte.
Par exemple pour cherche son chemin dans un dongeon qui est constitué de différentes pièces. Le premier passage de l'algorithme va trouver quelles pièces il faut traverser pour atteindre l'objectif. Lors de la prochaine réactualisation de l'IA, l'algorithme va maintenant chaerche le meilleur chemin à l'intérieur de la prémière pièce, et ainsi de suite pour chaque pièce jusqu'à l'objectif.
L'avantage c'est que la recherche de chemin est distribué sur plusieurs frames donc elle a moins d'impact sur le frame rate, et de plus comme à chaque recherche le nombre de possibilité est réduit l'algorithme va plus vite.
Ptet qu'ils font ça dans le thread aussi non ? =) Comme ça en même temps ça ne bloque pas le jeu, et ça répond plus vite aux commandes!
Ptet qu'ils font ça dans le thread aussi non ? =) Comme ça en même temps ça ne bloque pas le jeu, et ça répond plus vite aux commandes!
Un thread par définition ne bloquera pas ton jeu. Vu qu'il s'agit d'un 'processus' qui tourne en parallèle de ton thread principal. D'ou tout l'intérêt de placer les calculs longs et fastidieux (style tout ce qui concerne l'intelligence artificielle) dans un thread séparé.
[EDIT] Hum, oui sorry, j'avais lu trop vite :D. Donc on est d'accord [\EDIT]
Lenolian
08/07/2005, 13h41
Je me suis sans doute mal exprimé, je ne voulais pas dire que c'était une méthode de remplacement pour l'utilisation des thread mais plutôt une méthode qui combinée avec les threads permet d'avoir encore de meilleures perfs.
L'utilisation d'un thread dédié n'empêche pas d'optimiser l'algorithme, bien au contraire. Car même dans un thread un calcul complexe reste un calcul complexe et va mettre du temps à se résoudre. En réduisant la compléxité de chaque recherche de chemin, on obtient une réponse beaucoup plus rapide et surtout on linéarise (pas trouvé de meilleur terme) la charge de travail pour le thread.
En réduisant la compléxité de chaque recherche de chemin, on obtient une réponse beaucoup plus rapide et surtout on linéarise (pas trouvé de meilleur terme) la charge de travail pour le thread.
Oui voilà c'est ce que j'voulais dire par "réponse plus rapide" ;).
Au lieu que le personnage ne réponde pas avant d'avoir trouvé le chemin complet après un ordre de déplacement, il va commencer à se déplacer même si le thread n'a pas fini de trouver le chemin complet, dès que le thread aura trouvé le chemin préliminaire.
et comment tu fais pour trouver un chemin préliminaire ?
J'ai fait un pathfinding qui utilise A* , et je ne vois pas comment on peut faire ça .Pour moi tant que l'algo n'a pas trouvé la cible , les données sont inexploitables , il n'y a qu'à afficher les cases open et closed pour s'en rendre compte , on voit bien l'exploration de la map par l'algo , mais on ne peut pas envoyer le perso sur toutes ces pistes :)
Mais si tu as un truc pour calculer un chemin préliminaire,je suis preneur .
Lenolian
16/07/2005, 20h15
Il faut définir plusieurs niveaux de recherches. En prenant comme exemple un donjon avec 20 salles de chacune 100 tiles. Tu construis un graphe entre tes salles represantant les connections entre ces salles. Ensuite pour chaque salle tu construis un autre graphe qui permet de naviguer à travers les tiles de cette salle.
Lorsque tu lance une recherche pour la 1ère fois, tu étudies le graphe des salles. Vu leur nombre limité c'est rapide et tu obtiens une liste de salles donnant un chemin grossier que ton unité va suivre. Puis tu lances la recherche pour la 1ère salle, ce qui va donner le chemin final que l'unité doit suivre pour arriver à la prochaine salle. La recherche s'arrête la pour l'instant. Lorsque ton unité arrive enfin près de la seconde salle, tu lances ton algorithme pour trouver le chemin à travers la seconde salle. Et ainsi de suite jusqu'à arriver à destination.
Donc au lieu d'effectuer une recherche sur 2000 noeuds (20 salles x 100 tiles) en une seule fois. On effectue une recherche sur 20 noeuds seulement pour trouver un chemin grossier, elle s'effectue donc très rapidement. Puis pour chaque salle la recherche se fait sur 100 noeuds, ce qui se fait aussi rapidement. De plus les recherches sont étalées sur plusieurs frames, ce qui atténue encore plus leurs effets sur le framerate.
C'est un exemple simple avec seulement 2 niveaux, mais c'est bien evidemment extensible.
ok comme ça je comprends mieux , merci :)
Alors il me reste à apprendre à utiliser les threads pour la recherche du chemin ,dans un premier temps je vais chercher la totalité du chemin , on verra pour les étapes intermédiaires quand je saurai faire un thread :)
Vous avez jamais pensé à coder une IA qui fait du pathfinding avec une connaissance partielle du labyrinthe ?
Vous avez jamais pensé à coder une IA qui fait du pathfinding avec une connaissance partielle du labyrinthe ?
Si si je l'ai déjà fait , c'était tellement réaliste , que le perso ne trouvait jamais son chemin c'est te dire à quel point la simulation était poussée :)
vBulletin® v.3.6.5, Copyright ©2000-2009, Jelsoft Enterprises Ltd. Tous droits réservés - Version française vbulletin-fr.org