Pacman: comment les yeux retrouvent-ils le trou du monstre?

321

J'ai trouvé beaucoup de références à l'IA des fantômes dans Pacman, mais aucun d'entre eux n'a mentionné comment les yeux retrouvaient le trou du fantôme central après qu'un fantôme ait été mangé par Pacman.

Dans mon implémentation, j'ai implémenté une solution simple mais horrible. J'ai juste codé en dur à chaque coin dans quelle direction prendre.

Existe-t-il une meilleure / ou la meilleure solution? Peut-être un générique qui fonctionne avec différents niveaux de conception?

RoflcoptrException
la source
11
Êtes-vous sûr que le codage en dur sur le coin est assez bon? Cela ne garantit pas le meilleur itinéraire. Imaginez que le fantôme fait face à un long passage étroit. Selon votre algorithme, il devrait descendre tout ce passage, atteindre un coin, puis emprunter l'itinéraire le plus rapide. Si vous codez en dur sur chaque carré dans quelle direction aller, il saura peut-être simplement faire demi-tour en premier.
Mark Peters
3
@Mark, dépend de votre définition d'un coin. S'il s'agit d'une connexion en T, même si vous allez directement dans la ligne supérieure, c'est très bien.
Thorbjørn Ravn Andersen
1
@ Thorbjørn: Je ne parle même pas des intersections. Jetez un œil à ce forum: en.wikipedia.org/wiki/File:Pac-man.png . Si le fantôme se déplaçait vers la droite et se positionnait au deuxième point en bas à gauche, il ne rencontrerait aucune intersection pendant un certain temps. Cela lui fera parcourir 10 cases plus loin que s'il avait tourné en arrière (à gauche) et pris le chemin le plus court.
Mark Peters
6
votre solution utilise des points de cheminement (ou des miettes de pain), et je pense que c'est une technique couramment utilisée pour accélérer les algorithmes de recherche de chemin.
Nick Dandoulakis
1
Merci pour toutes les réponses! Je suis juste resté à ma solution précédente et j'ai codé en dur les directions à chaque coin. Pour le rendre générique, il est nécessaire que le fichier leveldesigner / a level définisse également ces informations dans la définition de niveau.
RoflcoptrException

Réponses:

152

En fait, je dirais que votre approche est une solution assez impressionnante, avec un coût d'exécution presque nul par rapport à n'importe quel type de recherche de chemin.

Si vous en avez besoin pour généraliser à des cartes arbitraires, vous pouvez utiliser n'importe quel algorithme de recherche de chemin - la recherche en largeur d'abord est simple à implémenter, par exemple - et l'utiliser pour calculer les directions à encoder à chacun des coins, avant que le jeu ne soit exécuté.

EDIT (11 août 2010): Je viens de me référer à une page très détaillée sur le système Pacman: le dossier Pac-Man , et puisque j'ai la réponse acceptée ici, j'ai pensé que je devrais la mettre à jour. L'article ne semble pas couvrir explicitement l'acte de retourner dans la maison du monstre, mais il déclare que la recherche directe de chemin dans Pac-Man est un cas de ce qui suit:

  • continuer à se déplacer vers la prochaine intersection (bien qu'il s'agisse essentiellement d'un cas spécial de «lorsque vous avez le choix, choisissez la direction qui n'implique pas d'inverser votre direction, comme vu à l'étape suivante);
  • à l'intersection, regardez les carrés de sortie adjacents, sauf celui dont vous venez de sortir;
  • choisir celui qui est le plus proche du but. Si plusieurs d'entre eux sont également proches du but, choisissez la première direction valide dans cet ordre: haut, gauche, bas, droite.
Kylotan
la source
16
Je pense qu'il veut dire que vous pouvez le calculer au moment de l'exécution (lorsque le niveau est chargé mais avant de commencer à le jouer) mais juste une fois. Ce n'est pas difficile à maintenir.
Mark Peters
3
Ouais, ou s'il y a un outil pour créer les cartes, dans le cadre de cela.
Kylotan
6
Il n'y a rien de mal à précalculer les chemins de retour. Vous échangez du stockage (chemins) pour des performances d'exécution.
Steve Kuo
6
Merci. Je pense que je m'en tiendrai à cette solution. Quelqu'un sait comment cela a été fait dans le Pacman original?
RoflcoptrException
4
Non, non. La question d'origine utilisait ce terme, mais il n'est pas exactement juridiquement contraignant.
Kylotan
85

