Discussion :

[Nicodemus]

Bonjour,

Dans le cadre d'un projet, je dois développer un Pacman en Java.
Pour implémenter l'intelligence artificielle des fantomes, lorsqu'ils suivent pacman, j'ai pensé à utiliser les graphes.

A partir du labyrinthe graphique, je déduis un graphe non orienté et pondéré. Le poids etant le nombre de cases séparant chaque carrefour.

Maintenant je dois mettre en place l'algo pour la recherche du plus court chemin (de la position du fantome à celle du pacman, biensur). Je pensais simplement utiliser Dijkstra car il est simple à implémenter, mais je viens de me rendre compte qu'il ne concerne que les graphes orientés...

Quel algorithme dois-je utiliser ? Et qui soit facilement implémentable...

Merci beaucoup.

[Jedai]

Les graphes non-orientés peuvent aussi être vu comme des graphes orientés où chaque arête a sa réciproque, donc tu peux tout à fait utiliser Dijkstra. Tu peux éventuellement utiliser A* à la place (c'est du Dijkstra agrémenté d'heuristique, qui peut-être exact ou "intuitif" selon ton choix).

--
Jedaï

[PRomu@ld]

Si tu ne cherches pas trop la performance , tu peux utiliser BellmanFord, c'est assez simple à coder :

http://brassens.upmf-grenoble.fr/IMSS/mamass/graphecomp/bellmannFord.htm

Pour ce qui est de dijkstra, le problème ne vient pas de graphes non orientés mais plutôt de la valuation des arêtes (elles doivent être toutes positives)

[bafman]

etant donné qu'il value son graph avec des distance, ce sera forcement positif (ou alors il fait des calcules etranges )
sinon moi aussi je conseil A* qui :
- est plus rapide de dijkstra grace au heuristiques
- permet d'avoir des chemin plus "naturels" encore grace a certaines heuristiques
- n'est pas plus compliqué a coder que dijkstra (c'est le même avec juste un cout suplementaire par case qui prend en compte l'heuristique)

et le dernier point : on le trouve partout sur internet

[Sivrît]

Remarque en passant : tu as pensé aux subtiles et sadiques différences de comportement entre les fantômes ? Je ne connais pas leurs personnalités (même les fantômes ont des sentiments) par coeur mais l'un est un traqueur implacable qui suit le plus court chemin, un autre doit plutôt viser l'intersection de destination du joueur.... Plus un qui se promène un peu au hazard et c'est un cauchemard assuré

[Nicodemus]

Je vous remercie tous pour vos réponses et suggestions.
Par manque de temps je viens de mettre en place simplement l'algo de Dijkstra et ça fonctionne nickel. Mais j'avoue que je suis tenté d'utiliser des heuristiques différentes par fantômes et de rendre le jeu bien plus captivant.

Mais bon... ce projet ne compte pas beaucoup et j'ai d'autres priorités. Je le reprendrais plus tard peut être.

Merci en tout cas