PacMan-Charakter-KI-Vorschläge für die optimale nächste Richtung

Question

Erstens ist dies KI für PacMan und nicht für die Geister .

Ich schreibe ein Android-Live-Wallpaper, das PacMan um Ihre Icons herum spielt. Es unterstützt zwar Benutzervorschläge durch Berührungen des Bildschirms, aber der Großteil des Spiels wird von einer KI gespielt. Ich bin zu 99 % mit der Programmierung des Spiels fertig, aber die KI für PacMan selbst ist noch extrem schwach. Ich suche Hilfe bei der Entwicklung einer guten KI für die Bestimmung von PacMan's nächster Bewegungsrichtung.

Mein ursprünglicher Plan war folgender:

1. Initialisieren Sie einen Punktezähler für jede Richtung mit einem Wert von Null.

2. Beginnen Sie an der aktuellen Position und verwenden Sie ein BFS, um die vier möglichen Ausgangsrichtungen zu durchlaufen, indem Sie sie der Warteschlange hinzufügen.

3. Nehmen Sie ein Element aus der Warteschlange, stellen Sie sicher, dass es nicht bereits "gesehen" wurde, stellen Sie sicher, dass es sich um eine gültige Brettposition handelt, und fügen Sie der entsprechenden anfänglichen Richtungsbewertung einen Wert für die aktuelle Zelle hinzu, der darauf basiert:

   1. Hat einen Punkt: plus 10
   2. Hat eine Steigerung der Leistung: plus 50
   3. Hat eine Frucht: plus Fruchtwert (variiert je nach Stufe)
   4. Hat einen Geist, der sich auf PacMan zubewegt: 200 abziehen
   5. Hat einen Geist, der sich von PacMan entfernt: nichts tun
   6. Hat einen senkrecht laufenden Geist: 50 % abziehen
   7. Multiplizieren Sie den Wert der Zelle mit einem Prozentsatz, der von der Anzahl der Schritte bis zur Zelle abhängt. Je mehr Schritte von der Ausgangsrichtung entfernt sind, desto näher liegt der Wert der Zelle bei Null.

   und reihen Sie die drei möglichen Richtungen von der aktuellen Zelle aus ein.

4. Sobald die Warteschlange leer ist, suchen Sie die höchste Punktzahl für jede der vier möglichen Ausgangsrichtungen und wählen diese aus.

Auf dem Papier hörte sich das für mich gut an, aber die Geister umgeben PacMan extrem schnell und er zuckt in denselben zwei oder drei Zellen hin und her, bis ihn einer erreicht. Auch das Anpassen der Werte für die Geisterpräsenz hilft nicht. Mein nächster Punkt BFS schafft es zumindest auf Level 2 oder 3, bevor das Spiel endet.

Ich bin auf der Suche nach Code, Gedanken und/oder Links zu Ressourcen für die Entwicklung einer richtigen KI - vorzugsweise die ersten beiden. Ich möchte das Projekt an diesem Wochenende auf den Markt bringen, also bin ich etwas in Eile. Jede Hilfe ist sehr willkommen.

---

Zu Ihrer Information: Dieser Beitrag wurde manuell auf GameDev.StackExchange

Answer 1

Wenn PacMan in einer Position stecken bleibt und anfängt, hin und her zu zucken, dann deutet das darauf hin, dass die verschiedenen Züge, die ihm offen stehen, sehr ähnliche Werte haben, nachdem du deine Metrik ausgeführt hast. Dann führen kleine Positionsänderungen der Geister dazu, dass der beste Zug hin und her springt. Sie sollten vielleicht in Erwägung ziehen, einige Hysterese um dies zu verhindern.

Einrichten: Wähle einen zufälligen Zug und notiere ihn mit dem Wert 0.

Für jeden Schritt:

1. Führen Sie die Wertungsfunktion über die verfügbaren Züge aus.
2. Wenn die höchste Punktzahl um x% höher ist als die Rekordpunktzahl, dann wird die Rekordpunktzahl überschrieben und mit der neuen Punktzahl fortgesetzt.
3. Wenden Sie die Bewegung an.

