Wegfindung in einem Java 2D-Spiel?

StackOverflow https://stackoverflow.com/questions/623095

Frage

Im Wesentlichen ist es ein Pacman-Klon Spiel arbeite ich an. Ich habe einen Feind Klasse und 4 Instanzen dieser Klasse erstellt, die alle vier Geister des Spiels darstellen.

Starten Sie alle Geister in zufälligen Bereichen des Bildschirms und dann müssen sie ihren Weg in Richtung des Pacman Charakter arbeiten. Da der Spieler den Pacman steuert, um es zu bewegen, sollten sie es folgen und die nächste Möglichkeit, auf ihn nehmen.

Es gibt kein Labyrinth / Hindernisse (noch) nicht, so dass die gesamte Karte (400x400 Pixel) ist offen Boden zu ihnen.

Für den Spieler und jeden Geist, kann ich die X, Y abrufen, Bildbreite und Höhe Attribute. Auch i bereits eine Kollisionserkennungsalgorithmus, also keine Sorgen darüber, dass nur über die Geister ihren Weg zu Pacman zu finden.

War es hilfreich?

Lösung

Für einen guten Wegfindung Algorithmus unter Verwendung von A * wahrscheinlich eine gute Idee wäre, aber für ein einfaches Spiel, das nicht anspruchsvoll, effizient erfordert, noch ein wirksamen Weg suchen, einfach mit den Zeichen auf ein Ziel zu bewegen, indem die Richtung des Ziels herauszufinden, sollte ausreichend sein.

Zum Beispiel die Entscheidung, den Charakter Bewegung zu machen, in Pseudo-Code: 

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

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

Ja, wird das Zeichen nicht die effizienteste Bewegung machen gehen, aber es wird bei jeder Iteration des Spiel Schleife näher und näher an das Ziel bekommen.

Es ist auch meine Vermutung, dass ein Arcade-Spiel aus den frühen 80er Jahren würde wahrscheinlich nicht anspruchsvoll Wegfindung Algorithmen werden.

Andere Tipps

Wenn Sie nur ein Raster von Pixeln haben - ein „großes Feld“, auf dem Pacman und Geist kann sich frei bewegen - dann der kürzeste Weg ist einfach -. Eine gerade Linie zwischen dem Geist und dem Pacman

Aber „kürzester Weg“ immer bedeutet, dass wir versuchen, ein Graph-Theorie Problem zu lösen. (Ich gehe davon Kenntnis von Graphen, eine Graphentheorie, adj. Matrizen, usw.!)

Im obigen Fall betrachtet jedes Pixel ein Knoten in einem Diagramm zu sein. Jeder Knoten an seinen Nachbarn durch eine Kante verbunden ist, und jede Kante hat gleiche „Gewicht“ (Bewegen mit dem Knoten auf „oben“ ist nicht langsamer als mit dem Knoten bewegend „unten“).

Sie haben also diesen: ( "*" = Knoten "-, /, \, |" = Flanke) 

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

Wenn Pacman in der Mitte ist, kann es sehr leicht zu jedem anderen Knoten.

Etwas mehr näher an der Realität sein könnte folgendermaßen aus: 

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

Nun, Pacman kann nicht diagonal bewegen. Um von der Mitte nach rechts unten erfordert 2 „Hopfen“ statt einem.

den Fortschritt fortzusetzen: 

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

Nun, von einem Knoten in der Mitte zu einem Knoten an der Spitze zu gehen, müssen Sie 3 Hopfen. Allerdings bewegen in Richtung nur der Boden nimmt 1-Hop.

Es wäre leicht, jeden Spiel-Board-Setup in ein Diagramm zu übersetzen. Jede „Kreuzung“ ist ein Knoten. Der Pfad zwischen zwei Kreuzungspunkten ist eine Kante, und die Länge dieses Weges ist das Gewicht dieser Kante.

A * ein. Durch den Aufbau eines Graphen (verwenden Sie eine adjency Matrix oder eine Liste von Knoten) können Sie den A * -Algorithmus verwenden, den kürzesten Weg zu finden. Andere Algorithmen sind Dijkstra. Und viele andere! Aber zuerst müssen Sie Ihr Problem in Bezug auf ein Diagramm zu gestalten, und dann Spielzeug mit, wie Sie vom Knoten A gehen würden (Pacman) zum Knoten B (Geist).

Ich hoffe, das hilft!

Es ist schon eine sehr lange Zeit, aber die Geister in Pac-Man aus dem Gedächtnis haben im Weg Wegfindung nicht viel zu tun. Sie würden eine ziemlich Standard randomisierten Labyrinth Traversal tun, bis sie „entdeckt“ Sie, die sich entlang der Achse einen freien Weg zu Ihnen eines Korridors beteiligt zu finden, und dann würden sie direkt auf Sie, bis Sie aus ihrer Sichtlinie verschwunden, woraufhin sie würde ein zufälliges Muster fortzusetzen. Auf höheren Ebenen Pac-Man würde unsichtbare Wege für eine Weile hinter sich lassen, dass die Geister würden „riechen“ und manchmal folgen.

