Wie implementiere ich einen intelligenten Feind in einem Shoot-Em-Up?

13

Stellen Sie sich ein sehr einfaches Shoot-em-up vor, etwas, das wir alle kennen:

Schießerei 1

Du bist der Spieler (grün). Ihre Bewegung ist auf die XAchse beschränkt. Unser Feind (oder Feinde) befindet sich oben auf dem Bildschirm, seine Bewegung ist auch auf die XAchse beschränkt. Der Spieler schießt mit Kugeln (gelb) auf den Feind.

Ich möchte eine KI für den Feind implementieren, die wirklich gut darin ist, den Kugeln des Spielers auszuweichen. Meine erste Idee war, den Bildschirm in einzelne Abschnitte zu unterteilen und diesen Gewichte zuzuweisen:

gewichteter Shoot-Em-Up

Es gibt zwei Gewichte: Das "Kugelgewicht" (grau) ist die von einer Kugel ausgehende Gefahr. Je näher die Kugel dem Feind ist, desto höher ist das "Kugelgewicht" ( 0..1wobei 1 die höchste Gefahr darstellt). Fahrspuren ohne Kugel haben ein Gewicht von 0. Das zweite Gewicht ist das "Distanzgewicht" (lindgrün). Für jede Spur addiere ich die 0.2Bewegungskosten (dieser Wert ist jetzt ein bisschen willkürlich und könnte angepasst werden).

Dann addiere ich einfach die Gewichte (weiß) und gehe auf die Spur mit dem niedrigsten Gewicht (rot). Dieser Ansatz weist jedoch einen offensichtlichen Fehler auf, da lokale Minima leicht übersehen werden können, da der optimale Ort einfach zwischen zwei ankommenden Kugeln liegt (wie durch den weißen Pfeil angegeben).

Also hier ist was ich suche:

Totale Zerstörung

  • Sollte einen Weg durch den Kugelsturm finden, auch wenn es keinen Ort gibt, an dem keine Kugel droht.
  • Der Feind kann Kugeln zuverlässig ausweichen, indem er eine optimale (oder nahezu optimale) Lösung auswählt.
  • Der Algorithmus sollte in der Lage sein, die Geschossbewegungsgeschwindigkeit zu berücksichtigen (da sie sich möglicherweise mit unterschiedlichen Geschwindigkeiten bewegen).
  • Möglichkeiten, den Algorithmus so zu optimieren, dass verschiedene Schwierigkeitsgrade angewendet werden können (dumm für superintelligente Feinde).
  • Algorithmus sollte verschiedene Ziele ermöglichen, da der Feind nicht nur Kugeln ausweichen will, er sollte auch in der Lage sein, den Spieler zu schießen. Das bedeutet, dass Positionen, an denen der Feind auf den Spieler schießen kann, bevorzugt werden sollten, wenn er Kugeln ausweicht.

Wie würden Sie das angehen? Im Gegensatz zu anderen Spielen dieses Genres möchte ich nur wenige, aber sehr "geschickte" Feinde haben, anstatt eine Menge dummer Feinde.

Blödmann
quelle
2
Haben Sie darüber nachgedacht, so etwas wie Lenkverhalten zu verwenden? Es gibt eine speziell für die Vermeidung von Hindernissen: red3d.com/cwr/steer/Obstacle.html
Tetrad
@Tetrad Ich habe über Lenkverhalten nachgedacht .. auch, weil sie sich gut umschalten lassen, wie "versuchen, Spieler abzuschießen" und wenn Gefahr droht, auf "Ausweichen" umschalten. Ich befürchte, dass eine 1D-Version von Evade (das ist es, womit ich mich im Grunde befasse) viel zu dumm ist, um gute Entscheidungen zu treffen. Ich könnte mich jedoch irren.
Bummzack

Antworten:

8

