Hello,
Bon tout d'abord une remarque sur le petit tutorial sur l'Algo A*
"
Voilà, vous savez comment fonctionne l'algorithme A*. Il ne donne pas toujours la meilleure solution mais il en donne une bonne. On pourrait comparer ses performances avec celles de l'algorithme de Dijkstra. Dijkstra donne la meilleure solution, mais A* est plus rapide.
"
Ah bon, A* ne donne pas la meilleure solution ? Il me semble que malgré que ce soit une heuristique elle donne toujours la meilleure solution, exactement comme Dijkstra (Contre exemple si vous pensez que j'ai tort...). Je pense que l'intérêt de Dijkstra est ailleurs (buts multiples...)
"
Utilisez une structure de liste triée pour repérer rapidement le meilleur noeud
"
J'aurais aimé en savoir plus sur cette structure de liste triée.
En fait je ne comprends pas vraiment pourquoi on utilise un tas pour chercher le noeud de cout miminum, ça revient à faire une opération en 0(log n) alors qu'on peut vraissemblablement la faire en O(1)... (Faut vraiment que je le code cet algo, mais je ne pense pas me tromper vu que j'ai déjà implémenté Dijkstra...)
J'ai lu cet article :
http://www.gamasutra.com/features/20...pinter_pfv.htm
Je ne comprends pas trop le paragraphe A faster implementation of A*
Quelle utilité de placer le point central [30,30] ?
Quelle structure de données utilise t'il pour coder l'Open List ?
Et je recherche aussi cet article
"Real-Time Pathfinding for Multiple Objects" by Swen Vincke (June 1997).
Plein d'articles qui le citent, mais impossible de le trouver...
Merci pour vos contributions....
Partager