Discussion :

[Zwart]

Bonjour, je suis en train de développer un petit Tactic RPG pour un projet et j'ai un problème avec la recherche des chemins lors des déplacements des joueurs.

Lorsque je clique sur une unité, sa zone de déplacement apparait à l'écran mais je n'ai pas trouvé d'algorithme pour que ma zone corresponde vraiment.
En effet si j'ai une case devant moi sur laquelle je ne peux pas passer, je ne l'affiche pas mais je peux encore passer derrière alors que normalement mon nombre de déplacement est limité et qu'il faut un déplacement de plus pour passer à coter de l'obstacle.

En gros je cherche un moyen de pouvoir parcourir tous les chemins possibles d'une distance précise correspondant au déplacement de l'unité.

Si quelqu'un peut m'aider ou me donner une piste.
Merci bien.

[nouknouk]

salut,

as-tu cherché du côté de l'algorithme A* ?

[Mat.M]

Regarder dans les tutos de DVP.
Khayyam90 a fait un très bon tuto et un excellent exemple.

http://khayyam.developpez.com/articles/algo/astar/

sinon tu as éventuellement des libs comme Opensteer un peu plus complexe et Micropather
http://www.grinninglizard.com/MicroPather/

[oxyde356]

Comme nouknouk je te conseil l'algorithme A* (A Star), algorithme de recherche du plus court chemin, c'est surement le plus utilisé dans les jeux vidéos (avec quelques optimisations) et il n'est pas très dur à mettre en oeuvre.

[Christuff]

En gros je cherche un moyen de pouvoir parcourir tous les chemins possibles d'une distance précise correspondant au déplacement de l'unité.

Si je me souviens bien ( corrigez moi si je me trompe, mes souvenirs sont un peu lointains ) A star va s'arrêter des qu'il aura trouver un chemin ( qui en général sera le plus court, mais pas forcement - ex le cas d'un labyrinthe )

S'il est primordial que tu ai parcouru tout les chemins, dans ce cas je penserait plutôt a l'algo de dijkstra

[oxyde356]

Tout dépend ce qu'il recherche, mais vu qu'il fait un jeu et que l'algorithme de dijkstra peut être très très long, j'espère que son jeu n'est pas en temps réel
Si ce qui compte c'est de trouver un chemin optimal sans faire ramer => A*

[deadalnix]

S'il est primordial que tu ai parcouru tout les chemins, dans ce cas je penserait plutôt a l'algo de dijkstra

A* c'est Dijkstra avec de l'euristique. C'est la façon dont tu calcule ton euristique qui va faire les différences précitées.

Mais si ton euristique reste toujours inférieure au cout réel de déplacement, alors tu économise du calcul par rapport à Dijkstra sans en fausser les résultats.

[nouknouk]

A* c'est Dijkstra avec de l'euristique. C'est la façon dont tu calcule ton euristique qui va faire les différences précitées.

Certes, mais que A* et Dijksta soient rapprochés dans leur fonctionnement n'empêche pas que la finalité n'est pas la même. A* n'est pas qu'une version 'optimisée' de Dijksta mais offre bel et bien 'service' différent puisqu'elle permet de gagner du temps mais ne garantit pas de retourner le chemin optimum à tous les coups.

exemples, si:

- on a genre un jeu de guerre en tour par tour et le but est d'afficher, lorsqu'on clique dessus, toutes les cases atteignables par une unité en fonction de ses 'points d'action' restant, on cherchera une approche systématique car le temps réel n'est plus un problème, par contre on veut être certain que le calcul des points d'actions imputés soit exact, donc le chemin optimal.

- par contre si on a un jeu genre RTS où on clique sur un unique point de destination, à charge pour l'unité sélectionné de s'y rendre du mieux qu'elle peut, le tout en temps réel, l'approche A* est préférable notamment à cause de contraintes temps réel.

Bref, tout dépend des besoins de Swart. A priori, et en relisant avec attention son post, je penche finalement pour l'interprétation de Christuff:

S'il est primordial que tu ai parcouru tous les chemins, dans ce cas je penserait plutôt a l'algo de Dijkstra

[deadalnix]

Certes, mais que A* et Dijksta soient rapprochés dans leur fonctionnement n'empêche pas que la finalité n'est pas la même. A* n'est pas qu'une version 'optimisée' de Dijksta mais offre bel et bien 'service' différent puisqu'elle permet de gagner du temps mais ne garantit pas de retourner le chemin optimum à tous les coups.

Non, d'ailleurs tu le montre bien dans tes exemples en dessous. A* est fait pour te donner un chemin vers une destination. Dijkstra n'est utile que si tu ne sais pas ou tu vas (comme ton exemple avec les points d'action).

A* te donnera ou non une solution optimale en fonction de ton euristique. pour avoir une solution il faut que dans tous les cas H < R ou H est ton euristique et R le coût réel optimal.

[ubenz]

je suis tombé sur une implémentation du A* qui ma pas mal plus

voila le liens,

http://www.grinninglizard.com/MicroPather/

j ai trouvé ca plutôt bien pensé , (très facile a intégrer) , tu as juste une fonction a surchargé qui te fourni un objet en paramètre et te demande ses voisin et leur poids (dans le cas d un chemin la distance,,le temps )