spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Tach Leutz,

ich mach es mal kurz: In meinem Top-Down-Shooter laufen eben die Gegner rum. Wie sollen die sich bewegen? Das meine ich mit KI. Also es gibt dich, die Spielfigur, die wird von Monstern gejagt. Wie sollen sich die Monster bewegen? Also was muss ich programmieren? Die billigste Variante eines solchen Chase-Algorithmus ist über Koordinaten-Differenzen rauszufinden, wohin ein Monster laufen muss, um dich zu berühren. Dann bist du tot. Soviel zu dem zugegeben nicht unbedingt orginellen Spielverlauf. Aber es beginnt ja erst. Die Zweit-Billigste Variante, aber die ist schon deutlich teurer, besteht im Flocking. Was das ist, steht in Wikipedia. Sorry, aber da ist das ganz gut erklärt. Um das zu erklären, bin ich nicht hier. Jetzt meine Frage: Gibt es noch andere Möglichkeiten der KI? Mein Ansatz zur Zeit ist die Differenz-Methode, mit der Randbedingung, dass die Position eines Monsters nur dann neu gesetzt werden darf, wenn die neue Position mindestens sagen wir mal 32 Pixel in x- und y-Richtung von allen anderen Monstern entfernt ist. Also die Monster dürfen sich nicht durchdringen. Das ist ja eine Forderung des Flocking. Das ist ja auch realistisch. Habt ihr euch das mal überlegt, wie man das machen könnte?

Zitat von »marcgfx«

Es wäre noch hilfreich zu wissen, weshalb du nicht mit deiner Lösung zufrieden bist. Es gibt unendlich viele Möglichkeiten für KI, die Frage ist was für ein Verhalten willst du erzeugen. Es ist etwas mit dem ich mich selbst grad viel beschäftige, aber soll ich dir jetzt einfach all meine Ideen aufzählen?? Ich weiss gar nichts über deine Monster. Haben sie irgendwelche Fähigkeiten, können sie z.b. schiessen?

Die Monster können noch nicht schiessen. Das kann ich natürlich einbauen, allerdings ändert sich dann das Gameplay erheblich. Bisher ist das ganze ein N-Wege scrollender Top-Down-Shooter. Die Spielfigur bewegt sich in 8 Richtungen immer in der Mitte der Kamera, schiessen kommt als nächstes. Randabfragen und Kollionserkennung über Bounding Box ist drin. Jetzt ist es an der Zeit die Monster laufen zu lassen. Dann kommt das Schießen des Players. Schließlich noch Items sammeln wie Leben, Munition etc., Scoreanzeige, Level-Verwaltung, State Machine, Highscoreanzeige. Das sind aber Kleinigkeiten. Zum Schluss wirds noch mal richtig heftig bei der Netzwerkfähigkeit. Da muss ich mal sehen, wann ich das schaffe. Das alles habe ich schon mal in AS3 und auch in JS gemacht, dieses Mal in C++. Die Grafik ist im Grunde erstmal egal, wie Spielfigur und Monster aussehen auch. Ich habe erst mal Grafiken aus anderen Spielen genommen. Es soll ja nicht veröffentlich werden. Die Grafiken sind ja schnell ausgetauscht, man muss halt welche haben

Also jetzt die KI. Bisher hatte ich immer das Flocking eingebaut, was aber ziemlich viel Fummelei ist. Außerdem wird da viel mit Arcustangens rum gerechnet, was viel CPU-Zeit kostet, deswegen jetzt die billige Variante über Koordinaten-Differenzen, da reicht addieren und subtrahieren. Es geht ja darum, die neue Position eines Monsters für den nächsten Frame zu berechnen. Die Monster sollen natürlich den Player killen durch Berührung. Das ist das Ziel. Es ist eine Hatz bzw. Ballerei auf freiem Feld, also Open World Es gibt zwar Bäume und Häuser, durch die man nicht durchlaufen kann, aber es ist eben kein Pacman mit engen Gassen, obwohl man das natürlich auch machen kann. Enge Gassen sind einfacher, weil es meistens weniger als 4 mögliche Richtungen gibt, bei mir sind es immer 8.

Bei der Differenz-KI erfolgt die Änderung der Monsterrichtung schlagartig, wo hingegen beim Flocking mehr oder weniger enge Kurve gelaufen werden. Das sieht schöner aus. Damit könnte ich aber leben, also wenn die Monster ruckartig die Richtung wechseln. Das ganze läuft schon, nur laufen die Monster nach einiger Zeit alle auf den gleichen Koordinaten, so dass man nur noch eines sieht. Das wird ja beim Flocking verhindert, in dem ein Mindestabstand zwischen den Monstern eingehalten wird.

