spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi Leute!
Also so langsam muss ich mich für mein Projekt mal mit den PvE Quests beschäftigen, wo es darum geht, die Gegner innerhalb eines Sektors zu vernichten, bzw. zu überleben. Jetzt sollen die Gegner aber natürlich nicht willkürlich herumfliegen, sondern halbwegs intelligent angreifen (Flottenformationen oder Taktik sind dazu allerdings nicht nötig).

Folgende Randparameter habe ich dazu: Ein Kampf findet immer in einem begrenzten Sektor statt, der eine Teilmenge des 2-dimensionalen reellen Raums ist, mit x- und y-Werten zwischen 0 und 360, also
§\{(x,y)|x,y\in[0,360]\}\subset R^2§
Die Spielerschiffe starten zwar recht zentral, können aber bewegt werden. Die Piratenschiffe (beliebige Anzahl) starten an zufälligen Positionen des Sektors. Diese sollen jetzt die Spielerschiffe angreifen, am besten in Gruppen, aber nicht unbedingt an Spielerschiffen vorbeifliegen, um ein anderes anzugreifen, und so evtl kampflos abgeschossen werden...

Da dachte ich an eine etwas vereinfachte Form des Glühwürmchenalgorithmus aus der Schwarmintelligenz, der ja vom Prinzip ähnlich funktioniert. Hier nochmal eine kurze anschauliche Zusammenfassung:

Zitat

Beim Glühwürmchenalgorithmus werden die Glühwürmchen zufällig im Raum platziert. Dabei hat jedes Glühwürmchen eine bestimmte Helligkeit, die vom Ort des Würmchens abhängt. Die Helligkeit steht hier stellvertretend für einen Wert einer Optimierungsfunktion über dem Raum. In jeder Iteration wird jedes Glühwürmchen mit jedem anderen verglichen und das dunklere der beiden bewegt sich einen Schritt auf das hellere zu (sprich, das Würmchen, das den schlechteren Wert hat, nähert sich dem mit dem besseren Wert an), plus einer Zufallskomponente in der Bewegung. Auf diese Weise bilden sich nach mehreren Durchläufen kleine Grüppchen um die lokalen Maxima der Optimierungsfunktion, und im Idealfall irgendwann eine große Gruppe am globalen Maximum. Bis auf die Optimierungsfunktion (sprich, welchen (Helligkeits-)Wert sie an welcher Stelle des Raums haben), haben die Glühwürmchen also keine globalen Informationen, sondern arbeiten nur mit Vergleichswerten untereinander -> Schwarmintelligenz

Wenn ich so ansetze, dass ich die Piratenschiffe als die Glühwürmchen nehme und die Spielerschiffe als lokale Maxima betrachte, sollten die Piratenschiffe Grüppchen in der Nähe der Spielerschiffe bilden. In dem Moment, wo ein Schiff ein lokales Maximum erreicht hat, also in einen Kampf verwickelt ist, würde ich es aus der Schleife rausnehmen und sich nicht mehr weiter bewegen lassen, bis das Ziel (und damit das Maxium) vernichtet wurde. Auf diese Weise müsste ich erreichen, dass die Schiffe immer zu den Spielern fliegen und wenn sie eines vernichtet haben, weiter zum nächstbesten (also dem Punkt, wo das nächsthellste Glühwürmchen ist) fliegen.

So weit die Theorie. Dazu ergeben sich ein paar Fragen:
1. Was haltet ihr von der Idee, ist diese tauglich? Ich brauche wie gesagt keine Taktiken/Schlachtpläne/Formationen, sondern lediglich ein halbwegs sinnvolles/intelligentes Verhalten der Einzelschiffe
2. Welche Lücken könnten entstehen, die zu dummem Verhalten führen?
3. Wie baue ich die Optimierungsfunktion auf? Angenommen, die Funktion hat im Raum überall den Wert 0 und bei den Spielerschiffen z.B. 1 oder ein Wert, der von der Stärke des Schiffes abhängt. Wie kann ich da am Besten eine glatte (wobei stetig eigtl auch reicht) Funktion aufstellen, die diese lokalen Maxima hat und um diese Maxima herum ein Gefälle in alle Richtungen hat, und welchen Radius für das Gefälle nehm ich da wohl am sinnvollsten? Ich brauche ja ein Gefälle, damit die Glühwürmchen unterschiedlich hell sind, das wäre ja sonst nur gegeben, wenn sie sich direkt auf dem gegnerischen Schiff befinden...
4. Wie kann ich den Aufbau dieser Funktion so gestalten, dass er bei jedem Durchlauf des Algorithmus recheneffizient durchgeführt werden kann?

Any Comments? Frei zum Philosophieren

Also nochmal zu den Randparametern:
Es werden so 3-5 Spielerschiffe sein und maximal 20 Piratenschiffe. Klar ist der Algorithmus quadratisch in der Laufzeit, aber da die Schiffe ja gerade mal 25 sind und dann ja auch immer weniger werden, sollte das doch eigtl. möglich sein. Zumal der Algorithmus ja nur ein paar wenige Berechnungen macht (Abstände, Anziehungskraft, Repositionierung). Und er muss ja nicht in jedem Frame aufgerufen werden, das reicht ja auch z.B. 1x die Sekunde, wenn man den Sektor z.B. rastert, sprich auf ganze Zahlen reduziert. Das dürfte bei der Größe der Schiffe bei weitem präzise genug sein.