PathFinding et Arbres binaires ... pas mieux !
Par -Alexandre LEGOUT aka LAlex- le lundi, septembre 29 2003, 18:53 - Projets - Lien permanent
Comme le préconise Patrick Lester dans son article Using Binary Heaps in A* Pathfinding, j'ai implémenté le gestion de la liste ouverte sous forme d'arbre binaire (binary heap) que l'on conserve trié en permanence pour ne pas avoir à chercher la case ayant le cout minimum en bouclant sur la liste ouverte. Et bien dans l'état actuel des choses, ce n'est pas plus performant !!! 
Pourtant, de ce que j'en ai compris, cela devrait aller beaucoup plus vite ! 8O Mais une petite surveillance su temps pris par chaque étape de la recherche indique que cette boucle sur la liste ouverte n'est pas ce qu'il y a de plus lent ... et en plus, chaque fonction indépendemment prend moins de 1ms., donc impossible de tracer le temps ... :?
Voila donc un exemple qui fait la comparation des deux méthodes sur chaque fois le même trajet. La carte est de dimensiosn 30x30 pour tester sur un peu plus grand que précédemment. Vous pouvez aussi télécharger le fichier source de la classe PathFinder.as ... si vous découvrez une explication, n'hésitez pas à me faire signe ! 
L'activation des arbres binaires se fait avec la variable statique BINARY_HEAPS qui est un booléen.
Commentaires
Salut lalex
D'abord je tiens à saluer ton beau boulot
Je veux juste te signaler qu'après quelques tests , la solution avec l'ABR est plus performante dès lors que le chemin est long (tester avec angle bas droite à angle haut gauche) .
Donc sur un jeu je pense que cette solution serai meilleure
Je vais essayer de voir ta source et de comprendre ce que je peux
A+
bon désolé mais ce n'etait vrai qu'avec la map que j'avais , lol .(j'avais pas vu qu'elle etait aléatoire :? )
Pure curiosité:
Comment se fait il qu'en deux chemins identiques inverses, les résultats soient différents?
Il existe souvent plusieurs "meilleurs chemins" ... Selon le sens dans lequel tu tourne pour inspecter tes cases, il peut en choisir un ou l'autre ...
++ ^^
D'accord, tu lui as en quelque sorte suggéré de rouler à droite de la route plutôt qu'à gauche =)
Bonjours,
Je pense avoir une petite idée qui expliquerait les bons résultats d'une implémentation avec une liste ouverte trié (J'ai pas regardé ta source, mais je suppose que tu utilise une liste trié).
Voilà, donc on suppose qu'une implémentation binary heaps est plus performante car les éléments sont insérés au bonne endroit avec la dichotomique (possible grâce à l'arbre binaire), donc, complexité en O(log2(n)) . Alors que si on veut insérer un élément au bonne endroit dans une simple liste, l'algorithme est en O(n).
Seulement, ce que l'on ne prend pas en compte dans cette histoire c'est que les nouveaux éléments qui seront ajouter à la liste n'ont pas une valeur arbitraire. Au contraire, l'ordre dans lequel ils sont insérer est déjà plus ou moins trié (a cause que l'algorithme A* recherche à ce déplacer dans la bonne direction), ils auront donc tendance à se placer en début de liste.
Enfin, ce n'est qu'une suggestion. D'autant que je ne suis pas expérimenté. J'attends votre avis sur la question, et n'hésitez pas a me reprendre.
Hello !!
Je suis en train de tester ta classe, et j'ai un phénomène assez bizarre...
Soit un fla avec 1 bouton et 4 textInput, j'insère le point de base et le point d'arrivée. Mais la plupart des points d'arrivée qui se trouvent à gauche du point de départ me retourne undefined. Il me semble pourtant que la map passée permette par exemple un déplacement de 4:6 à 1:8, mais non
voilà le code :
import com.lalex.game.PathFinder;
var t:Array = [
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 0, 10, 10],
[ 0, 0, 0, 0, 0, 0, 10, 10, 10, 10],
[ 0, 0, 0, 0, 10, 10, 10, 10, 0, 0],
[ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10],
[ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10],
[ 10, 10, 10, 0, 10, 10, 10, 0, 10, 10],
[ 10, 10, 10, 10, 10, 10, 10, 0, 10, 10]
];
cbt.addEventListener( 'click', mx.utils.Delegate.create( this, onClick ) );
function onClick( evt:Object )
{
_level0.displayArray( PathFinder.findPath( t, Number( tx0.text ),
Number( ty0.text ),
Number( tx1.text ),
Number( ty1.text ) ) );
}
ça me semble un peu bizarre, mais peut-être que je fais une erreur quelque part.. ??
a+
Yop!
Ben, quelques bugs mineurs subsistent encore dans cette classe...
J'envisage de la redévelopper "from scratch" assez vite, notamment en prenant en compte quelques rectifications sur l'algo que m'a communiqué l'auteur original de l'article que j'ai traduis...
++ ^^
En fait, je suis reparti sur A star (wikipedia) et différentes visions que j'ai trouvée. Vu que je n'ai pas besoin d'un algo aussi complexe que tu l'avais fait (parcours en diagonale, arbres binaires, etc...) j'ai fini par redévelopper un pathFinder plus épuré en m'inspirant un peu du tiens (j'aime bien l'idée de la grille qui stocke en mémoire les différents éléments pour les récupérer facilement) et de certaines lectures que j'ai faites. Au final, j'ai un truc assez simple, mais qui me semble bien fonctionnel pour mes besoins.
Vis-à-vis de ton code, j'ai pu remarquer quelques optimisations possibles, entre autre au niveau de la récupération du chemin final (tu prend le dernier élément de la liste, unshift dans un nouveau tableau, et un simple while( element.parent != undefined ) pour itérer et remonter les niveaux + unshift pour ajouter dans le tableau me semble plus simple que ce que tu fais, mais je n'ai pas trop testé au niveau performances.
Peut-être également supprimer la variable "close" et n'utiliser que "open" à true ou false selon si il est dans la liste ouverte ou fermée.
Voilà
et merci pour le partage des sources, ça m'a bien aidé à me remettre dans les algos de graphes (j'ai fait ce genre de trucs pendant mes études... djikstra, bellmann, et tellement de trucs que je supportais à peine, lol)
a+
Fil des commentaires de ce billet