J'ai résolu ce problème pour les niveaux génériques de cette façon: Avant que le niveau ne commence, je fais une sorte de "remplissage par inondation" à partir du trou du monstre; chaque tuile du labyrinthe qui n'est pas un mur reçoit un numéro qui indique à quelle distance elle est éloignée du trou. Ainsi, lorsque les yeux sont sur une tuile à une distance de 68, ils regardent laquelle des tuiles voisines a une distance de 67; c'est la voie à suivre alors.

Erich Kitzmueller
la source
15
Oui. Floodfill est très bon pour éclairer la voie dans toute situation où le monde n'est pas trop grand pour le rendre viable. Je pense qu'il pourrait être utilisé même dans les grands mondes en imposant un réseau plus grossier dont la connectivité était précalculée. Cela ferait légèrement bouger les choses, mais ce serait mieux que les embouteillages que j'ai vus dans de tels jeux.
Loren Pechtel
1
Pour économiser de l'espace (pour les mondes plus grands ou les systèmes contraints), vous pouvez enregistrer la direction à parcourir à chaque intersection, plutôt que d'enregistrer une valeur pour chaque tuile. C'est essentiellement ce que OP suggérait.
BlueRaja - Danny Pflughoeft
BlueRaja: Bien sûr, mais c'est plus complexe à faire et le résultat n'est pas aussi optimal - le fantôme est mangé entre deux intersections, donc il pourrait courir dans la mauvaise direction pendant un certain temps. Ma solution fonctionnait bien sur un en.wikipedia.org/wiki/HP_200LX, alors combien pourrait-elle être plus contrainte?
Erich Kitzmueller
5
(Je suis en retard ...) Oui, l'inondation est bonne, mais vous n'avez pas réellement besoin d'un nombre complet, juste une direction (deux bits) dans chaque carré pour pointer vers le carré suivant à utiliser.
Matthieu M.
Matthieu: Oui, ce serait une optimisation possible.
Erich Kitzmueller
42

Pour une alternative aux algorithmes de recherche de chemins plus traditionnels, vous pouvez jeter un œil au modèle (correctement nommé!) Pac-Man Scent Antiobject .

Vous pouvez diffuser un parfum de trou de monstre autour du labyrinthe au démarrage et laisser les yeux le suivre à la maison.

Une fois l'odeur configurée, le coût d'exécution est très faible.


Edit: malheureusement l'article de wikipedia a été supprimé, donc WayBack Machine à la rescousse ...

Dan Vinton
la source
2
ça allait être ma réponse. C'est essentiellement la même chose que les ammoQ, mais je me souviens toujours de l'odeur de pacman :)
Luke Schafer
On dirait que l'article wikipedia est mort / supprimé. Le résultat principal de Google est ce fil, mais je pense que cela se rapproche.
David
2
Je suis devenu confus pendant une seconde, mais j'ai immédiatement compris ce que l'on entend par "parfum". C'est une excellente façon de décrire ces choses de champ scalaire!
Steven Lu
18

Vous devriez jeter un œil à un algorithme de recherche de chemin , comme l'algorithme de Dijsktra ou l' algorithme A * . Voici quel est votre problème: un problème de graphique / chemin.

Clement Herreman
la source
18

Toute solution simple qui fonctionne est maintenable, fiable et fonctionne assez bien est une bonne solution. Il me semble que vous avez déjà trouvé une bonne solution ...

Une solution de recherche de chemin d'accès sera probablement plus compliquée que votre solution actuelle, et donc plus susceptible de nécessiter un débogage. Ce sera probablement aussi plus lent.

OMI, s'il n'est pas cassé, ne le répare pas.

ÉDITER

IMO, si le labyrinthe est corrigé, alors votre solution actuelle est un code bon / élégant. Ne faites pas l'erreur d'assimiler "bon" ou "élégant" avec "intelligent". Un code simple peut également être "bon" et "élégant".

Si vous avez des niveaux de labyrinthe configurables, vous devriez peut-être simplement faire le cheminement lors de la configuration initiale des labyrinthes. Le plus simple serait de demander au concepteur de labyrinthe de le faire à la main. Je ne prendrais la peine d'automatiser cela que si vous avez un bazillion de labyrinthes ... ou si les utilisateurs peuvent les concevoir.

(À part: si les routes sont configurées à la main, le concepteur de labyrinthe pourrait rendre un niveau plus intéressant en utilisant des routes sous-optimales ...)

