Ich fand viele Hinweise auf die KI der Geister in Pacman, aber keiner von ihnen erwähnte, wie die Augen ihren Weg zurück zum zentralen Geisterloch finden, nachdem ein Geist von Pacman gefressen wurde.
In meiner Implementierung habe ich eine einfache, aber schreckliche Lösung implementiert. Ich habe nur an jeder Ecke fest codiert, in welche Richtung ich gehen soll.
Gibt es eine bessere / oder die beste Lösung? Vielleicht eine generische, die mit verschiedenen Level-Designs funktioniert?
artificial-intelligence
path-finding
heuristics
pacman
RoflcoptrException
quelle
quelle
Antworten:
Eigentlich würde ich sagen, dass Ihr Ansatz eine ziemlich großartige Lösung ist, mit fast null Laufzeitkosten im Vergleich zu jeder Art von Pfadfindung.
Wenn Sie es benötigen, um es auf beliebige Karten zu verallgemeinern, können Sie einen beliebigen Pfadfindungsalgorithmus verwenden - die Breitensuche ist beispielsweise einfach zu implementieren - und damit berechnen, welche Richtungen an jeder Ecke codiert werden sollen, bevor das Spiel ausgeführt wird.
EDIT (11. August 2010): Ich wurde gerade auf eine sehr detaillierte Seite des Pacman-Systems verwiesen: Das Pac-Man-Dossier , und da ich hier die akzeptierte Antwort habe, hatte ich das Gefühl, ich sollte sie aktualisieren. Der Artikel scheint nicht explizit die Rückkehr zum Monsterhaus zu behandeln, aber er besagt, dass die direkte Wegfindung in Pac-Man ein Fall von Folgendem ist:
quelle
Ich habe dieses Problem für generische Levels folgendermaßen gelöst: Bevor das Level beginnt, mache ich eine Art "Flood Fill" aus dem Monsterloch; Jedes Plättchen des Labyrinths, das keine Wand ist, erhält eine Zahl, die angibt, wie weit es vom Loch entfernt ist. Wenn sich die Augen also auf einer Kachel mit einem Abstand von 68 befinden, sehen sie, welche der benachbarten Kacheln einen Abstand von 67 hat. das ist dann der richtige Weg.
quelle
Als Alternative zu herkömmlichen Pfadfindungsalgorithmen können Sie sich das (entsprechend benannte!) Pac-Man Scent Antiobject-Muster ansehen .
Sie könnten beim Start den Duft von Monsterlöchern im Labyrinth verbreiten und die Augen nach Hause folgen lassen.
Sobald der Geruch eingerichtet ist, sind die Laufzeitkosten sehr niedrig.
Edit: Leider wurde der Wikipedia-Artikel gelöscht, also WayBack Machine zur Rettung ...
quelle
Sie sollten sich einen Pfadfindungsalgorithmus wie den Dijsktra-Algorithmus oder den A * -Algorithmus ansehen . Dies ist Ihr Problem: ein Diagramm- / Pfadproblem.
quelle
Jede einfache Lösung, die funktioniert, ist wartbar, zuverlässig und funktioniert gut genug, ist eine gute Lösung. Es klingt für mich so, als hätten Sie bereits eine gute Lösung gefunden ...
Eine Pfadfindungslösung ist wahrscheinlich komplizierter als Ihre aktuelle Lösung und erfordert daher eher ein Debugging. Es wird wahrscheinlich auch langsamer sein.
IMO, wenn es nicht kaputt ist, reparieren Sie es nicht.
BEARBEITEN
IMO, wenn das Labyrinth fixiert ist dann Ihre aktuelle Lösung ist gut / elegant - Code. Machen Sie nicht den Fehler, "gut" oder "elegant" mit "klug" gleichzusetzen. Einfacher Code kann auch "gut" und "elegant" sein.
Wenn Sie konfigurierbare Labyrinth-Ebenen haben, sollten Sie möglicherweise nur die Pfadfindung durchführen, wenn Sie die Labyrinthe zum ersten Mal konfigurieren. Am einfachsten wäre es, den Labyrinthdesigner dazu zu bringen, dies von Hand zu tun. Ich würde mich nur darum kümmern, dies zu automatisieren, wenn Sie eine Unmenge Labyrinthe haben ... oder Benutzer sie entwerfen können.
(Nebenbei: Wenn die Routen von Hand konfiguriert werden, könnte der Labyrinthdesigner ein Level durch die Verwendung suboptimaler Routen interessanter machen ...)
quelle
Im ursprünglichen Pacman fand der Geist den gelben Pillenfresser durch seinen "Geruch", er würde eine Spur auf der Karte hinterlassen, der Geist würde zufällig herumwandern, bis sie den Geruch fanden, dann würden sie einfach dem Geruchspfad folgen, zu dem sie direkt führten der Spieler. Jedes Mal, wenn sich Pacman bewegte, wurden die "Geruchswerte" um 1 verringert.
Ein einfacher Weg, um den gesamten Prozess umzukehren, wäre eine "Pyramide des Geistergeruchs", deren höchster Punkt in der Mitte der Karte liegt. Dann bewegt sich der Geist einfach in Richtung dieses Geruchs.
quelle
Angenommen, Sie haben bereits die Logik, die erforderlich ist, um Pacman zu jagen, warum sollten Sie das nicht wiederverwenden? Ändern Sie einfach das Ziel. Es scheint viel weniger Arbeit zu sein, als zu versuchen, eine ganz neue Routine mit genau derselben Logik zu erstellen.
quelle
Es ist ein Wegfindungsproblem. Einen beliebten Algorithmus finden Sie unter http://wiki.gamedev.net/index.php/A* .
quelle
Wie wäre es mit jedem Quadrat, das einen Abstand zum Zentrum hat? Auf diese Weise können Sie für jedes gegebene Quadrat Werte von unmittelbaren Nachbarquadraten in alle möglichen Richtungen erhalten. Sie wählen das Quadrat mit dem niedrigsten Wert und bewegen sich zu diesem Quadrat.
Die Werte würden mit jedem verfügbaren Algorithmus vorberechnet.
quelle
Dies war die beste Quelle, die ich finden konnte, wie es tatsächlich funktionierte.
http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Wenn die Geister getötet werden, kehren ihre körperlosen Augen zu ihrem Ausgangspunkt zurück. Dies wird einfach erreicht, indem das Zielplättchen des Geistes auf diesen Ort gesetzt wird. Die Navigation verwendet dieselben Regeln.
Es macht tatsächlich Sinn. Vielleicht nicht die effizienteste der Welt, aber eine ziemlich gute Möglichkeit, sich keine Sorgen um einen anderen Staat oder irgendetwas in dieser Richtung machen zu müssen. Sie ändern nur das Ziel.
Randnotiz: Ich wusste nicht, wie großartig diese Pac-Man-Programmierer waren, die im Grunde genommen ein ganzes Nachrichtensystem auf sehr kleinem Raum mit sehr begrenztem Speicher erstellt haben ... das ist erstaunlich.
quelle
Ich denke, Ihre Lösung ist richtig für das Problem, einfacher als das, eine neue Version "realistischer" zu machen, bei der Geisteraugen durch Wände gehen können =)
quelle
Hier ist ein Analogon und ein Pseudocode zur Flutfüllungsidee von ammoQ.
Die Idee ist, dass es sich um eine Breitensuche handelt. Jedes Mal, wenn Sie auf ein neues benachbartes Quadrat s stoßen, führt der beste Weg durch p. Es ist O (N), glaube ich.
quelle
Ich weiß nicht viel darüber, wie Sie Ihr Spiel implementiert haben, aber Sie könnten Folgendes tun:
Ein Pseudocode:
quelle
Der Vorschlag von dtb23, an jeder Ecke nur eine zufällige Richtung zu wählen, und schließlich werden Sie feststellen, dass das Monsterloch schrecklich unzulänglich klingt.
Sie können jedoch den ineffizienten Return-to-Home-Algorithmus verwenden, um das Spiel unterhaltsamer zu gestalten, indem Sie den Schwierigkeitsgrad des Spiels variieren. Sie würden dies tun, indem Sie einen der oben genannten Ansätze wie Ihre Wegpunkte oder die Flutfüllung anwenden, dies jedoch nicht deterministisch. Sie können also an jeder Ecke eine Zufallszahl generieren, um zu entscheiden, ob Sie den optimalen Weg oder eine zufällige Richtung wählen.
Mit fortschreitendem Level verringern Sie die Wahrscheinlichkeit, dass eine zufällige Richtung eingeschlagen wird. Dies würde zusätzlich zur Levelgeschwindigkeit, Geistergeschwindigkeit, Pillenfresspause (usw.) einen weiteren Hebel für den Gesamtschwierigkeitsgrad hinzufügen. Sie haben mehr Zeit zum Entspannen, während die Geister nur harmlose Augen sind, aber diese Zeit wird im Laufe der Zeit immer kürzer.
quelle
Kurze Antwort, nicht sehr gut. :) Wenn Sie das Pac-Man-Labyrinth ändern, werden die Augen nicht unbedingt zurückkommen. Einige der herumschwebenden Hacks haben dieses Problem. Es kommt also auf ein kooperatives Labyrinth an.
quelle
Ich würde vorschlagen, dass der Geist den Weg speichert, den er vom Loch zum Pacman genommen hat. Sobald der Geist stirbt, kann er diesem gespeicherten Pfad in umgekehrter Richtung folgen.
quelle
Wenn Sie wissen, dass Pacman-Pfade nicht zufällig sind (dh jedes spezifische Level 0-255, Inky, Blinky, Pinky und Clyde funktionieren genau für dieses Level).
Ich würde dies nehmen und dann vermuten, dass es einige Hauptpfade gibt, die das gesamte Labyrinth als "Rückweg" umschließen, den ein Augapfelobjekt nimmt, bis es dort ist, wo Pac Man den Geist gegessen hat.
quelle
Die Geister in Pacman folgen mehr oder weniger vorhersehbaren Mustern, wenn sie versuchen, zuerst auf X oder Y zu passen, bis das Ziel erreicht ist. Ich habe immer angenommen, dass dies genau das gleiche für Augen ist, die ihren Weg zurück finden.
quelle
Genießen!
quelle
Mein Ansatz ist ein wenig speicherintensiv (aus der Sicht der Pacman-Ära), aber Sie müssen nur einmal rechnen und es funktioniert für jedes Level-Design (einschließlich Sprünge).
Beschriften Sie die Knoten einmal
Wenn du zum ersten Mal ein Level lädst, beschrifte alle Monster-Lair-Knoten mit 0 (was den Abstand zum Lair darstellt). Beschriften Sie die verbundenen Knoten 1, die mit ihnen verbundenen Knoten 2 usw. nach außen, bis alle Knoten beschriftet sind. (Hinweis: Dies funktioniert sogar, wenn das Versteck mehrere Eingänge hat.)
Ich gehe davon aus, dass Sie bereits Objekte haben, die jeden Knoten und Verbindungen zu seinen Nachbarn darstellen. Pseudocode könnte ungefähr so aussehen:
Die Augen bewegen sich zum Nachbarn mit dem Etikett mit dem geringsten Abstand
Sobald alle Knoten beschriftet sind, ist das Routing der Augen trivial. Wählen Sie einfach den Nachbarknoten mit der niedrigsten Entfernungsbeschriftung aus (Hinweis: Wenn mehrere Knoten den gleichen Abstand haben, spielt es keine Rolle, welcher ausgewählt wird). Pseudocode:
Vollständig beschriftetes Beispiel
quelle
Für mein PacMan-Spiel habe ich einen etwas "
shortest multiple path home
" Algorithmus erstellt, der für jedes Labyrinth funktioniert, mit dem ich es versorge (innerhalb meiner Regeln). Es funktioniert auch über diese Tunnel.Wenn das Level geladen ist, ist alles
path home data in every crossroad
leer (Standard) und sobald die Geister beginnen, das Labyrinth zu erkunden, werden siecrossroad path home information
jedes Mal aktualisiert, wenn sie auf eine "neue" Kreuzung stoßen oder von einem anderen Pfad wieder auf ihre bekannte Kreuzung stoßen.quelle
Der ursprüngliche Pac-Man benutzte keine Wegfindung oder ausgefallene KI. Es hat die Spieler nur glauben lassen, dass es mehr Tiefe gibt als es tatsächlich war, aber tatsächlich war es zufällig. Wie in Künstliche Intelligenz für Spiele / Ian Millington, John Funge angegeben.
Ich bin mir nicht sicher, ob es wahr ist oder nicht, aber es macht für mich sehr viel Sinn. Ehrlich gesagt sehe ich diese Verhaltensweisen, über die die Leute sprechen, nicht. Red / Blinky zum Beispiel folgt dem Spieler nicht immer, wie es heißt. Niemand scheint dem Spieler absichtlich konsequent zu folgen. Die Chance, dass sie dir folgen, erscheint mir zufällig. Und es ist einfach sehr verlockend, zufälliges Verhalten zu sehen, besonders wenn die Chancen, verfolgt zu werden, mit 4 Feinden und sehr begrenzten Drehmöglichkeiten auf kleinem Raum sehr hoch sind. Zumindest in der ersten Implementierung war das Spiel extrem einfach. Schauen Sie sich das Buch an, es befindet sich in einem der ersten Kapitel.
quelle