Trouver son chemin dans un labyrinthe

Salut,

J'aimerais faire une sorte de Pac-man 3D

Cependant, a la différence de l'ancien jeu, le mien aurait des terrains qui ne serais pas toujours pareil.
Jaimerais savoir si il existe un algoritme pour aider mes fantomes à aller rejoindre mon "pac-man" sans, bien sur, traverser les murs (c'est un fantome stupide).

PS, jaimerais autre chose que d'y aller par essai-erreur.

Merci

Il y a un truc de ce genre qui est utilisé par tous les jeux de Sokoban. Ca marche très bien.

Tu associe le nombre -1 à chaque case du labyrinthe, et 0 à la case du pacman. Puis tu parcours la boucle suivantes (premier passage avec i = 0) jusqu'à ce qu'il n'y ait plus de -1 dans le tableau:

toute case contenant -1 et voisine d'une case contenant i reçoit i+1.

Une fois que c'est fait, le fantome trouve immediatement le plus court chemin vers le pacman. Evidemment, le calcul doit être refait à chaque mouvement du pacman ou à chaque changement de configuration du labyrinthe.

On peut aussi essayer de faire de cette maniere...

matrix est le plateau de jeu, on met des -1 sur les murs, et des infinity sur les cases. La case qui contien le fantome est à zero...

Code:

---

1 2 3 4 5 6

fonction chemin : ( point_orig, point_arriv ) { matrice[point_arriv.x][point_arriv.y] = min( matrice[point_arriv.x][point_arriv.y], matrice[point_orig.x][point_orig.y] + poid[point_arriv.x][point_arriv.y] ); }

---

Ensuite, il suffit de faire une petite fonction recursive qui va lancer la fonction chemin dans chaque direction, pour chaque point.

A la fin, il suffit de repartir du point final, pour chercher la case adjacente la plus petite, et continuer... comme ca on retrouve le plus court chemin...

Si je me souvient bien, c'est l'algorithme de Dijkstra (orthographe approximative )

Citation:

---

Envoyé par bibi.skuk

Si je me souviens bien, c'est l'algorithme de Dijkstra (orthographe approximative )

---

C'est ça!

Algorithme général: http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Il y a l'algorithme A* qui est peut-être plus pertinent, Dijkstra est très gourmand.

Citation:

---

Envoyé par Miles

Il y a l'algorithme A* qui est peut-être plus pertinent, Dijkstra est très gourmand.

---

C'est également se que je me suis dit.

J'aivais deja entendu parler de l'algo A* (si j'ai bien comprit le principe étant de definir les points de la map comme point de "traverse" point de "deplacement" et de point de "collision").

Comme je ne connait pas les points il faudrais tout de meme faire un ballayage du labyrinthe avant chaque depart.

A mon avis une petite recherche sur google avec comme mon clef graphe, plus court chemin, dijkstra, bellman-ford ... te donneras de bon resultat.

Double post :S

dsl

Citation:

---

Envoyé par benratti

A mon avis une petite recherche sur google avec comme mon clef graphe, plus court chemin, dijkstra, bellman-ford ... te donneras de bon resultat.

---

je crois que se forum a bien repondu a ma question, merci beaucoup tout le monde