Wenn Pac-Man ein Einschalten bekommt, ist der einzige Unterschied in dem Algorithmus, dass, wenn sie dich entdecken, die Geister Sie statt dem Weg zu euch fliehen würden.

Also, für ein authentisches Erlebnis, werden Sie wahrscheinlich nicht brauchen einen sehr hoch entwickeltes Wegfindung Algorithmus überhaupt. Wenn Sie sein Phantasie wollen, natürlich können Sie eine * implementieren.

Gehen Sie direkt auf Ihre Feinde ist ein Anfang, aber wenn man ein Labyrinth hinzufügen werden Sie ein bisschen smarter Wegfindung so Ihre Geister hinzufügen wollen nicht in Kurven oder Sackgassen stecken bleiben.

Das folgende Tutorial ist eine große leichte Führung zu gehen mit A * gestartet, mit herunterladbaren Beispielen.

Path Finding auf Tile basierend Maps

in Pacman alle den Geist einen anderen chasing Algorithmus hatten

  • Blinky -> Chases. Wird in der Regel den kürzesten Weg nehmen Sie, und neigt dazu, zu folgen.
  • Pinky -> Hinterhalte. Neigt einen Umweg zu Pac-Man zu nehmen. Tötlich. (Kleiner Finger und Blinky neigen andere Wahl zu machen, wenn eine Richtung der Wahl, oft der Spieler in einer Ecke caging)
  • Inky -> Freak. Dieser Typ wirkt seltsam. Er bewegt sich über das Brett ziemlich zufällig, aber manchmal jagt, wenn er in der Nähe bekommt.
  • Clyde -> Idiot. Bewegt zufällig. Nicht viel von einer Bedrohung.

Die Geister haben ein interessantes Muster in ihre Bewegungen programmiert. Gelegentlich werden sie gleichzeitig einzustellen und ihre Verfolgung von Pac-Man Abstand nehmen und an ihre jeweiligen Ecken des Labyrinths zurückkehren, die Eingabe von „Streumodus“

gibt es eine vollständige Beschreibung der algo unter der Pacman Dossier

Bezug

Guillaume

Sie könnten beginnen Blick auf ein * (Ein Stern)

Und hier ist eine Seite , die Links zu anderen Weg zu finden, Algorithmen hat.

[Bearbeiten] gah ... Gehirn zu langsam ist ... über dieses Buch vergessen, ist es C oder C ++ (I vergessen welche), aber man kann immer noch die Konzepte für Java bekommen. Es kann nicht sein, das für Sie am einfachsten zu lesen, ist aber insgesamt nicht schlecht. AI für Spiele-Entwickler von David M. Bourg, Glenn Seemann .

Ich denke, für den kürzesten Weg Algorithmus geht bei jeder Bewegung von Pacman gemacht. Eine sehr gute Umsetzung ist Dijkstra-Algorithmus .

Just zusammenfassen: Visualisieren Sie das Labyrinth als Graph mit Ecken und Kanten. Jede Kante hat eine Wartezeit (in Ihrem Fall all Kanten haben gleiches Gewicht). Der Algorithmus findet den kürzesten Weg von der Quelle zum Ziel vertice vertice um einen Schritt nach unten jeweils sofort erreichbar Kante bewegt. Dann auf der nächsten vertice tun Sie das gleiche und behalten zu tun, bis Sie an das Ziel zu bekommen. Der erste Weg erreicht ist der kürzeste Weg. Es kann zu diesem Algorithmus getan viele Optimierungen sein, um die Dinge zu beschleunigen, wie zu berücksichtigen, wo der Pacman in seiner vorherigen Position war und in welcher Richtung es bewegte, so dass Sie einige heiristics im Algorithmus zu bekommen. Ich würde vorschlagen, den kürzesten Weg von jedem Geist zu Pacman auf jeder Bewegung zu finden und den Geist in dieser Richtung bewegen. Schließlich verringert sich der Abstand und Sie werden Pacman fangen können.

Eine andere Heuristik, die sie verwendet werden, können alle unmittelbaren Kanten erreichbar von Pacman zu finden und versuchen, so viele dieser Eckpunkte wie möglich von Geistern zu decken. Anstatt also Pacman als Ziel vertice der Einstellung setzen wir die Eckpunkte immediatetly erreichbar von Pacman als Ziel, das Ergebnis wird sein, dass die zur Verfügung stehenden Geister werden versuchen themajor Fluchtwege von Pacman zu verschleiern und ihn zu fangen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top