Dies hat zur Folge, dass PacMan nicht mehr bei jedem Schritt den "besten" Zug auswählt, aber es scheint, dass eine gierige lokale Suche ohnehin nicht optimal wäre. Dadurch wird PacMan konsistenter und die Zuckungen hören auf.

Answer 2

Sie haben eine Möglichkeit, PacMan in einen "Pfadfolgemodus" zu versetzen. Der Plan ist, dass du bestimmte Umstände erkennst, einen vorgezeichneten Pfad berechnest, dem PacMan folgen soll, und dann Bedingungen für ein frühzeitiges Verlassen dieses Pfades ausarbeitest. Sie können dies für verschiedene Umstände verwenden.

Wenn PacMan in drei der vier Richtungen innerhalb eines bestimmten Abstands von Geistern umzingelt ist, dann erstelle einen Fluchtweg, der PacMan entweder von den Geistern weg oder zu einem Power-Up führt. Die Ausgangssituation wäre dann gegeben, wenn er das Power Up isst oder nicht mehr umzingelt ist.

Wenn PacMan ein Power-Up isst, baue einen Pfad, um einige Geister in der Nähe zu essen. Die Ausgangssituation wäre, wenn sich keine Geister auf dem Pfad befinden, dann berechne den Pfad neu. Oder, wenn keine Geister in der Nähe sind, beenden Sie den Modus ganz.

Wenn weniger als die Hälfte der Punkte übrig ist oder keine Punkte mehr in der Nähe sind, musst du einen Pfad betreten, um einige Punkte zu essen, und dich dabei von den Geistern fernhalten. Berechne den Pfad neu, wenn ein Geist in der Nähe ist, oder verlasse ihn ganz, wenn mehrere Geister in der Nähe sind.

Wenn es keine Situationen gibt, die einen Pfad rechtfertigen, können Sie zu der Standard-KI zurückkehren, die Sie zuvor programmiert haben.

Answer 3

Sie können verwenden Ameisenkolonie-Optimierung Techniken, um den kürzesten sichtbaren Weg zu finden, der zu vielen zu essenden Symbolen führt oder viele Punkte bringen kann.

Answer 4

Ich weiß nicht viel über künstliche Intelligenz oder spezielle Algorithmen, aber hier sind einige Dinge, die Sie ausprobieren könnten und die Ihnen vielleicht für die Arbeit in der Regierung genügen :)

Was das Problem mit den Geistern angeht, die ihn schnell umzingeln, ist die Geister-KI vielleicht zu stark? Ich weiß, dass es im klassischen Pacman angeblich spezifische Verhaltensweisen für jeden Geist gibt, wenn du das also nicht eingebaut hast, solltest du das vielleicht tun.

Um das Backtracking zu unterbinden, könnte man einen Gewichtsabzug für kürzlich durchquerte Knotenpunkte einführen, so dass er weniger geneigt ist, zu früheren Pfaden zurückzukehren. Wenn das nicht ausreicht, um ihn in die eine oder andere Richtung zu lenken, kann man den Attraktivitätsabzug logarithmisch erhöhen, so dass der eine Weg sehr schnell deutlich attraktiver wird als der andere.

Für das Problem, dass er von Geistern gefangen wird, könnte man von einem allgemeinen zielbasierten Algorithmus zu einem Ausweichalgorithmus wechseln, sobald die Geister eine gefährliche Knotennähe erreicht haben.

Answer 5

Es wäre von Vorteil, wenn Sie wüssten, wie die Bots "denken" (wie in diesem ausgezeichneten Artikel erklärt Dossier ). Wenn Sie z. B. das Verfolgungs-/Streumuster der Geister kennen, können Sie die Punkte an "gefährlichen" Stellen platzieren und so weiter.

Ich füge diese Antwort hinzu, wohl wissend, dass es nicht die beste Lösung ist, nach der Sie gesucht haben (da Sie nächste Woche liefern wollten ), aber vielleicht ist sie für jemanden, der dies in Zukunft liest, von Nutzen. Quasi eine Zeitkapsel :)