Coder son pathdinfing : comment commencer ???

Salut tout le monde,

Bon, je ne sais pas si je devais poster ici mais étant donné que le sujet concerne surtout les algos de pathfinding et surtout A*, je pense que c'est le bon endroit...

En fait je bosse depuis quelques jours là dessus, j'ai lu plusieurs docs à ce sujet, et je pense avoir bien saisi le fonctionnement de l'algo A*.... En revanche, je bloque complétement pour son codage : je ne sais pas vraiment par où commencer, ni comment organiser mon code, quelles structures de données utiliser... :?

Par exemple, pour les Open et Closed Lists, quel type de données vaut-il mieux utiliser??? Tableau, liste chaînée, ...? Comment représenter l'espace : une matrice d'entiers, une matrice d'instances d'une classe point ???

J'espère que vous pourrez m'aider, merci d'avance... Et puisqu'on est encore seulement le 3, bonne année à tous !!!


PierreAd


PS : j'aurais aimé coder ça en OO, mais si vous avez d'autres idées (peut être plus simples pour un premier jet) n'hésitez pas ;-)

Je n'arrive pas à comprendre ton problème ; pq veux-tu utiliser l'algorithme de A* ?
Tout dépend ce que l'on veut faire....
ce sujet a déja été abordé sur le forum.

Sinon voir le site de Matt Buckland et autre comme Gamedev.net

Chercher sur
http://www.wordware.com/files/games/
il ya des exemples de code source en anglais

Tu peux très bien représenter l'espace par une matrice de coordonnées.

La structure de donnée à utiliser est une file de priorité, la meilleure complexité étant obtenue avec un tas de Fibonacci. Par contre c'est un peu délicat à implémenter, donc tu peux envisager plus simple je pense (genre une liste triée ?) :wink:. Note aussi que selon le langage utilisé, tu auras sûrement déjà en standard des structures de files de priorité.

Enfin, personnellement je n'utilise pas de liste Closed (jamais compris quel était son intérêt, par rapport au fait de stocker cette info directement dans les noeuds).

Citation:

---

Je n'arrive pas à comprendre ton problème ; pq veux-tu utiliser l'algorithme de A* ?
Tout dépend ce que l'on veut faire....
ce sujet a déja été abordé sur le forum.

---

Ce n'est pas pour faire quelque chose de particulier, simplement pour appréhender un peu mieux cet algo et apprendre toujours un peu plus, et par la même occasion coder un peu plus :wink:... je sais que le sujet avait déjà été abordé, mais ce n'est pas tant le déroulement de l'algo à strictement parler qui me posait problème, mais la façon dont je devais représenter mes données

Citation:

---

Enfin, personnellement je n'utilise pas de liste Closed (jamais compris quel était son intérêt, par rapport au fait de stocker cette info directement dans les noeuds).

---

C'est pas faux ! enfin quoiqu'il en soit, il faudra toujours une open list :roll:


En tout cas merci de vos réponses, je vais essayer de regarder un peu ça si j'arrive à me bloquer une heure ou deux ce week end.

Bon week end a vous,


PierreAd

Comme je te l'ai dit, pour la liste Open il faut une file de priorité (triée). Si tu es en Java ou en C++ tu as des conteneurs standards style set ou priority_queue qui, sans être optimaux, font déjà bien le boulot.

Pour l'avoir codé et si tu recherches du pédagogique le fonctionnel serait mieux que l'OO, mais je suppose que ça peut s'appliquer à ce que tu veux.
Tu peux englober le type que tu veux en A*, pourvu que tu puisse faire les traitements appropriés sur ce type.

Moi non plus pas de closed list, mais j'avais une liste de noeuds déjà parcourus (c'est peut être la même chose?)

(Moi je viens de finir un SSS*, c'est plus rigolo, mon puissance4 m'explose à chaque fois lol)