A étoile [A star, A*]

Bonjour,

J'aimerais implémenter l'algorithme de recherche du chemin le plus cours (A*) avec javascript. malheureusement je n'ai rien trouvé sur développez et sur Internet je ne trouve que des pseudo-code incompréhensible.

Quelqu'un pour-t-il me donner un pseudo-code simplifier et un code source ?

merci...

:D ce pseudo code incompréhensible s'appelle algorithme. et y a que ça sur ce forum :mouarf3:

Excuse moi mais je sais ce ke c qu'un algorithme... :D

Tu l'as toi ce pseudo-code (algorithme) ?

Tu veux un code source en quel langage ? JS ? Ca va être difficile :(

j'ai pas de pseudo-code ni de code source, mais une explication très détaillée du fonctionnement de l'algo, a partir de laquelle ça ne doit pas etre très dur d'implémenter l'algo.

(je dis ça mais j'ai jamais essayé)

http://www.gamedev.net/reference/articles/article2003.asp

pas mal le lien

merci pour le lien :wink:

je l'avais dj trouvé au paravent mais le lien de traduction francaise était naze...

je l'avais laisser de coté pour chercher une version francaise...

merci... un peut de traduction me fera pas de mal

++

Le principe est très .. intuitif.
Tu réalises une exploration jusqu'au chemin final.
A chaque nouvelle étape que tu vas évaluer le coût de passer par cette étape comme étant le coût connu (somme de coûts réels d'étape à étape) pour y arriver, plus le coût estimé pour aller jusqu'à l'arrivée (une heuristique comme p.ex. une distance ||Arrivée-Etape||).
A chaque itération, tu choisis comme point de départ l'étape de plus faible coût total estimé.

Bonjour,

Le lien donne une explication bien compliquée pour un algorithme simple :

Supposons que l'on ait un graphe qui permette de connaitre les liens de chaque noeud (noeuds contigus) et la distances correspondante.

Pour trouver le plus court chemin d'un noeud A à un noeud B, on calculera calculera le plus court chemin du noeud A à tous les noeuds du graphe.

On a besoin comme de définir pour chaque noeud du graphe les valeurs suivantes :
- DA(X) : distance d'un noeud X à A (que l'on initialisera à "infinie").
- PR(X) : prédecesseur de X sur le chemin B à A.

ProcessNode est la procédure permettant de traiter tous les noeuds contigus d'un noeud X.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Procedure ProcessNode(X) ; begin Pour i de 1 au nombre de noeuds contigus à X : begin Y=noeud_contigu(X,i) distance_ Y_ à_ A_via_X = DA(X) + Dist(X,Y) si distance_ Y_ à_ A_via_X < DA(Y) : begin DA(Y) = distance_ Y_ à_ A_via_X PR(X) = Y ProcessNode(Y) end end end

---

On fait ProcessNode(A) et, au retour, on a la distance dans DA(B) et on récupére le chemin en parcourant les prédecesseurs de B jusqu'à A.
Evidement, Si DA(B)="infinie", il n'y a pas de chemin de A à B.

Pour optimiser dans une application réélle, on peut modifier l'ordre de parcours des noeuds contigus en utilisant des informations "géographiques" afin de traiter la ligne droite AB en priorité. On a alors des chances de tomber assez vite sur le point B. On peut alors comparer, dans la procedure processNode, DA(X) à DA(B) et si DA(X)>DA(B) il est alors inutile de traiter le noeud X.

merci... beaucoup...

voila qqe autres liens très interressants et qui ont été difficiles à déniché...

l'article :
http://www.policyalmanac.org/games/aStarTutorial.htm

le lien mort retrouvé...
http://blog.lalex.com/archives/20030...thfinding.html

Wikipédia:
http://fr.wikipedia.org/wiki/Algorithme_A%2A

Geocities:
http://www.geocities.com/jheyesjones/astar.html

voila....

je n'ai pas encore tout compris le system... mais j travail...

merci encore pour votre aide :wink: