Trouver le chemin dans un jeu Java 2D?

Question

C'est essentiellement un jeu de clone de pacman sur lequel je travaille. J'ai une classe Enemy et 4 instances de cette classe ont été créées. Elles représentent toutes 4 fantômes du jeu.

Tous les fantômes démarrent dans des zones aléatoires de l'écran, puis doivent se frayer un chemin vers le personnage de pacman. Lorsque le joueur contrôle le joueur, il doit le suivre et prendre le chemin le plus proche possible vers lui.

Il n'y a pas encore de labyrinthe / d'obstacles, donc la carte entière (400x400 pixels) leur est ouverte.

Pour le joueur et chaque fantôme, je peux récupérer les attributs X, Y, largeur et hauteur de l’image. De plus, j’ai déjà un algorithme de détection des collisions, donc ne vous inquiétez pas pour ça, juste au sujet des fantômes qui se rendent chez pacman.

Answer 1

Pour un bon algorithme de recherche de chemin, utiliser A * serait probablement une bonne idée, Cependant, pour un jeu simple qui ne nécessite pas de recherche de chemin sophistiquée, efficace ni efficace, il suffit que les personnages se dirigent vers une cible en recherchant la direction à suivre.

Par exemple, la décision de déplacer le caractère, en pseudocode:

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Oui, le personnage ne fera pas le mouvement le plus efficace, mais il se rapprochera de plus en plus de la cible à chaque itération de la boucle de jeu.

Je pense aussi qu'un jeu d'arcade du début des années 80 n'utiliserait probablement pas des algorithmes sophistiqués de recherche de chemins.

Answer 2

Si vous ne disposez que d’une grille de pixels, un "grand champ" pacman et fantôme peuvent se déplacer librement - le chemin le plus court est facile - une ligne droite entre le fantôme et le pacman.

