Algorithme de déplacement - Pacman

[adeline08]

Bonjour,

Je réalise actuellement le projet Pacman et il ne me manque qu'une chose : un algorithme de recherche de Pacman performant ! J'ai déjà l'idée mais je n'arrive pas à la mettre en oeuvre.

Mon idée : créer une liste.
On part de la case du fantôme. On l'ajoute à la liste. On analyse les 4 cases autour. Si ce ne sont pas des murs, on les ajoute à la liste (en effectuant un double marquage pour ensuite retracer le chemin à parcourir par le fantôme). Il faudrait ensuite réaccéder aux 4 (ou moins ...) cases ajoutées et analyser les 4 cases autour etc...

Mais je n'arrive pas à le mettre en oeuvre....
Je me ramène toujours à des boucles infinies ou à des codes interminables .....

Voici une partie de mon code pour exemple :

if (AncienneCase[0]+1<31) { // on regarde la case en X+1, Y
maCase[0]=AncienneCase[0]+1;
maCase[1]=AncienneCase[1];

if (comparaisonCaseMur(maCase[0],maCase[1])==false) {
CaseTest[0]=maCase[0];
CaseTest[1]=maCase[1];
CaseTest[2]=AncienneCase[0]; // enregistrement de l'ancienne Position
CaseTest[3]=AncienneCase[1]; // idem
maListe.add(maListe.size(), CaseTest);


}
}

Idem en X-1, Y+1, Y-1. Puis comment modifier AncienneCase sachant qu'on a entre 1 et 4 nouvelles cases ajoutées....

Merci d'avance de votre aide,

Bonne soirée
-----

[Paraboloide_Hyperbolique]

Bonsoir,

Je pense que l'algorithme que vous proposez, bien que théoriquement valable est loin d'être performant. Pour chaque étape vous avez:

Etape 1: visiter 4 cases.
Etape 2: visiter 3 = (4-1) cases pour chacune des 4 cases = 4.3 cases (on ne visite pas la case de départ, déjà visitée).
Etape 3: visiter 3 cases pour les 4.3 cases de départ = 4.3² cases.
...
Etape n: visiter 4.3^n cases.

Pour n = 31, cela fait de l'ordre de 2,47 x 10^15 cases (pour un seul fantôme...) C'est ingérable sur la plupart des ordinateurs.

En terme de consommation mémoire, votre algorithme est exponentiel. Il y a moyen de réduire la consommation mémoire en marquant les cases explorées (car la plupart des cases sont explorées plusieurs fois avec votre algorithme), mais cela restera peu efficace.

A votre place, j'irais voir dans la littérature (tapez dans Google "algorithme pacman"); il y a beaucoup d'algorithmes bien plus efficaces qui sont proposés.

[kwariz]

Bonsoir,
En fait l'algorithme que tu tentes de mettre en oeuvre est une sorte de parcours en largeur d'abord du plateau.

