pathfinding click and play

**youp_db** · 31/07/2006, 12h36

bonjour,

voici le problème :

comment faire pour faire bouger un personnage le long d'un chemin tordu SANS PASSER EN DEHORS en sachant qu'il doit aller ou le joueur a clické.

c'est pour un jeu vidéo en 2D de type click and play (exemple : monkey island)
exemple :

chemin :

x (arrivée)

--------------------------
********************|
********************|
********************| x (point de départ)

merci

**Matthieu Brucher** · 31/07/2006, 13h26

As-tu cherché dans le forum l'algorithme A* ?

**youp_db** · 31/07/2006, 13h38

Envoyé par Miles

As-tu cherché dans le forum l'algorithme A* ?

oui, pas trouvé ... , mais es-tu certain qu'il n'y a pas plus simple vu le type de jeu ??

**Matthieu Brucher** · 31/07/2006, 13h43

Le problème du plus court chemin est un problème de parcours de graphe, et le A* est l'un des plus performant à ce niveau, par rapport à ce qui se fait d'habitude. Maintenant, tu peux aussi l'optimiser en utilisant des points caractéristiques de la grille de ton jeu plutôt que la grille complète.

**youp_db** · 31/07/2006, 14h36

Envoyé par Miles

...Maintenant, tu peux aussi l'optimiser en utilisant des points caractéristiques de la grille de ton jeu plutôt que la grille complète.

mais comment faire cela stp ?

**Matthieu Brucher** · 31/07/2006, 14h46

Sur ta grille, tu indiques des points particuliers et tu fais un pathfinding entre ces points.

**youp_db** · 31/07/2006, 22h57

savez-vous ou je peux trouver la traduction de cet algorithme en C svp ?

merci

**PRomu@ld** · 01/08/2006, 17h30

Nous ne sommes pas ici pour te "pondre" le code tel quel.

Ici nous pouvons t'aider sur la compréhension de l'algorithme.

Ensuite si c'est un problème d'implémentation, tu pourras aller voir dans le forum C.

Mais en aucun cas nous ne produisons pas de "code à la demande". Seulement des aides.

Si tu n'as aucune idée de l'algorithme, cette page pourra t'aider : http://www.policyalmanac.org/games/aStarTutorial.htm

**youp_db** · 04/08/2006, 14h08

Envoyé par PRomu@ld

...
Ici nous pouvons t'aider sur la compréhension de l'algorithme.

sur le site http://www.policyalmanac.org/games/aStarTutorial.htm, dans la figure 5, à côté de la position actuelle, on peut constater que le cout le plus faible se trouve dans la case a gauche la plus éloigné du point d'arrivé.

comment cela se fait il ? comment faire pour l'éviter ?

merci

**Matthieu Brucher** · 04/08/2006, 14h11

J'ai pas tout lu, mais normalement, on utilise une heuristique qui estime un chemin peu coûteux, mais ce n'est pas le meilleur. Il peut arriver que l'heuristique se plante et indique d'aller à un endroit qui n'est pas optimal pour nous, mais pour lui si. Mais ne tout manière, il trouve bien un chemin correct dans l'exemple.

**youp_db** · 04/08/2006, 22h28

d'après la figure 6, les cases formant le chemin ont été sauvegardées dans une liste fermée.

mais comment font-ils après pour savoir quelles cases garder, à savoir les cases jaunes de la figure 7

merci

**Matthieu Brucher** · 04/08/2006, 23h49

Au fur et à mesure de la construction du chemin, on stocke les cases à parcourir, la liste est donc construite en temps réel.

**youp_db** · 05/08/2006, 00h20

Envoyé par Miles

Au fur et à mesure de la construction du chemin, on stocke les cases à parcourir, la liste est donc construite en temps réel.

oui, mais il y a des cases stockées inutilement comme dans la figure 6 où on peut voir que certaines cases en bleu se situent autour de la case de départ mais ne sont pas utilisées pour le chemin final.

**Matthieu Brucher** · 05/08/2006, 00h28

En fait, dans chaque cas, on note le parent optimal trouvé jusqu'à présent, et donc en remontant ces cases, on trouve le chemin jaune.

pathfinding click and play

Algorithmes et structures de données

Discussions similaires

Partager

Partager