Mais "le plus court chemin" signifie invariablement que nous essayons de résoudre un problème de théorie des graphes. (J'assume la connaissance des graphes, de la théorie des graphes, des matrices adj., Etc.!)

Dans le cas ci-dessus, considérez chaque pixel comme un nœud d’un graphe. Chaque nœud est connecté à ses voisins par un bord, et chaque bord a le même "poids". (Le passage au noeud situé au-dessus de "n'est pas plus lent que le passage au noeud" au-dessous de ").

Donc, vous avez ceci: ("" *" = noeud, "-, /, \, |" = bord)

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-* 

Si Pacman est au centre, il peut être déplacé très facilement vers n’importe quel autre noeud.

Quelque chose de plus proche de la réalité pourrait être ceci:

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-* 

Maintenant, pacman ne peut pas se déplacer en diagonale. Pour aller du centre vers le bas à droite, vous devez disposer de 2 "sauts". plutôt qu'un.

Pour continuer la progression:

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

Maintenant, pour passer d'un nœud du milieu à un nœud du haut, vous avez besoin de 3 sauts. Cependant, aller vers le bas ne prend que 1 saut.

Il serait facile de traduire toute configuration de plateau de jeu en graphique. Chaque "intersection" est un noeud. Le chemin entre deux intersections est une arête et sa longueur est le poids de cette arête.

Entrez A *. En construisant un graphe (utilisez une matrice d'addition ou une liste de nœuds), vous pouvez utiliser l'algorithme A * pour trouver le chemin le plus court. D'autres algorithmes incluent Dijkstra. Et plein d'autres! Mais vous devez d’abord définir votre problème en termes de graphique, puis de jouer du nœud A (pacman) au nœud B (fantôme).

J'espère que ça aide!

Answer 3

Cela fait très longtemps, mais de mémoire, les fantômes de Pac-Man n’ont pas fait grand-chose en matière de recherche de parcours. Ils effectueraient une traversée aléatoire de labyrinthe assez standard jusqu'à ce qu'ils "tachent". vous, ce qui impliquait de trouver un chemin dégagé le long de l’axe d’un couloir qui se dirigeait vers vous, puis ils se dirigeaient directement vers vous jusqu’à ce que vous disparaissiez de leur ligne de mire, après quoi ils reprenaient un schéma aléatoire. À des niveaux plus élevés, Pac-Man laisserait des traces invisibles derrière lui pendant un moment, ce que les fantômes "sentiraient". et parfois suivent.

Lorsque Pac-Man a eu le pouvoir, la seule différence dans l'algorithme est que, lorsqu'ils vous ont repéré, les fantômes vous fuient au lieu de se diriger vers vous.

Ainsi, pour une expérience authentique, vous n’avez probablement pas besoin d’un algorithme de recherche de cheminement très sophistiqué. Bien sûr, si vous voulez être chic, vous pouvez implémenter A *.

Answer 4

Marcher directement vers vos ennemis est un début, mais lorsque vous ajoutez un labyrinthe, vous voudrez ajouter un chemin un peu plus intelligent pour que vos fantômes ne restent pas coincés dans des virages ou des impasses.

Le tutoriel suivant est un excellent guide léger pour se familiariser avec A *, avec des exemples téléchargeables.

Recherche de chemin sur des cartes avec mosaïque

Answer 5

dans Pacman tous les fantômes avaient un algorithme de poursuite différent

• Blinky - > Chases. Empruntera généralement le chemin le plus court et tend à le suivre.
• Pinky - > Des embuscades A tendance à prendre un chemin plus détourné vers pac-man. Mortel. (pinky et blinky ont tendance à faire des choix différents lors du choix d'une direction, mettant souvent le joueur en cage dans un coin)
• Inky - > Freak. Ce mec agit étrangement. Il fait le tour du tableau assez au hasard, mais le poursuit parfois quand il se rapproche.
• Clyde - > Idiot. Se déplace au hasard. Pas vraiment une menace.

Les fantômes ont un schéma intéressant programmé dans leurs mouvements: parfois, ils cesseront simultanément d’abandonner la poursuite de Pac-Man et retourneront à leurs coins respectifs du labyrinthe, en entrant dans le "mode dispersion".

il existe une description complète de l'algo à l'adresse du dossier pacman .

salutations

Guillaume

Answer 6

Vous pourriez commencer à regarder A * (une étoile)

.

Et voici une page contenant des liens vers d'autres algorithmes de recherche de chemin.

[modifier] gah ... le cerveau est trop lent ... j'ai oublié ce livre, il est en C ou C ++ (je ne sais plus lequel), mais vous pouvez toujours obtenir les concepts pour Java. Ce n'est peut-être pas le plus facile pour vous de lire, mais dans l'ensemble, ce n'est pas mal. AI pour les développeurs de jeux de David M. Bourg, Glenn Seemann .

Answer 7

Je pense qu’il faut privilégier l’algorithme du chemin le plus court à chaque mouvement effectué par pacman. La l'algorithme de Dijkstra est une très bonne implémentation.

Juste pour résumer: visualisez le labyrinthe sous forme de graphique avec des sommets et des arêtes. Chaque bord a une attente (dans votre cas, tous les bords ont le même poids). L'algorithme trouve le chemin le plus court du sommet de la source au sommet de la cible en descendant d'une étape vers le bas de chaque bord immédiatement accessible. Ensuite, au sommet suivant, faites de même et continuez jusqu’à atteindre la cible. Le premier chemin atteint est le plus court chemin. De nombreuses optimisations peuvent être apportées à cet algorithme pour accélérer les choses, par exemple en tenant compte de l'emplacement du pacman dans sa position précédente et de la direction dans laquelle il s'est déplacé afin que vous puissiez obtenir des héritages dans l'algorithme. Je suggérerais de trouver le chemin le plus court de chaque fantôme à pacman à chaque mouvement et de déplacer le fantôme dans cette direction. Finalement, la distance diminuera et vous pourrez attraper pacman.

Une autre heuristique qui peut être utilisée pour trouver toutes les limites immédiates accessibles depuis pacman et essayer de couvrir autant de ces sommets que possible par des fantômes. Ainsi, au lieu de définir pacman comme sommet cible, nous définissons les sommets immédiatement accessibles comme cible par pacman. Le résultat est que les fantômes disponibles tenteront de couvrir les principales échappées de pacman et de l’attraper.