ALGORITHME DE PATHFINDING A STAR (A*)

Signaler
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
-
notavelido
Messages postés
2
Date d'inscription
vendredi 13 mars 2009
Statut
Membre
Dernière intervention
25 janvier 2010
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/41235-algorithme-de-pathfinding-a-star-a

notavelido
Messages postés
2
Date d'inscription
vendredi 13 mars 2009
Statut
Membre
Dernière intervention
25 janvier 2010

Re-Bonjour,
Et merci pour la réponse rapide ;-)

Bonne fin de journée
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
44
Bonjour,
Une fois le zip téléchargé et extrait, ouvrir la solution et sélectionner le bon projet comme projet de démarrage (AStarTester). C'est tout.
notavelido
Messages postés
2
Date d'inscription
vendredi 13 mars 2009
Statut
Membre
Dernière intervention
25 janvier 2010

Bonjour à tous,
Ce programme semble des plus intéressant et pourrait vraiment m'aider à la réalisation d'un de mes projets, cela dit j'ai un petit problème. Quand j'essaie de lancer la solution, une erreur survient en me disant que: "Le fichier projet ou le site Web a été déplacé ou ne se trouve pas sur mon ordinateur."
Quelqu'un saurait-il comment pallier à ce problème?

En vous remerciant d'avance
sebmafate
Messages postés
4936
Date d'inscription
lundi 17 février 2003
Statut
Modérateur
Dernière intervention
14 février 2014
32
sympa... ca me ramène quelques années en arrière... à l'époque où j'apprenais le LISP :)
c'était sympa la fac :p
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
44
Merci pour la note ;-)
Le but est effectivement de présenter l'algorithme de manière agréable et comme je l'ai précisé il s'agit d'une version de base qui peut (qui doit) être améliorée. En tout cas merci pour les différentes idées, j'en tiendrai certainement compte pour les prochaines versions!
MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Oui effectivement le gain n'est pas trop important comme il est en première position.
Disons que j'ai du utiliser cet algo il y a 3 ans pour un jeu de stratégie temps réel avec 70 unités en même temps sur une carte 500*500 et forcément là il vaut mieux tout faire pour être le plus performant.
Comme par exemple pour l'insertion tu utilises un comparer alors que normalement la liste est déjà entièrement triée : tu peux donc obtenir l'index où insérer en faisant une recherche dichotomique.
De la même manière pour tester si un noeud appartient à la liste open tu fais un Contains alors qu'un tableau à 2 dimensions de booléens seraient beaucoup plus rapide.
Bien entendu pour présenter une source à code source j'aurais fait comme toi et préféré un joli code plutôt qu'un code moche et performant : ces indications sont surtout pour ceux qui veulent l'utiliser dans un jeu temps réél.
Enfin bref 10 : l'algo aussi bien présenté manquait à csharpfr :)
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
44
Merci pour le commentaire.
Ce n'est pas un algo trop coûteux justement, mais concernant le Remove tu as bien sûr raison (ça sera corrigé dans la prochaine version).
Il est clair que c'est plus rapide d'aller supprimer à un élément précis, que de devoir itérer pour retrouver cet élément [ Remove(object o) fait un IndexOf pour avoir l'index puis un RemoveAt, en gros on gagne donc un IndexOf(). En même temps, puisqu'il s'agit toujours d'un RemoveAt(0), IndexOf n'aura qu'une itération à faire, ce qui est relativement négligeable ]
MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Je n'ai pas regardé la source mais juste la preview du code :
Node best = this._open[0]; // This is the best node
this._open.Remove(best);

Comme c'est un algo coûteux :
this._open.RemoveAt(0);
sera un peu plus rapide (à cause du IndexOf dans la fonction Remove (je me doute que tu le sais, je le dis pour les autres :) ))
Ca n'est pas grand chose mais dans un jeu ou dans project hoshimi ça peut être très bénéfique :)