Stephen C
la source
Oui ça marche. Cependant, je voudrais écrire du bon code et pas seulement du code. Et en plus j'ai ajouté la dernière phrase de ma question, donc si possible l'algorithme devrait être non seulement pour un labyrinthe mais pour plusieurs.
RoflcoptrException
des labyrinthes peuvent également être générés (j'ai un algorithme qui génère de jolis labyrinthes pacman), donc un peu d'automatisation est la voie à suivre
Erich Kitzmueller
"... ou les utilisateurs peuvent les concevoir." Dans ce cas, vous avez un labyrinthe de bazillions.
phuzion
@phuzion - J'en suis conscient. Cependant, il existe une distinction entre les deux cas. Si c'est l'OP qui crée un labyrinthe de bazzilion, alors c'est un inconvénient d'avoir à créer le routage à la main. S'il s'agit d'un utilisateur final ... cela signifie que l'OP doit rédiger de la documentation, effectuer un dépannage sans fin des dédales des utilisateurs finaux, répondre à d'innombrables plaintes concernant son manque d'amitié, etc. En d'autres termes, les raisons de la mise en œuvre de la génération automatique d'itinéraire sont différentes .
Stephen C
14

Dans le Pacman original, le fantôme a trouvé le mangeur de pilules jaunes par son "odeur", il laisserait une trace sur la carte, le fantôme se promènerait au hasard jusqu'à ce qu'il trouve l'odeur, puis ils suivraient simplement le chemin de l'odeur qui les mènerait directement à le joueur. Chaque fois que Pacman se déplaçait, les «valeurs de l'odeur» diminuaient de 1.

Maintenant, un moyen simple d'inverser tout le processus serait d'avoir une "pyramide d'odeur fantôme", qui a son point le plus élevé au centre de la carte, puis le fantôme se déplace simplement dans la direction de cette odeur.

Ivo Wetzel
la source
J'aime vraiment cette approche et je vais aussi essayer celle-ci
RoflcoptrException
5
Ce n'est pas correct; S'ils suivaient tous cet algorithme, ils finiraient par lui courir après un seul fichier. Le comportement de chaque fantôme est différent; vous pouvez trouver plus d'informations sur l'article Wikipedia.
diviseur
5

En supposant que vous ayez déjà la logique requise pour chasser pacman, pourquoi ne pas réutiliser cela? Changez simplement la cible. Il semble que ce serait beaucoup moins de travail que d'essayer de créer une toute nouvelle routine en utilisant exactement la même logique.

John Gardeniers
la source
oui j'ai la logique de chasser pacman déjà implémentée, mais je ne
suis
D'après mon expérience (j'aime écrire des versions de pacman juste pour le plaisir), cela peut conduire à des yeux coincés hors du trou pendant longtemps. C'est parce que l'algorithme de poursuite va généralement dans le sens de "si pacman est au nord, allez au nord" mais le labyrinthe pourrait contenir des "pièges" où les yeux devraient d'abord aller au sud. Puisque pacman se déplace, le fantôme s'échappera tôt ou tard, mais le trou est une cible fixe. (Remarque: je parle de labyrinthes générés)
Erich Kitzmueller
3

Que diriez-vous de chaque carré ayant une valeur de distance au centre? De cette façon, pour chaque carré donné, vous pouvez obtenir des valeurs de carrés voisins immédiats dans toutes les directions possibles. Vous choisissez le carré avec la valeur la plus basse et vous vous déplacez vers ce carré.

Les valeurs seraient précalculées en utilisant n'importe quel algorithme disponible.

mvbl fst
la source
J'allais suggérer cela. Un remblai vers l'extérieur à partir du «trou de monstre». Je pense que votre réponse bénéficierait d'une photo.
AjahnCharles
3

C'était la meilleure source que j'ai pu trouver sur la façon dont cela fonctionnait réellement.

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Lorsque les fantômes sont tués, leurs yeux désincarnés retournent à leur emplacement de départ. Ceci est simplement accompli en plaçant la tuile cible du fantôme à cet endroit. La navigation utilise les mêmes règles.

Cela a du sens. Ce n'est peut-être pas le plus efficace au monde, mais c'est une très bonne façon de ne pas avoir à vous soucier d'un autre état ou quoi que ce soit dans ce sens, vous changez simplement la cible.

Note latérale: Je ne savais pas à quel point ces programmeurs pac-man étaient géniaux, ils ont essentiellement créé un système de messagerie entier dans un très petit espace avec une mémoire très limitée ... c'est incroyable.

Midpipps
la source
2

Je pense que votre solution est juste pour le problème, plus simple que cela, est de rendre une nouvelle version plus "réaliste" où les yeux fantômes peuvent traverser les murs =)