Das Ganze sollte möglichst effizient werden, weil schlußendlich massenhaft Monster rumlaufen sollen, damit möglichst viel Action entsteht. Es kommen dann noch schicke Explosionen dazu, so viel Animationen wie möglich, wie ein richtig geiler Automaten-Shooter aus den 90ern. So soll es mal werden.

Ganz schlecht in diesem Sinne wäre ein A*, also eine echte Pathfindung. Genau wie beim Flocking gibts da praktisch für jede Sprache eine fertige Bibliothek zum Dazulinken, so dass sich der Aufwand in Grenzen hält. Allerdings dürfte Pathfindung am teuersten sein. Das Spiel soll mit 60 fps laufen, das ist auch schon ziemlich teuer, aber weniger sieht schlecht aus. Wenn es ohne Pathfindung geht, dann passiert es, dass die Monster ständig gegen eine Wand laufen, weil sie wissen, dass sich dahinter der Player befindet, aber nicht durchkommen. Mit Pathfindung würden sie halt das Hindernis umgehen können. Das ist schon deutlich schlauer, aber eben teuer.

Mehr ist mir bis jetzt nicht eingefallen, wie die Monster sich noch bewegen könnten. Deswegen meine Frage, obs noch andere Ideen gibt.

Vielleicht baue ich auch alle 3 Methoden ein zum Umschalten, damit man genau sehen kann, wie sich das Spiel ändert.

Das Schießen der Monster wird dann auch noch mal was kosten, weil die nicht sinnlos in der Gegend rumballern sollen, sondern nur dann, wenn Sichtkontakt zur Spielfigur besteht. Dann sollen sie direkt draufhalten, wodurch das Spiel sehr schwer werden kann. Über das Balancing habe ich mir noch keine Gedanken gemacht, erst müssen noch ein paar andere Dinge laufen, wie die KI eben.

Das ganze ist mit SDL 1.2 gemacht, das müsste ich irgendwann mal umstellen auf 2.1, also alles Multiplattform. Level-Editor ist der Tiled, der ist ja auch Multiplattform. Angefangen habe ich vor ca. 3 Monaten unter Linux, mache aber zur Zeit weiter mit Windows 10. Als IDE nehme ich Code::Blocks, der verwendet g++ für 32 Bit, obwohl Linux und Windows bei mir 64 Bit sind. Bisher gabs da keine Probleme. Einfach genial das Teil, auch Multiplattform und kostenlos. Zu tun gibts noch jede Menge, darüber wird wohl das Jahr hingehen, bevor alles passt.

Zitat von »CeDoMain«

Du kannst mal im Internet nach Wegfindungsalgorithmen suchen.
...

Das hat sich jetzt überschnitten, den A* hatte ich schon auf dem Schirm. Na das sind ja mal viele supergute Ideen! Ich lege mal los, mal sehen, wie weit ich komme. Üblicherweise ist irgendwann die Rechenzeit verbraucht und dann muss man sparen.

Zitat von »marcgfx«

So wie es sich anhört hast du eine ähnliche Ansicht wie ich bei meinem Spiel. Zum Thema Flocking: Das habe ich nur für "Assistenten" des Spielers eingebaut. Bei den Gegnern reicht die normale Physik völlig aus. Durch das kollidieren werden sie bereits zu einem Flocking-Verhalten gezwungen. Atan ist schon eher teuer, aber wenn du mit C++ arbeitest dürftest du weniger Probleme als ich damit haben . Ich verwende für atan2 eine Approximation die ich irgendwo in einem Forum gefunden habe. Wie viele Gegner sollen denn auf einmal überhaupt aktiv sein? Wenn es <100 sind, machst du dir definitiv schon zu viele Gedanken.

Naja so 100 animierte Objekte inklusive Geschossen und Explosionen könnten es schon werden. Nur innerhalb der Kamera, die Map ist ja viel größer. Die Monster außerhalb der Kamera muss man ja weder animieren (updaten) noch bewegen (move) oder auf Kollision testen. Also denke ich mir, jedes Monster bekommt eine Eigenschaft isVisible, die true ist, wenn das Monster im Kameraausschnitt zu sehen ist. Dazu muss man aber zu Beginn des Gameloops über alle Monster loopen und anhand der Position auf der Map dieses Flag setzen. So wird das eben doch immer mehr Rechnerei. CPU-Fresser kann ich mir unendlich viele vorstellen, zum Beispiel Lichteffekte oder Tageszeiten. Da weiss ich noch gar nicht, wie man so etwas bauen könnte. Das kommt erst später