Ich denke, Ihre Grundidee ist Ton, aber es ist nicht analog. Sie benötigen ein analoges Wertefeld, das über den Bildschirm läuft. 1D-Diffusionsgradient, aus dem Sie im Handumdrehen einen Wert an einem genauen Punkt auf dieser Linie ableiten können. Diffusionsgradienten sind billig und können von mehreren Feinden gleichzeitig verwendet werden, da sie die Umgebung beschreiben und nicht die Sichtweise der Entität (ein bisschen wie Radiosity Lighting) - wahrscheinlich, warum Sie sich für den Ansatz entschieden haben, den Sie in Ihrer Frage haben . Dieser Gradient sollte relativ gleichmäßig sein, um eine organische Bewegung des Feindes hervorzurufen. Er wird offensichtlich aktualisiert, wie es Ihr Gamestate tut. Vielleicht gleitender Durchschnitt ?

Der Gradient sollte kombinieren:

  • Nähe
  • Geschwindigkeit
  • Breite der Kugel
  • (optional) Position der Ziele (Spieler)

Zum Ausweichen müssen wir in der Lage sein, eine Lösung genau zu finden, wenn eine Lösung existiert . Dies ist der Fall, wenn eine Lücke vorhanden ist, durch die der Feind ausweichen kann. Das heißt, Sie können nur das tun, was Sie können, sodass der Gradientenansatz nicht schlechter funktioniert als jeder andere Ansatz in diesem Sinne, würde ich sagen.

Der Diffusionsgradient sollte den Feind in Richtung lokaler Optima (die Spitzen in der Grafik) drängen, wobei es weniger wichtig ist, sich zu bewegen, je näher wir einem lokalen Minimum kommen. Dies öffnet die Tür für intelligentere Entscheidungen darüber, wann der Feind eine gute Schussöffnung hat.

Wenn der Feuerbedarf größer ist als der Bewegungsbedarf, dann tun Sie dies. Ihr Code kann dies auch dadurch bestimmen, wie sehr sie sich unterscheiden. Sie können dies als Teil des Basisgraphen implementieren. In diesem Fall reduziert die Position des Spielers die Umgebungswerte im Graphen (vorausgesetzt, die Gegner ziehen sich zum niedrigsten Punkt zurück), wodurch alle Entscheidungen in einem Graphen zusammengefasst werden. Wunsch zu feuern "Grafik getrennt von der Haupt" Wunsch, auszuweichen "Grafik, die Ihnen mehr direkte Kontrolle bieten wird.

IRL, ich würde mir nicht die Mühe machen, einem Projektil auszuweichen, bis es sich in einer Entfernung befindet, von der ich weiß, dass es bei meiner höchsten Ausweichgeschwindigkeit immer schwieriger wird, sie zu umgehen. Erfahrung aus erster Hand beim Werfen von Steinen als Junge. Eine Kugel in x-Entfernung, die sich mit der Geschwindigkeit y bewegt, hat die gleiche Gefahrenbewertung wie eine Kugel in 2x-Entfernung, die sich mit 2y bewegt. Dies muss also korrekt berücksichtigt werden.

Möglichkeiten zur Optimierung des Algorithmus für den Feind gehören

  • Einführung einer Latenz bei Aktualisierungen des Diagramms (Born Too Slow)
  • Einfügen zufälliger, lokalisierter Ungenauigkeiten in das Diagramm
  • Aufgrund der Faulheit der KI müssen sich Gegner einfach nicht an die Anweisungen des Diagramms halten, und zwar über eine Reihe von Aktualisierungen (z. B. 1 bis 10 Frames).

Auch hier können Sie entweder alle Faktoren in ein Diagramm implementieren (weniger Kontrolle und weniger nützlich für mehrere Feinde) oder in mehrere Diagramme, die Sie zusammen betrachten, um die Ergebnisse zu erhalten (modularer, funktioniert wahrscheinlich besser für mehrere Feinde). Es ist schwierig, genauer zu sein, da es viele Richtungen gibt, in die Sie diesen Ansatz einschlagen können.

