LAlex devblog v6 - PathFinding et Arbres binaires ... pas mieux ! - Commentaires

PathFinding et Arbres binaires ... pas mieux ! - titouille

titouille — Wed, 25 Jan 2006 20:17:48 +0000

Ok.
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)

PathFinding et Arbres binaires ... pas mieux ! - LAlex

LAlex — Wed, 25 Jan 2006 17:58:37 +0000

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...

++ ^^

PathFinding et Arbres binaires ... pas mieux ! - titouille

titouille — Tue, 24 Jan 2006 18:43:43 +0000

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.. ??

PathFinding et Arbres binaires ... pas mieux ! - Dorian

Dorian — Wed, 06 Apr 2005 01:14:49 +0000

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.

PathFinding et Arbres binaires ... pas mieux ! - enchanteur

enchanteur — Mon, 23 Feb 2004 14:17:32 +0000

D'accord, tu lui as en quelque sorte suggéré de rouler à droite de la route plutôt qu'à gauche =)

PathFinding et Arbres binaires ... pas mieux ! - LAlex

LAlex — Mon, 23 Feb 2004 14:01:08 +0000

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 ...

++ ^^

PathFinding et Arbres binaires ... pas mieux ! - enchanteur

enchanteur — Mon, 23 Feb 2004 13:43:26 +0000

Pure curiosité:
Comment se fait il qu'en deux chemins identiques inverses, les résultats soient différents?

PathFinding et Arbres binaires ... pas mieux ! - kiroukou

kiroukou — Tue, 30 Sep 2003 12:46:29 +0000

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 :? )

PathFinding et Arbres binaires ... pas mieux ! - kiroukou

kiroukou — Tue, 30 Sep 2003 12:44:20 +0000

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+