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é.

[PRomu@ld]

Si vous cherchez plus d'informations sur l'algorithme a start, vous pouvez consulter ceci :

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

[major doudou]

merci pour toutes ces réponses ...

je programme en caml, et je me demande comment modéliser le graphe des intersections et des branches : j'ai pensé à une liste de sous-listes à 5 éléments, chacune comportant le numéro de l'intersection, ses deux coordonnées, puis dans l'ordre le numéro et la distance des intersections à gauche, droite, en haut et en bas.

[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

[pseudocode]

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

heu oui... tu as totalement raison. J'ai besoin de vacances

[mchk0123]

heu oui... tu as totalement raison. J'ai besoin de vacances

Rassures toi je n'ai aucun mérite (j'y suis déjà (en vacances (progn (if (< (- (now) (car dates_debut_vacances) "1_mois") (message "j'ai les neurones qui chauffes)))))))))))

[fumidu]

Je ne comprends pas pourquoi tout le monde a d'office écarté min-max pour la poursuite... Je trouve ça parfaitement adapté ! On a évidemment besoin de Dijikstra ou d'A* pour la fonction d'évaluation, mais min-max et toutes ses améliorations permettent d'élaborer une 'stratégie' de poursuite, à plus forte raison si les fantômes coopèrent ! Dans le cas, le meilleure moyen de chopper ce salaud de pacman n'est pas forcement de foncer droit sur lui, mais ptet de l'encercler ou de le coincer dans une impasse.

Pour ceux qui ne connaissent pas min-max, ça servirait dans ce cas à explorer la poursuite plusieurs tours à l'avance, en supposant que les fantômes essayent de minimiser la distance à pacman, et pacman essaye de l'augmenter. Sur deux directions apparemment équivalentes, il y en a peut être une qui est meilleure à long terme.

Bon, cela dit, j'ai bien conscience que ça complique énormément le problème, et que ça laisse peu de chance au joueur... Mais je trouve le concept intéressant

[Jean-Marc.Bourguet]

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

Tiens, j'avais retenu quelque chose d'autre, mais je n'ai fait que lire une presentation sommaire d'A*.

A* trouve rapidement un bon chemin pour autant que la fonction d'estimation soit bonne.

Dijsktra, c'est A* avec une fonction d'estimation qui assure de trouver l'optimum au detriment de la quantite de calcul faite.

[pseudocode]

merci pour toutes ces réponses ...

je programme en caml, et je me demande comment modéliser le graphe des intersections et des branches : j'ai pensé à une liste de sous-listes à 5 éléments, chacune comportant le numéro de l'intersection, ses deux coordonnées, puis dans l'ordre le numéro et la distance des intersections à gauche, droite, en haut et en bas.

Le plus simple c'est de représenter le labyrinthe sous forme de graphe.

- Les sommets sont les couloirs (valeur = longueur du couloir)
- Les arcs sont les intersections (valeur = somme des 2 sommets)

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
  _________
 |  _D___ *|
 |C|     | |
 | |_____|E|
 |  __B____|
 | |
 |A|
 | |
  +

Sommets:
A(4), B(8), C(4), D(8), E(4)

Arcs:
AB (8+4=12)
AC (4+4=8)
CD (4+8=12)
DE (8+4=12)
BE (8+4=12)

Chemins possibles de (+) vers (*)

Note: (*) est sur une intersection, donc dans plusieurs couloirs a la fois.

Cas 1: on considere que (*) est dans D ==> depart=A arrivée=D
Chemin 1: AB+BE+ED = 12+12+12 = 36
Chemin 2: AC+CD = 8+12 = 20

Cas 2: on considere que (*) est dans E ==> depart=A arrivée=E
Chemin 3: AB+BE = 12+12 = 24
Chemin 4: AC+CD+DE = 8+12+12 = 32

Chaque fantome prend (si possible) un itineraire different, du plus court au plus long.

[jobherzt]

Tiens, j'avais retenu quelque chose d'autre, mais je n'ai fait que lire une presentation sommaire d'A*.

A* trouve rapidement un bon chemin pour autant que la fonction d'estimation soit bonne.

Dijsktra, c'est A* avec une fonction d'estimation qui assure de trouver l'optimum au detriment de la quantite de calcul faite.

je dirais plutot :
-djikstra c'est un algo exhaustif qui trouve le chemin le plus court, en temps polynomiale en temps polynomial mais un peu long
- A* c'est une heuristique qui trouve un chemin pas trop long en un temps raisonnable, moyennant des hypothese raisonnable sur le graphe.

[edit] enfin ca revient au meme que ce que tu dis, en fait.. mais je pense que c'est A* qui decoule de dijkstra et pas l'inverse.

[pseudocode]

enfin ca revient au meme que ce que tu dis, en fait.. mais je pense que c'est A* qui decoule de dijkstra et pas l'inverse.

Oui, tout a fait.

A* est un classique "dijkstra" dans lequel on choisi d'abord les arcs qui permettent de se rapprocher du but (via une heuristique pour le calcul de la distance).

On s'arrete generalement a la premiere solution trouvée par cette méthode. Alors qu'avec le "dijkstra" classique, on enumere toutes les solutions

[Jean-Marc.Bourguet]

mais je pense que c'est A* qui decoule de dijkstra et pas l'inverse.

Historiquement, oui.

[Sivrît]

Par contre juste un point:
L'heuristique permet d'orienter la recherche pour tomber au plus vite sur le bon chemin. Mais moyennant une petite hypothèse sur celle-ci le résultat de A* est exact, ce qui le rend très intéressant car il est généralement bien plus rapide tout en donnant toujours un des plus courts chemins (ce qui nous suffit la plupart du temps).

[mchk0123]

Quand on parle d'heuristique c'est que la solution trouvée est bonne mais pas forcément la meilleure.

Et de plus la justesse de la solution trouvée dépend du choix de la distance utilisée.

[BugFactory]

Bonjour,

J'ai lu un article détaillant A*. En fait, la qualité de l'heuristique estimant la distance restante, tant qu'elle répond aux conditions nécessaires (pas de surestimation si ma mémoire est bonne, donc la distance à vol d'oiseau fonctionne), ne change que la vitesse de calcul. La solution donnée par A* est toujours optimale. On aura donc une seule solution parmis toutes celles qui existent, mais on est assuré qu'il n'en existe pas de meilleure, au mieux des égalités.