Hernán Eche
la source
2
Pour ajouter encore plus de réalisme, permettez aux fantômes eux-mêmes de pouvoir se déplacer à travers les murs: D
Thomas Eding
3
Ce sont les murs opaques du fantôme, mais les fantômes du second ordre (fantôme d'un fantôme) sont plus transparents. (vous pouvez trouver de nombreux manuels d'utilisation avec des bugs transformés en fonctionnalités)
Hernán Eche
1
+1 pour les "fantômes du second ordre" - oh oui, le dérivé d'un fantôme doit sûrement transcender les simples objets du premier ordre comme les murs ... :)
Assad Ebrahim
2

Voici un analogue et un pseudocode à l'idée de remplissage d'inondation de ammoQ.

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

L'idée est que c'est une recherche en premier, donc à chaque fois que vous rencontrez un nouveau carré adjacent s, le meilleur chemin passe par p. C'est O (N) je crois.

Mark Peters
la source
2

Je ne sais pas grand-chose sur la façon dont vous avez implémenté votre jeu, mais vous pouvez faire ce qui suit:

  1. Déterminez l'emplacement relatif des yeux par rapport à la porte. c'est à dire est-il laissé au-dessus? Juste en dessous?
  2. Ensuite, déplacez les yeux en face de l'une des deux directions (par exemple, faites-le bouger vers la gauche s'il est à droite de la porte et en dessous de la porte) et vérifiez s'il y a des murs et vous en empêche.
  3. S'il y a des murs qui vous empêchent de le faire, faites-le se déplacer dans l'autre sens (par exemple, si les coordonnées des yeux par rapport à la broche sont juste au nord et qu'il se déplaçait actuellement à gauche mais qu'il y a un mur dans la manière de le faire se déplacer vers le sud.
  4. N'oubliez pas de continuer à vérifier à chaque fois pour vous déplacer pour continuer à vérifier où les yeux sont par rapport à la porte et vérifiez s'il n'y a pas de coordonnées latitudinales. c'est-à-dire que ce n'est qu'au-dessus de la porte.
  5. Dans le cas où ce n'est qu'au-dessus de la porte, descendez s'il y a un mur, déplacez-vous à gauche ou à droite et continuez à faire ce numéro 1 - 4 jusqu'à ce que les yeux soient dans la tanière.
  6. Je n'ai jamais vu d'impasse dans Pacman, ce code ne tiendra pas compte des impasses.
  7. En outre, j'ai inclus une solution pour quand les yeux «oscilleraient» entre un mur qui enjambe l'origine dans mon pseudocode.

Quelques pseudocodes:

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile

la source
2

La suggestion de dtb23 de simplement choisir une direction aléatoire à chaque coin, et vous finirez par trouver les sons de trou de monstre horriblement inefficaces.

Cependant, vous pouvez utiliser son algorithme de retour à la maison inefficace pour rendre le jeu plus amusant en introduisant plus de variations dans la difficulté du jeu. Pour ce faire, appliquez l'une des approches ci-dessus telles que vos points de cheminement ou le remplissage de l'inondation, mais en le faisant de manière non déterministe. Ainsi, à chaque coin, vous pouvez générer un nombre aléatoire pour décider s'il faut prendre la voie optimale ou une direction aléatoire.

Au fur et à mesure que le joueur progresse, vous réduisez la probabilité qu'une direction aléatoire soit prise. Cela ajouterait un autre levier sur le niveau de difficulté global en plus de la vitesse de niveau, de la vitesse fantôme, de la pause de prise de pilule (etc.). Vous avez plus de temps pour vous détendre tandis que les fantômes ne sont que des yeux inoffensifs, mais ce temps devient de plus en plus court à mesure que vous progressez.

imoatama
la source
2

Réponse courte, pas très bien. :) Si vous modifiez le labyrinthe de Pac-man, les yeux ne reviendront pas nécessairement. Certains des hacks flottants ont ce problème. Cela dépend donc d'avoir un labyrinthe coopératif.

dwidel
la source
2

Je proposerais que le fantôme stocke le chemin qu'il a pris du trou au Pacman. Ainsi, dès que le fantôme meurt, il peut suivre ce chemin stocké dans le sens inverse.

Fischer Ludrian
la source
2
ce chemin sera probablement trop long
Ahmad Y. Saleh
Chaque fois que vous revisitez un nœud, vous pouvez éliminer une boucle de l'historique. Cela rendrait les choses un peu plus directes. Cela pourrait être plus intéressant que de toujours suivre le même chemin direct, mais assez souvent, il comprendra des boucles presque idiotes (par exemple, 3 côtés d'un carré).
AjahnCharles
1

