Pacman - Déplacement des fantômes

[invite6f219c61]

Bonjour à tous,
Je tente actuellement de réaliser l'application Pacman en Java.
J'ai choisi de réaliser 3 niveaux. La différence entre ces niveaux sera l'algorithme de déplacement des fantômes (et éventuellement leur vitesse, je verrais selon le résultat des tests).

Pour l'algorithme du niveau 1, j'ai choisi quelque chose de pas très efficace (volontairement) : division du plateau en 4 parties, et les fantômes se dirigent dans la partie où se trouve Pacman (avec un coup sur 2 aléatoire pour provoquer des déplacements différents pour les 4 fantômes).

Toutefois , pour le dernier niveau, je souhaitais trouver un algorithme beaucoup plus puissant du type Dijkstra ou A* mais je n'arrive pas du tout à le mettre en oeuvre dans mon application.
J'ai commencé à répertorier tous les "sommets" de mon plateau (où des changements de direction sont possibles) et je voulais calculer le "coût" de chaque chemin rassemblant 2 sommets mais je ne suis pas sûre que cela puisse se mettre en oeuvre, d'autant plus qu'il faudrait prendre en compte le sommet le plus proche de Pacman et non sa position réelle. Et ensuite je ne vois pas comment renseigner au fantôme comment il pourrait rejoindre les différents sommets...

Est-ce que quelqu'un aurait une idée ?
Merci d'avance de votre aide ! Et Joyeuses Pâques à tous !
-----

[invite45bf7ad1]

Bonjour,

J'avais implémenté quelque chose de similaire il y a assez longtemps. En fait c'est quelque chose d'assez simple sur le papier mais pas toujours élégant à implémenter, pour pouvoir supporter des grandes maps, et vu qu'il s'agit souvent de couloirs, tu peux effectivement le modéliser sous forme de sommets et d'arrêtes et du coup créer un graphe sur lequel appliquer Dijkstra

Tu peux calculer un graphe une bonne fois pour toute au début en utilisant les embranchements de ton labyrinthe. La partie rusée, c'est qu'il faut modifier un peu ce graphe avant d'y appliquer Dijkstra, en "cassant" les arrêtes sur laquelle le fantôme se trouve et celle sur laquelle pacman se trouve pour y ajouter un noeud et deux coûts

Par exemple si un fantôme est "au millieu" d'une arrête de coût 10, ça deviendra alors deux arrêtes de coût 5 de part et d'autre, pareil pour Pacman. La partie pénible étant parfois de déterminer à quel niveau de l'arrête il se trouve. Il faut bien entendu également penser au cas particulier ou tu es sur la même arrête que lui, qui est en fait assez trivial à gérer. Tu te retrouve alors avec un graphe sur lequel tu peux appliquer Dijkstra pour résoudre ton problème de chemin.

C'est un peu fastidieux mais j'avais déjà fait comme ça avec une sorte de plan de ville pour faire des itinéraires d'un point à l'autre

Bon courage!