Pacman : comment les yeux trouver leur chemin vers le trou de monstre ?

Question

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

Dans ma mise en œuvre, j'ai implémenté une solution simple mais horrible. J'ai juste codé en dur à chaque coin quelle direction devrait être prise.

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

Answer 1

En fait, je dirais que votre approche est assez impressionnant, avec une quasi-nulle de l'exécution du coût par rapport à toute sorte de pathfinding.

Si vous avez besoin de généraliser à l'arbitraire des cartes, vous pouvez utiliser n'importe quel algorithme de pathfinding - largeur-première recherche est simple à mettre en œuvre, par exemple - et de l'utiliser pour calculer les directions d'encoder à chacun des coins, avant que le jeu est exécuté.

EDIT (11 août 2010): j'ai été appelé de façon très détaillée d'une page sur le Pacman système: Le Pac-Man Dossier, et depuis que j'ai accepté de répondre ici, j'ai senti que je devais le mettre à jour. L'article ne semble pas couvrir la loi de retour à l'monster house explicitement, mais il affirme que le pathfinding directe de Pac-Man est un cas suivants:

• continuer de progresser vers la prochaine intersection (même si c'est un cas particulier de " quand le choix, choisir la direction qui n'implique pas de renverser votre direction, comme on le voit dans l'étape suivante);
• à l'intersection, regardez les adjacente à la sortie carrés, à l'exception de celui d'où vous venez;
• en choisir un qui est plus proche de l'objectif. Si plus d'un est également à proximité de l'objectif, choisir le premier qui valide la direction dans cet ordre: haut, gauche, bas, droite.

Answer 2

J'ai résolu ce problème pour les niveaux génériques de cette façon: Avant que le niveau commence, je fais une sorte de "flood flood" du trou du monstre; Chaque carreau du labyrinthe qui n'est pas un mur reçoit un nombre qui indique à quelle distance il est loin du trou. Ainsi, quand les yeux sont sur une tuile avec une distance de 68, ils regardent lequel des carreaux voisins a une distance de 67; c'est le chemin à parcourir alors.

Answer 3

Pour une alternative à la plus traditionnelle de pathfinding des algorithmes, vous pouvez prendre un coup d'oeil à l' (le bien nommé!) Pac-Man Parfum Antiobject modèle.

Vous pourriez diffuse monstre-trou-parfum autour du labyrinthe au démarrage et ont les yeux suivent à la maison.

Une fois que l'odeur est mis en place, la durée d'exécution coût est très faible.

---

Edit: malheureusement, l'article de wikipédia a été supprimée, de sorte que WayBack Machine à la rescousse...

Answer 4

Vous devriez jeter un coup d'oeil à un algorithme de pathfindings, comme l'algorithme de Dijsktra ou l' algorithme A * . Voici votre problème: un problème de graphe / chemin.

Answer 5

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

Une recherche de chemin solution risque d'être plus compliqué que votre solution actuelle, et donc plus susceptibles de demander de débogage. Il sera probablement plus lent.

IMO, si elle n'est pas cassé, ne le répare pas.

MODIFIER

IMO, si le labyrinthe est fixe alors votre solution actuelle est bon / code élégant. Ne faites pas l'erreur d'assimiler la "bonne" ou "élégante" avec "intelligent". Simple code peut également être "bon" et "élégant".

Si vous avez configurable dédale de niveaux, alors peut-être vous devriez juste faire le pathfinding lorsque vous d'abord configurer les labyrinthes. Le plus simple serait d'obtenir le labyrinthe, le concepteur de le faire à la main. J'avais peine l'automatisation de ce si vous avez un bazillion labyrinthes ... ou les utilisateurs peuvent concevoir eux.

(Aparté: si les itinéraires sont configurés par la main, le labyrinthe concepteur pourrait faire un niveau plus intéressant par l'utilisation non optimale des itinéraires ... )