Pathfinding : ca avance, et en 3D isométrique !
Par -Alexandre LEGOUT aka LAlex- le vendredi, août 29 2003, 12:43 - Projets - Lien permanent
J'avance bien sur mon algo de pathfinding. En fait, j'avais fait un peu n'importe quoi dans ma première implémentation (mal compris l'explication de l'algo en anglais), et là j'ai tout repris en me basant sur l'implémentation de zeh (voir lien plus bas). Sans reprendre son algo, cela m'a permi de mieux le cerner, et de pouvoir l'implementer correctement. En fait, ce qui change par rapport au sien, ce que mon implémentation est faite en POO, alors que la sienne est une "simple" fonction, qui prend un tableau à deux dimensions en paramètre.
La structure de mes classes est en fait assez simple : une classe 'Map', qui contient la méthodes findPath, et qui prend en paramètre les coordonnées de départ et d'arrivée. Une classe 'Tile', qui constitue la base de chaque élément de la carte, et qui est étendue par des classes 'Wall', 'Floor', 'Sand', etc... qui vont représenter les différents type de terrain.
Apparemment, il est assez optimisé (j'en ai d'ailleurs profité pour suggérer quelques mini-optimisations à l'auteur du pathfinding précédemment cité), et j'arrive à obtenir des performances trés légerement meilleures, alors que tout est codé en objet : je n'en revient pas moi-même !!! En fait, de par l'implémentation objet et l'utilisation des "pointeurs" de Flash (utilisation des références et non pas des valeurs), j'arrive à éviter certaines boucles... Par contre, le temps que vous voyez affiché sur l'image est pour le Flash Player 7 (beta v7.0.2.0), qui est bien plus rapide que le 6 ...
J'en ai profité pour créer une méthode d'affichage en 3D isométrique, parce que je trouve ca plus joli ... 
Dés la sortie de Flash MX 2004, je le refait en ActionScript 2, et je mettrai les sources à disposition ici-même !
Je pense également faire prochainement une explication en français de l'algorithme A* pour le pathfinding, basé sur ce que j'en ai compris, et axé sur la pédagogie pour le mettre à la portée du plus grand nombre.
Commentaires
coucou lalex!
A tu entendu parlé de l'algo de Diijstra ?
En connais tu les difference?
a+
ps: sympa la map iso
ps: pourrait tu mettres les "interfaces" des classes que t'as crée
Il s'agit de l'algorithme de "Dijkstra" (et non pas "Diijstra") ...
La différence est que l'alogithme A* se base sur le "poids" de la distance parcourue, mais aussi sur une estimation de la distance restant à parcourir. Sans cela (cad avec l'algo de Dikjstra), partir dans le sens opposé au point d'arrivée a la même signification que partir dans la bonne direction. Ce qui fait que plus de cases sont testées, donc plus long ...
Pour les classes, je les donnerai en même temps que le code complet ... A+
Heu ... le titre, c'est pas plutot Pathfinding ?
Oups ..... C'est rectifié maintenant. Merci neo !
je voudrai savoir si vous pouvez m'envoyer le pricipe de l'algo de dijkstra pour que je puisse créer un programme qui vous facilitera le travail
Elamine > Qui me facilitera quel travail ? :o
J'ai déjà publié une classe de pathfinding sur ce même blog : http://www.lalex.com/blog/archives/200309/61-pathfinding-arbres-binaires-pas-mieux.html
++ ^^
lalex... tu acceptes les url qui vont vers des sites de craking ?
(regarde au dessus)
bye
eka > C'est un site d'information ! Et encore, c'est trés léger comme information ... Donc ca ne me dérange pas plus que ca, bien que je n'encourage absolument pas ce genre de pratiques ...
Moock met bien un lien vers ASV sur son blog !
++ ^^
je parlais + du site de Elamine qui parle au dessus
enfin pas grave c'est pas un forum ici 
eka > Oui, j'avais bien compris, et ma réponse parle bien de ca !
je ne comprends pas le système de parent...
comment est-ce que l'on retrouve le chemin?
merci d'avance
Salut, j'ai créé une assos informatique au sein de mon école de méca. Un des adhérent s'intéresse à la programation en C et plus partculièrement au pathfinding. Dans notre assos on dispose de licenses visual c++ 6.0 pourriez-vous m'expliquer et si vous savez en faire m'envoyer un programme de pathfinding en langage C.
Merci d'avance, l'assos info !
@Charles> Tu trouveras une explication de l'algo ici : http://blog.lalex.com/archives/200309/49-traduction-article-sur-pathfinding.html
Il n'y a plus qu'a implementer ensuite!
++ ^^
Salut!
J'ai moi aussi programmé un pathfinding basé sur A* est qui est fonctionnel.
Il peut rechercher un chemin dans un environnement de type matrice 2D ou 3D.
La matrice peut contenir des coefficients qui influent sur la recherche si l'on désire rechercher le meilleur chemin (et pas forcément le plus court).
C'est programé en C++, c'est une classe object, c'est multi-plateforme et sous licence GNU/GPL => voir sur http://spomky.com/?p=4
bonjour, j'ai vu votre discussion par rapport a l'implémentation de lalgo A*. cet algo m'interessse beaucoup car je dois l'utiliser dans mon projet en écol d'ing.
sauf qu'en C++ je suis pas un bon! donc j'aurai besion de votre aide.
en fait moi j'ai une matrice creuse dans un fichier que je récupere sous forme d'une map et je dois faire un calcul d'optimum en creeant un arbre et le parcourir pour trouver l'optimum . avec bien sur calcul d'estimation a chque noeud pour descendre en profendeur que quand c'est nécesssaire juska ckon tombe sur l'optimum.
je voulais donc savoir si c'est possible que quelqu'uun puisse m'aider un trouver un code qui permet ceci! merci beaucoup.
Fil des commentaires de ce billet