Discussion :

[major doudou]

Bonjour,
Je suis actuellement en train de programmer un pacman en caml (ce n'est peut-être pas l'idéal mais c'est dans le cadre de mes études donc je n'ai pas le choix pour le langage à utiliser), j'ai fini le code qui affiche la carte, le pacman et les fantômes : j'utilise des matrices de la taille en pixels des images en question qui contiennent les codes rgb de ces pixels (par exemple si le pixel de la 4ème colonne 2ème ligne du pacman est jaune, alors la matrice du pacman aura sa case (2,4) qui contient le code rgb jaune) ; j'utilise ensuite une autre matrice pour la carte, qui elle contient les codes cases des éléments de cette carte (par exemple si la case (3,4) de ma carte est un mur, alors la case (3,4) de la matrice contient un 3, le code que j'utilise pour symboliser les murs). J'ai presque fini de programmer les déplacements au clavier du pacman, mais j'en viens maintenant à un problème que je ne trouve pas si simple à résoudre : le choix des déplacements des fantômes, ceux-ci, lorsqu'ils sont assez proches du pacman, doivent le suivre non pas en tendant vers ses coordonnées, mais en prenant le chemin le plus court du labyrinthe qui menera à lui. J'ai trouvé des sites parlant d'algorithmes de poursuite minmax, alphabeta, ... sans vraiment comprendre à quoi ils pourraient me servir.

Auriez-vous des idées pour créer un code qui trouve dans la matrice de la carte (qu'on peut pour plus de facilité représenter par des 0 et des 1 : 0 pour une case ou le fantôme peut passer, 1 pour les autres) le chemin le plus court qui mène au pacman ? Ce code ne doit pas être trop long car il sera utilisé à chaque boucle du jeu, le choix de direction des fantômes pouvant changer continuellement ...
merci

[Strab]

La question n'est pas liée à Caml, elle va dans le forum Algorithmes. (Il vaut mieux demander à un modérateur de la déplacer plutôt que de poster en double).

Minmax et alphabeta ne sont pas des algorithmes de poursuite, ce sont des algorithmes de recherche dans un graphe, adaptés à la recherche d'une tactique de jeu. Ce que tu cherches, ce sont des algorithmes comme Dijkstra ou mieux dans ton cas, A*.

[Jean-Marc.Bourguet]

Traditionnellement, les algo de poursuites des fantômes dans un pacman sont très simples; et chaque fantôme a le sien. Si j'ai bonne mémoire, un avait simplement des rebonds aléatoires quand il atteignait un mur, un autre choisissait sa direction pour qu'elle le dirige vers le pacman.

[major doudou]

Le problème est qu'on peut faire un réagir un fantôme de plusieurs façons différentes, il peut :
> soit suivre le pacman seulement lorsque ce dernier passe dans son champ de vision, le danger est alors très limité
> soit faire tendre ses coordonnées vers celles du pacman, même si le chemin alors pris n'est pas le plus court pour s'en rapprocher (il va donc s'arrêter s'il est de l'autre côté d'un mur)
> soit sélectionner le plus court chemin qui l'amènera au pacman, même s'il doir faire le tour de la carte
C'est ce troisième point, à mon avis le plus difficile, que je veux coder.
En caml j'avais pensé à une liste de listes, un analyseur de carte rajoute une nouvelle liste pour chaque chemin possible, et compare à la fin les longueurs de chaque liste pour en prendre la plus courte ...

[pseudocode]

soit sélectionner le plus court chemin qui l'amènera au pacman, même s'il doir faire le tour de la carte

Si tu cherches le chemin le plus court, l'ago est A*

Si tu cherches un chemin possible, pas forcement le plus court, tu as Dijkstra (mais c'est tres couteux en cpu) ou alors BFS (chemin moins direct).

D'une maniere generale, cherche "pathfinding algorithms" sur

[Sivrît]

En première approche un A* directement sur ta matrice (comme tout le monde quoi).

Comme le A* porte sur un graphe, l'idéal serait de calculer le graphe (noeuds pour les intersections et arrêtes pour les couloirs) à partir de la matrice. A la base on peut prendre un noeud par case mais limiter les noeuds permettra d'aller bien plus vite et sera plus exploitable. Ce graphe fait un formidable outil pour expérimenter divers comportements suivant qu'on veut faire simple ou pas (pour le joueur) ou s'approcher du jeu originel.

Les fantômes peuvent viser le joueur lui même, son intersection de destination, son intersection de départ (pour lui couper la retraite). Ils peuvent remettre à jour leur direction plus ou moins souvant (ça sera plus facile pour le joueur - et le CPU - s'ils ne changent qu'aux intersections ou même toutes les cases). Un fantomes sadique pourrait aussi viser le baricentre/la plus forte concentration de boules restantes pour attendre le joueur qui aurra déjà tous ses copains derrière lui. Ou y aller au pif histoire d'être bien imprévisible.

Et pour ne laisser aucune chance au joueur qui sera vraiment frustré : une intelligence de groupe ! On prend l'origine et la destination du joueur, mais pas pour deux fantômes donnés. On affecte ces cibles aux fantômes les plus proches d'elles pour optimiser la traque

Les fantômes peuvent aussi être plus ou moins rapides, pouvoir ou non faire demi-tour, prendre les virages plus ou moins vite afin de leur donner une personnalité.

[mchk0123]

Si tu cherches le chemin le plus court, l'ago est A*

Si tu cherches un chemin possible, pas forcement le plus court, tu as Dijkstra (mais c'est tres couteux en cpu) ou alors BFS (chemin moins direct).

De mémoire il me semblait que c'était l'inverse :

A* -> calcul rapide d'un chemin optimum entre A et B
Dijkstra -> calcul de tous les chemins les plus courts depuis A