Achso beim atan könnte man doch auch eine Tabelle benutzen, man muss wohl nur auf Division durch Null achten. Beim Sinus und Cosinus mache ich das öfter. Aber das sind ja schon Optimierungen. Erstmal ist ja noch Rechenzeit da.

Zitat von »CeDoMain«

Damit beim Map-Verschieben nicht ALLE Monster durcgegangen werden, kannst du sie in sogenannte Quadtrees (in 3D "Octree") einteilen. Damit kannst du dann beim neuberechnen eine große Menge an Monstern ausschließen. Schau einfach mal im Internet nach diesem Begriff.

Ansonsten mache ich mir auch nicht so die großen Sorgen über Performance! Auch 100 Objekte sollten kein Problem sein - ein 3D Spiel muss da ganz andere Dinge machen... Warum benötigst du für die Richtungsberechnungen überhaupt Trigonimetrie? Ich habe das alles über Vektoren lösen können, bei meinem 2D-Shooter damals im Informatikunterricht.

Ich würde schauen, dass du möglichst viele Dinge Eventgesteuert machst oder über Aufgabenlisten in jedem Monster. In der Gameloop wird dann einfach in jedem Monster geschaut, ob es was tun soll oder nicht. Dann kannst du auch sagen, dass nur alle 2 Frames die Richtung neu berechnet wird. Oder alle 1 - 5 und das per Zufall. So bekommst du auch noch mehr Dynamik ins Spiel.

Die Winkelfunktionen brauche ich beim Flocking. @Schorsch. Mit karthesischen Koordinaten komme ich da nicht hin, sondern ich muss die umrechnen in Polarkoordinaten. Dafür nehme ich eine Vector 2D-Bibliothek und da gibt es dann solche Funktionen (das ist AS3):



Weiterhin jede Menge Sinus und Cosinus und hässliche Wurzeln zur Längenberechnung nach Pythagoras. Deswegen habe ich die folgende simple Chasing-Methode programmmiert, die ist schon wesentlich weniger CPU-lastig, funktioniert auch. Über Koordinatendifferenzen wird die Richtung gefunden, in die ein Monster laufen muss, um die Spielfigur zu erwischen. Je nach Richtung wird dann monster->moveX und monster->moveY gesetzt, das sind die Inkremente, die man auf die aktuelle Monsterposition addieren muss, um zur nächsten Position zu gelangen. Ganz einfach eigentlich. Musste ich aber auch ne Zeichnung machen Außerdem wird nach eine Variable gesetzt für die Richtung, die brauche ich, damit er die richtige Animationssequenz aus dem Spritesheet holt. Es gibt 8 Richtungen mit jeweils 4 Animations-Phasen, macht 32 Frames für die Monster. Der Player braucht mehr, weil der auch schiessen kann. Alles Standard soweit.



setDir setzt eben die Richtung im Monsterobjekt, update() schaltet die Animationsphasen durch und verwaltet die benötigten Counter dafür und move() setzt dann schließlich die neue Position. getID() bedeutet: jedes Monster hat eine eindeutige ID.

Das Problem, das ich jetzt noch habe, ist, dass die Monster eben ineinander laufen. Gestern habe ichs nicht mehr geschafft, das zu lösen, ist wohl kniffliger als ich zunächst dachte.

Das wollte ich jetzt so lösen:

Schleife über alle Monster
hole ein Monster
führe für dieses Monster das chasing aus und rufe dann monster->move() auf

In move() wird wieder eine Schleife über alle Monster gelegt,
die Position wird aber nur dann tatsächlich verändert, wenn x- und y-Koordinaten aller anderen Monster mindestens 31 Pixel von der
Position des betrachteten Monsters entfernt liegen,
sonst bleibt das Monster eben stehen.
Das betrachtete Monster selbst wird von der Berechnung ausgeschlossen, dafür brauche ich die ID.

Die move-Methode sieht so aus, funktioniert aber noch nicht, die Monster eiern seltsam rum und bleiben bald stehen:



Sobald x- oder y-Differenz kleiner als 31 Pixel ist, soll er die Schleife verlassen, denn darf das Monster nicht bewegt werden wegen Durchdringung.
Da scheint ein logischer Fehler drinzuliegen.

Schließlich wird mit move2() die Position wirklich geändert.

Ich habe mal ein kleines Video angehängt, damit man das mal sieht. Am Anfang das ist die AS3-Version mit Flocking, die C++-Version sieht aber genau so aus.