Ingenieur
quelle
1
Lieber Nick. Ich habe eine kleine Testversion dieses Verhaltens in Flash implementiert und bin sehr zufrieden mit dem Ergebnis (Aufzählungszeichen werden zufällig erzeugt). Derzeit verwende ich 3 Farbverläufe, einen für Bedrohung, Bewegungskosten und einen statischen für die Ränder (damit Ränder des Bildschirms weniger wünschenswert sind). Sie werden in der Flash-Anwendung visualisiert. Ich habe das Gefühl, dass ich mit einigen Optimierungen sehr gute Ergebnisse erzielen und auch andere Gewichte wie Schießpositionen berücksichtigen kann. Vielen Dank Kumpel.
Bummzack
1
Hey @bummzack, es ist ein Vergnügungskamerad, das ist eine coole kleine Demo! Ihre Sicht auf das Problem war für mich neu und sah interessant aus - ich bin froh zu sehen, dass es funktioniert! Ich helfe gerne dabei und danke fürs Teilen.
Ingenieur
7

Dies kann als Pfadproblem angesehen werden. Anstatt zu überlegen, wie der Bösewicht die Kugeln vermeidet, werden die Kugeln statisch abgebildet und der Bösewicht muss durch sie zum unteren Rand des Bildschirms wandern.

    E    
B  B**B
  B***B  B
 B***B   B
B**B** B 
 B**B**BB
B*****B B
      P

E = Feind
B = Kugel
P = Spieler
* = Pfadoptionen zum unteren Bildschirmrand

Sobald der Bösewicht einen erfolgreichen Weg eingeschlagen hat, muss er nur jedes Mal den nächsten Schritt tun. Vermutlich gibt es bereits einige gute Algorithmen, um solche Pfade zu finden. Wenn sich der Baddy mit der gleichen Geschwindigkeit wie die Kugeln bewegt, könnte ein Beispielalgorithmus sein;

Beginnen Sie am Baddy und markieren Sie sichere Positionen in leeren Räumen unten links, direkt unten und unten rechts. Betrachten Sie dann jeden sicheren Bereich, den Sie gerade erstellt haben, und wiederholen Sie ihn. Wenn Sie zu irgendeinem Zeitpunkt feststellen, dass sich keine sicheren Bereiche darunter befinden, markieren Sie den Bereich als nicht sicher und führen Sie eine Rückverfolgung durch.

Qwerky
quelle
1
Interessanter Ansatz. Ich befürchte, dass dies ein bisschen teuer ist, da sich die Umgebung so schnell ändert und es schwierig ist, gängige Algorithmen für die Wegfindung zu verwenden, da sie am besten mit diskreten "Karten" funktionieren.
Bummzack
Es sollte nicht zu teuer sein, vergessen Sie nicht, dass Sie nur die unterste Reihe pro Runde berechnen müssen, Sie müssen nicht die ganze Sache neu berechnen.
Qwerky
@bummzack Environment ist zumindest in Bezug auf den Computer nicht "schnell". Für Spieleentwickler sollte man verstehen, dass fast jedes Spiel schrittweise aufgebaut ist, es ist nur ungefähr die Größe dieses Schritts. Bei jedem Schritt können jedoch Berechnungen durchgeführt werden, sodass die Qwerky-Lösung genau das Richtige für Sie ist.
Deele
Eigentlich stimme ich @bummzack zu. Obwohl dieser Ansatz logisch solide ist, wird er teurer als der in der Frage vorgeschlagene 1D-Ansatz. Das mag eine vorzeitige Optimierung sein, aber ich finde diesen Ansatz weitaus eleganter. Siehe meine Antwort für eine Ausarbeitung dazu.
Ingenieur
2
Dies ist wahrscheinlich die richtige , aber keine realistische Antwort . In der Zeit, die der Feind benötigt, um einen Pfad zu erarbeiten, kann es vorkommen, dass auf dem Feld weitere Kugeln den Pfad vollständig ungültig machen. Eine Neuberechnung des Pfades ist daher ein Muss. Und Neuberechnung ist eine Hündin . Darüber hinaus verteuert Ihre Idee, bis zu einem Punkt zurückzukehren, an dem es sicher war, es noch mehr! @ Nick Wiggill Ich glaube nicht, dass es eine vorzeitige Optimierung ist, nur eine gute Voraussicht, um sicherzustellen, dass Sie sich nicht selbst in den Schritt treten.
Ray Dey