Plutôt que de partir du fantôme, tu vas partir de la case du pacman. On va indiquer dans chaque case la distance de celle-ci au pacman. Celle où se situe pacman sera marquée 0. Les distances se calculent avec un parcours en largeur.
Il faut relancer le calcul à chaque changement de case du pacman.
Une fois que ton labyrinthe est marqué, tu déplaces chaque fantôme vers une case plus proche du pacman ; comme en général les labyrinthes sont petits tu ne devrais pas rencontrer de problèmes de performances (j'ai dans les années 90 implémenté cet algo et ça marchait pas trop mal, tss ... en 20 ans on tombe toujours sur les mêmes projets )

[Chanur]

Bonjour,

Pour n = 31, cela fait de l'ordre de 2,47 x 10^15 cases (pour un seul fantôme...) C'est ingérable sur la plupart des ordinateurs.

En terme de consommation mémoire, votre algorithme est exponentiel. Il y a moyen de réduire la consommation mémoire en marquant les cases explorées (car la plupart des cases sont explorées plusieurs fois avec votre algorithme), mais cela restera peu efficace.

Non.
Je suis désolé, mais l'algorithme est linéaire en fonction du nombre de cases.

Pour la case courante ,
incrémenter le nombre d'itérations
marquer la case avec le nombre courant d'itérations
regarder les 4 cases haut, bas, gauche et droite
Si c'est un mur, ou une case déjà marquée, ne rien faire
Si c'est une case vierge, lacer la même chose sur cette case.

Quand ou arrive à la case voulue, on arrête, et il suffit de choisir comme parcours celui qui donne le plus petit nombre d'itérations

On peut implémenter ça soit par une fonction récursive, soit en balayant une liste de cases à la fin de laquelle on ajoute chaque nouvelle case explorée
Ce schéma est reproduit autant qu'il y a de cases, et certainement pas de façon exponentielle. Il consomme très peu de mémoire.
Je l'ai déjà implémenté, et à moins de mettre une pause à chaque itération, je ne vois pas comment ça pourrait prendre ne fût-ce qu'une milliseconde ...

La dernière fois que je l'ai fait, j'avais un écran de 1200*1600 pixel, on pouvait aller sur chaque pixel (sauf les murs), et le temps de calcul pour trouver le plus court chemin d'un point à un autre était négligeable (je n'ai pas mesuré, mais c'était inférieur au dixième de seconde).

a+

[A voir en vidéo sur Futura]

[adeline08]

Bonjour,
Merci pour vos réponses =)

Chanure, je ne vois pas comment marquer la case afin de ne pas la réécrire deux fois ...
Et sans employer la récursivité (je ne sais pas la formulation en java), comment appliquer cette méthode aux cases testées ?
Est-il possible de compter le nombre de cases ajoutées, de retourner à la première case que l'on vient d'ajouter et ensuite de .... recommencer l'algo? sans récursivité, je ne vois vraiment pas comment faire..

[Chanur]

Chanure, je ne vois pas comment marquer la case afin de ne pas la réécrire deux fois ...

(Chanur, sans e )
C'est à toi de le gérer : il te suffit d'avoir un tableau [hauteur][largeur], qui peut être un tableau d'entier, de structures, ou ce dont tu as besoin, et tu peux y marquer les cases comme tu veux.

Et sans employer la récursivité (je ne sais pas la formulation en java), comment appliquer cette méthode aux cases testées ?
Est-il possible de compter le nombre de cases ajoutées, de retourner à la première case que l'on vient d'ajouter et ensuite de .... recommencer l'algo? sans récursivité, je ne vois vraiment pas comment faire..

crée le tableau des cases :
Une classe Cellule (je n'aime pas utiliser le mot case pour éviter la confusion avec le switch ... case).
un tableau Cellule terrain [hauteur][largeur]

puis une liste des cellules que tu visites :
Cellule * cellule_visitee [largeur*hauteur]. C'est un tableau de pointeurs,
dont les éléments seront des pointeurs vers les cases du tableau terrain

remplir de 0 le tableau cellule_visitee (en le déclarant static, ou avec un memset)
initialiser cellule_visitee[0] = &terrain[i][j], en supposant que i et j soient les coordonnées d'arrivée
n = 0
fin = 1 (indice de la fin du tableau cellule_visitee)
cellule_visitee[0]->indice = indice = 1;
tant que cellule_visitee[n] != NULL
    indice ++;
    regarder les cellules voisines
    a chaque fois qu'une cellule doit être visitée (ce n'est pas un mur et son indice est nul)
        noter dans cette nouvelle cellule l'indice courant,
        ajouter la nouvelle cellule dans la liste cellule_visitee à l'indice fin,
        et incrémenter fin
fin tant que
parcourir le tableau "terrain" depuis le point de départ, en choisissant à chaque fois d'aller sur une cellule dont "indice"
est inférieur à celui de la cellule courante : on arrive au point d'arrivée par le plus court chemin possible (ou un des plus courts s'il y en a plusieurs)

