ALGORITHME DE PATHFINDING A STAR (A*)
MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
-
23 janv. 2007 à 22:50
notavelido Messages postés 2 Date d'inscription vendredi 13 mars 2009 Statut Membre Dernière intervention 25 janvier 2010 - 25 janv. 2010 à 10:50
notavelido Messages postés 2 Date d'inscription vendredi 13 mars 2009 Statut Membre Dernière intervention 25 janvier 2010 - 25 janv. 2010 à 10:50
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
https://codes-sources.commentcamarche.net/source/41235-algorithme-de-pathfinding-a-star-a
25 janv. 2010 à 10:50
Et merci pour la réponse rapide ;-)
Bonne fin de journée
25 janv. 2010 à 09:15
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.
25 janv. 2010 à 07:14
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
24 janv. 2007 à 16:06
c'était sympa la fac :p
24 janv. 2007 à 11:12
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!
24 janv. 2007 à 09:53
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 :)
24 janv. 2007 à 07:11
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 ]
23 janv. 2007 à 22:50
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 :)