Sachant que les chemins pacman ne sont pas aléatoires (c'est-à-dire que chaque niveau spécifique 0-255, encre, clignotant, pinky et clyde fonctionnera exactement le même chemin pour ce niveau).

Je prendrais ceci et devinerais alors qu'il y a quelques chemins principaux qui enroulent tout le labyrinthe comme un "chemin de retour" qu'un objet globe oculaire prend en attente là où il est quand l'homme pac a mangé le fantôme.

Incognito
la source
1

Les fantômes de pacman suivent des schémas plus ou moins prévisibles en termes de tentative de correspondance sur X ou Y en premier jusqu'à ce que l'objectif soit atteint. J'ai toujours supposé que c'était exactement la même chose pour les yeux qui revenaient.

socle
la source
1
  1. Avant le début du jeu, enregistrez les nœuds (intersections) dans la carte
  2. Lorsque le monstre meurt, prenez le point (coordonnées) et trouvez le nœud le plus proche dans votre liste de nœuds
  3. Calculez tous les chemins partant de ce nœud jusqu'au trou
  4. Prenez le chemin le plus court par la longueur
  5. Ajouter la longueur de l'espace entre le point et le nœud le plus proche
  6. Dessiner et se déplacer sur le chemin

Prendre plaisir!

GingerHead
la source
1

Mon approche est un peu gourmande en mémoire (du point de vue de l'ère Pacman), mais vous n'avez besoin de calculer qu'une seule fois et cela fonctionne pour tous les niveaux de conception (y compris les sauts).

Étiqueter les nœuds une fois

Lorsque vous chargez un niveau pour la première fois, étiquetez tous les nœuds de l'antre du monstre 0 (représentant la distance de l'antre). Continuez à étiqueter les nœuds connectés 1, les nœuds connectés à eux, etc., jusqu'à ce que tous les nœuds soient étiquetés. (note: cela fonctionne même si l'antre a plusieurs entrées)

Je suppose que vous avez déjà des objets représentant chaque nœud et des connexions à leurs voisins. Le pseudo-code pourrait ressembler à ceci:

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

Remplir de tanière

Les yeux se déplacent vers le voisin avec l'étiquette de distance la plus basse

Une fois que tous les nœuds sont étiquetés, le routage des yeux est trivial ... il suffit de choisir le nœud voisin avec l'étiquette de distance la plus basse (remarque: si plusieurs nœuds ont une distance égale, peu importe lequel est choisi). Pseudo code:

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

Exemple entièrement étiqueté

Carte complète

AjahnCharles
la source
0

Pour mon jeu PacMan, j'ai créé un shortest multiple path homealgorithme quelque peu " " qui fonctionne pour le labyrinthe que je lui fournisse (dans mon ensemble de règles). Il fonctionne également à travers les tunnels.

Lorsque le niveau est chargé, tout path home data in every crossroadest vide (par défaut) et une fois que les fantômes commencent à explorer le labyrinthe, ils crossroad path home informationcontinuent d'être mis à jour chaque fois qu'ils rencontrent un «nouveau» carrefour ou d'un chemin différent trébuchent à nouveau sur leur carrefour connu.

iNyuu
la source
-2

Le pac-man original n'utilisait pas la recherche de chemin ni l'IA sophistiquée. Cela a simplement fait croire aux joueurs qu'il y avait plus de profondeur qu'elle ne l'était réellement, mais en fait, c'était aléatoire. Comme indiqué dans Intelligence artificielle pour les jeux / Ian Millington, John Funge.

Je ne sais pas si c'est vrai ou non, mais cela a beaucoup de sens pour moi. Honnêtement, je ne vois pas ces comportements dont les gens parlent. Red / Blinky for ex ne suit pas le joueur à tout moment, comme on dit. Personne ne semble suivre systématiquement le joueur, exprès. La chance qu'ils vous suivent me semble aléatoire. Et il est tout simplement très tentant de voir le comportement de façon aléatoire, surtout lorsque les chances de se faire chasser sont très élevées, avec 4 ennemis et des options de virage très limitées, dans un petit espace. Au moins dans sa mise en œuvre initiale, le jeu était extrêmement simple. Consultez le livre, il est dans l'un des premiers chapitres.

user4664601
la source
oui, il a utilisé de l'IA. Et oui Blinky suit pacman quand il est en mode poursuite (y passe de temps en temps), donc c'est bien l'IA
Jean-François Fabre