Note : pour connaître les cases voisines, il est pratique d'avoir dans la classe cellule les coordonnées de la cellule
Evidemment, il faut initialiser correctement le tableau terrain, en affectant les coordonnées, en marquant les murs et en mettant "indice" à 0

Note2 : il est inutile de poursuivre le balayage de cellule_visitee dès que tu as atteint le point de départ, sauf si tu veux t'en servir pour plusieurs fantômes à la fois : après tout cet algorithme donne d'un coup le plus court chemin depuis n'importe quelle cellule ...

[galoed]

Bonsoir !

pour avoir déja participé à la création d'un jeu de pacman,

nous avions utilisé cet algorithme :

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

vous pouvez toujours l'analyser et voir si ça pourrait être bien.

peut être que ça vous donneras quelques idées

Galoed !

[Paraboloide_Hyperbolique]

Bonjour,
Non.
Je suis désolé, mais l'algorithme est linéaire en fonction du nombre de cases.

Pour la case courante ,
incrémenter le nombre d'itérations
marquer la case avec le nombre courant d'itérations
regarder les 4 cases haut, bas, gauche et droite
Si c'est un mur, ou une case déjà marquée, ne rien faire
Si c'est une case vierge, lacer la même chose sur cette case.

Quand ou arrive à la case voulue, on arrête, et il suffit de choisir comme parcours celui qui donne le plus petit nombre d'itérations

On peut implémenter ça soit par une fonction récursive, soit en balayant une liste de cases à la fin de laquelle on ajoute chaque nouvelle case explorée
Ce schéma est reproduit autant qu'il y a de cases, et certainement pas de façon exponentielle. Il consomme très peu de mémoire.
Je l'ai déjà implémenté, et à moins de mettre une pause à chaque itération, je ne vois pas comment ça pourrait prendre ne fût-ce qu'une milliseconde ...

La dernière fois que je l'ai fait, j'avais un écran de 1200*1600 pixel, on pouvait aller sur chaque pixel (sauf les murs), et le temps de calcul pour trouver le plus court chemin d'un point à un autre était négligeable (je n'ai pas mesuré, mais c'était inférieur au dixième de seconde).

a+

Bonjour,

Oui, tel que vous le décrivez (en maintenant une liste des cases visitées) c'est linéaire; mais ce n'est pas comme ça que je comprend l'algorithme d'adeline08 (où il semble que pour chaque case l'on explore systématiquement les 4 cases autour).

[azad]

Salut
Dans le vrai Pacman d'origine, celui de Namco, les fantômes ont un circuit pré-établi (du moins dans les 3 ou 4 premiers tableaux) ils peuvent parfaitement passer à coté de Pacman sans le dévorer. Et les fans du jeu connaissent même certaines cases où les fantômes ne passent jamais. Ce n'est que dans les tableaux d'ordre plus élevés qu'ils acquièrent un peu plus d'intelligence et leur circuit change en fonction de la position de Pacman - mais pas à tous les coups - la position de Pacman n'est pas prise en compte à tout les coups, ils adoptent alors un autre circuit qui les dirigent vers une position voisine de leur cible. C'est pourquoi, pendant une fraction de seconde, on voit le jeu (je parle de l'original, sur Z80 toujours) se figer alors que l'on se branche vers de nouvelles routines. Z80 oblige. A mon avis faire un tel jeu avec un algorithme de recherche en continu et avec la puissance de calcul dont on dispose aujourd'hui, rendrait le jeu injouable. Aucun joueur n'y résisterait, pas même s'il en est le programmeur. (sauf s'il "triche" par exemple en maintenant deux ou trois touches pressées pendant l'action)
Je devrais avoir quelque part dans mon grenier, les listings en assembleur Z80. Si ça vous tente. Une quinzaine de page A3 illisibles pour moi, qui suis 6502.

[azad]

Incroyable, je viens de faire une recherche, et .... il est là : http://cubeman.org/arcade-source/pacman.asm