Zauberspruch - So optimieren Sie den Schaden pro Sekunde

23

Stellen Sie sich vor, wir haben einen Zauberer, der einige Zaubersprüche kennt. Jeder Zauber hat 3 Attribute: Schaden, Abkühlzeit und eine Zauberzeit. Ziemlich normales Rollenspielzeug.

Abklingzeit: Die Zeit (t), die benötigt wird, um den Zauber erneut wirken zu können. Ein Zauberspruch "kühlt ab", sobald er wirkt.

Zauberzeit: Die Zeit (t), die benötigt wird, um einen Zauber anzuwenden. Während der Zauberer etwas ausführt, kann ein anderer Zauber nicht ausgeführt und nicht abgebrochen werden.

Die Frage ist: Wie würden Sie den Schaden bei unterschiedlichen Zaubersätzen maximieren?

Es ist einfach, den höchsten Schaden pro Zauberzeit zu berechnen. Aber was ist mit Situationen, in denen es besser ist, zu warten, als festzusitzen und einen Zauber mit geringem Schaden zu wirken, wenn ein viel höherer verfügbar ist?

Beispielsweise,

  1. Feuerball: 3000 Schaden, 3 Sekunden Zauberzeit, 6 Sekunden Abkühlung.

  2. Frostblitz: 20 Schaden, 4 Sekunden Zauberzeit, 4 Sekunden Abkühlung.

  3. Feuerschlag: 3 Schaden, 3 Sekunden Zauberzeit, 3 Sekunden Abkühlung.

In diesem Fall ist Ihr Schaden pro Sekunde höher, wenn Sie sich für den niedrigeren DPCT-Zauber (Feuerschlag) anstelle des Frostblitzes entschieden haben. Wir müssen also die Konsequenzen der Wahl eines Zaubers berücksichtigen. Alt-Text

Im folgenden Beispiel handelt es sich um Fälle von "Overcasting" und "Warten". Alt-Text

Aaronfarr
quelle
Warum sollte ich in dieser Situation 1-3-1 machen? Warum nicht 1-2-1? Warum nicht 1-2-3-1, was effizienter ist als 1-3-1-X, wenn 1-3-1 allein das Ziel nicht tötet?
@ Joe Wreschnig: Danke für den Hinweis. War ein Fehler in meinem Beispiel. Vereinfacht jetzt auf nur 2 Fälle.
Aaronfarr
1
Gierig, wie bei der Auswahl des höchstmöglichen verfügbaren DPS-Zaubers, wann immer dies möglich ist. Missachtung anderer Logik dh. warten.
Aaronfarr
1
Nur um das Wasser zu trüben. Betrachte einen Zauberspruch, der, Schaden verursacht, aber 50 Sekunden benötigt, um gewirkt zu werden. Es ist dps / dpct ∞, aber es sollte niemals ausgewählt werden, wenn das Ziel mit anderen Mitteln in weniger als 50 Sekunden getötet werden kann.
deft_code 15.11.10
1
Sie sollten einen Link zum Betrüger unter math.stackexchange.com/questions/10414/…
Sparr

Antworten:

23

Alle KI ist Suche!

Wenn Sie in die Eingeweide der KI geraten, ist es erstaunlich, wie viel davon wirklich Suche ist .

  • Zustand : Die verbleibende Abklingzeit aller verfügbaren Zauber.
  • Fitness : Totalschaden angerichtet
  • Kosten : Gesamtzeit
  • Äste : jeder bekannte Zauber. Wenn sich der Zauber noch in der Abklingzeit befindet, addiere diesen Wert zu seiner Zauberzeit.
  • Ziel : Gesamtgesundheit des Ziels. Das Ziel muss eine begrenzte Menge an Schaden sein, also wähle im Falle eines unbekannten Ziels die größtmögliche Gesundheit.
    Alternativ könnte das Ziel weniger als 50 Sekunden dauern und die Suche würde den maximalen Schaden ermitteln, der in 50 Sekunden verursacht werden könnte.

Stecken Sie diese Parameter in eine Uniform Cost Search (UCS) und stellen Sie sicher, dass Sie einen optimalen Kampfplan haben. Noch besser, wenn Sie eine Heuristik erstellen, mit A * oder IDA * suchen und die gleiche Antwort viel schneller erhalten.

Ein weiterer Vorteil der Verwendung von UCS besteht darin, dass eine optimale Besetzungsreihenfolge für viel kompliziertere Situationen gefunden werden kann als für Situationen, für die Sie nur drei Variablen angegeben haben. Einige andere Aspekte, die leicht hinzugefügt werden könnten:

  • Schaden im Laufe der Zeit
  • Aktualisiere den Zauber, um die Abklingzeit anderer Zauber zu verringern
  • Eilzauber, der andere Zauber schneller wirken lässt.
  • Schadensverstärker, der bewirkt, dass andere Zauber mehr Schaden verursachen.

BKS ist nicht allmächtig. Die Vorteile von Schutzzauber können nicht modelliert werden. Dafür müssen Sie auf Alpha-Beta-Suche oder Minimax upgraden.
Es kann auch nicht mit Area-of-Affects umgehen und Gruppenkämpfe sind sehr gut. UCS kann optimiert werden, um in diesen Situationen angemessene Lösungen zu bieten. Es kann nicht garantiert werden, dass die optimale Lösung gefunden wird.

deft_code
quelle
2

Dies ist ein spezialisiertes kombinatorisches Optimierungsproblem. Mit zunehmender Anzahl von Zaubersprüchen steigt die Schwierigkeit, die optimale Kombination / das optimale Muster von Zaubersprüchen zu finden, erheblich an. Heuristiken ähnlich denen, die für das Rucksackproblem verwendet werden, wären bei der Lösung dieses Problems wertvoll.

Sparr
quelle
1

Sie müssen in "Schaden pro Einheit der Zauberzeit" (DPCT) denken - zum Beispiel würde ein Feuerball mit einem 3-Sekunden-Zauber und 3000 Schaden 1000 DPCT verursachen.

Wenn Sie 3 Sekunden auf die Abklingzeit warten müssten, bevor Sie sie wirken, würde dies sie auf 500 DPCT reduzieren (3000 Schaden, geteilt durch 6 Sekunden insgesamt, einschließlich des Wartens).

Sie müssen also nur die Schadenszeit pro Zauber bestimmen, einschließlich aller verbleibenden Wartezeiten für die Abklingzeit. Wählen Sie den mit dem höchsten DPCT aus. Warten Sie, falls erforderlich, und sprechen Sie ihn dann aus. Wiederholen, bis der Chef tot ist :)

Bluescrn
quelle
Das Problem ist, dass DPCT sehr irreführend sein kann. Nehmen wir zum Beispiel an, wir fügen dem Mix zwei weitere Zauber hinzu: Feuerball: 3000 Schaden, 3 Sekunden Zauber, 6 Sekunden Abklingzeit, DPCT: 1000 Zauber # 2: 20 Schaden, 4 Sekunden Zauber, 4 Sekunden Abklingzeit, DPCT: 5 Zauber # 3: 3 Schaden, 3 Sekunden Zauberzeit, 3 Sekunden Abklingzeit, DPCT: 1 (Denken Sie daran, dass die Abklingzeit in dem Moment beginnt, in dem der Zauber gewirkt wird.) Auch wenn Zauber 3 eine niedrigere DPCT hat, führt dies zu höheren DPPS (1-3-1-3). .) als Zauber # 2 (1-2-1-2 ...).
Aaronfarr
1

Wenn Sie Ihr Beispiel verwenden, möchten Sie wahrscheinlich, dass die beiden Zaubersprüche effektiver sind, aber möglicherweise einen anderen Vorteil für Sie haben. Eine kurze Wirkzeit (oder gar keine für diese Angelegenheit) wäre sehr nützlich, daher kann es sich lohnen, sie zu verwenden, auch wenn sie weniger Schaden anrichtet und länger dauert, um sie wieder zu verwenden.

Sie können der Gleichung jederzeit ein anderes Element hinzufügen. Mana- / Magiepunkte können diesem Zweck dienen, indem der Spieler bestimmen kann, ob die Verwendung dieser Punkte den Vorteil wert ist.

Insgesamt ist das DPCT (oder DPS, wie es in vielen Spielen genannt wird, die von Spielern, die nach der besten Mischung suchen, hochgestimmt und diskutiert werden) jedoch das Hauptelement, das Sie ausgewogen haben möchten, besonders wenn Sie irgendeine Art von haben Tech / Skill-Bäume, die es verschiedenen Spielern ermöglichen, mit unterschiedlichen Fähigkeiten voranzukommen, aber die Fähigkeit haben, an ihrer gegebenen Position im Spiel ähnliche Schadensbeträge zu verursachen.

Jeff Gray
quelle
0

Hat diesen Algorithmus herausgefunden, der für meine Zwecke gut funktioniert.

Die Leute brachten einige großartige Punkte vor. Wenn Sie ihm ultimative Zielparameter geben, können normale Suchalgorithmen ihre Sache tun. dh Füge in t Sekunden optimalen Schaden zu, füge x Schaden in optimaler Zeit zu.

Mein Algorithmus gibt einfach die Folge von Zaubersprüchen mit dem höchsten Schaden pro Sekunde zurück. Es ist ein schneller Algorithmus, da er die Größe der Menge, die Sie durchlaufen, verringert und keine Kenntnisse anderer Suchbaumtechniken erfordert.

Der erste Schritt besteht darin, den Zauber mit dem höchsten Schaden pro Zauberzeit zu identifizieren. Dieser Zauber wird zum "Grundzauber", da er den höchsten Schaden pro Sekunde garantiert. Das heißt, du solltest diesen Zauber immer wirken, wenn die folgenden 2 Bedingungen erfüllt sind: 1) Der Grundzauber ist verfügbar (nicht bei Abklingzeit). 2) Sie wirken derzeit keinen Zauber.

Es geht also darum, andere Zauber auszufüllen, während der Grundzauber abklingt. Zwischen (Wirkzeit) und (Abklingzeit - Wirkzeit). Es kann jedoch zu Überlappungen kommen (Regel 2 oben ist falsch).

Es wird dann eine Sache der Rekursion durch alle Nicht-Grundlinien-Zauber, um alle Folgen von Zaubersprüchen zu finden, die nicht gegen die 2 Regeln verstoßen.

Für Zaubersprüche, die sich DO überlappen, müssen Sie sie für potenziellen Schaden bestrafen, den der Grundzauber angerichtet haben könnte (bis zu seinem maximalen Schaden).

Nehmen Sie zum Beispiel 2 Zauber

1: 300 Schaden, 3 Sekunden Zauberzeit, 10 Sekunden Abklingzeit

2: 290 Schaden, 3s Zauberzeit, 3s Abklingzeit

Der größte Schaden entsteht durch die Sequenz 1 - 2 - 2 - 2. Dies führt zu einer Überlappung von 2 Sekunden in einem potenziellen # 1-Zauber. Dies ist jedoch immer noch von Vorteil, da Sie, wenn Sie den dritten Zauberspruch (dh 1 - 2 - 2) nicht wirken, 880 Schaden mit 1 Sekunde Zeit sparen. Wenn du den zusätzlichen Zauberspruch Nr. 2 wirkst, erhältst du 1170 - 2 Sekunden von Nr. 1, also 200. 970 Schaden ist dein relativer Schaden.

Aaronfarr
quelle
-2

Sie könnten einen einfachen Schalterkasten mit "Sicherheitsstufe" erstellen.

Das ist einfach unglaublich, also hüte dich vor Logikfehlern jenseits der Gedankenebene meines müden Zustands, aber ich hoffe, das kann dir den Einstieg erleichtern.

Angenommen, Ihre Zeit wird in Ganzzahlen angegeben -

// after casting spell
int remainingTime = (coolDown - castTime);
switch(spellJustCast)
{
  // assuming the cast method will have some input validation for whether the spell
  // is off cooldown or not, pass the time as a parameter
  case 3 : castSpell1(remainingTime);
           castSpell2(remainingTime);
           break;
  case 1 : castSpell2(remainingTime);
           castSpell3(remainingTime);
           break;
  case 2 : castSpell1(remainingTime);
           castSpell3(remainingTime);
           break;
  default: System.out.println("Debug!");
           break;
}

Einige der Methodenaufrufe sind aufgrund Ihrer Zauberzeiten nicht erforderlich, aber auf diese Weise ist immer Platz für Aktualisierungen.

Bearbeiten: Ich habe gerade festgestellt, dass Sie die verbleibende Zeit nach dem Wirken des neuen Zaubers zurücksetzen müssen, wahrscheinlich am besten, um ihn zu einem Klassenattribut / -feld zu machen und ihn über einen Aufruf innerhalb der castSpell-Methoden festzulegen.

kymully
quelle
Ich habe wirklich keine Ahnung, worauf Sie hier abzielen, aber keine moderne Spiel-Engine verfügt über Funktionen wie castSpell1 und castSpell2.
1
@ Joe Wreschnig Ich meinte, sie seien seine eigenen Methoden in seinen benutzerdefinierten Spielklassen. Dies ist nur ein abstraktes Beispiel, kein detailliertes.
kymully
1
Richtig, so funktionieren Zauber in modernen Motoren nicht. Es gibt eine castSpell-Funktion, die ein Objekt übernimmt, dessen Felder aus einer Datei gelesen werden. Eine solche switch-Anweisung kann in keiner realen Engine aufrechterhalten werden, und es ist eine Art Planungsalgorithmus erforderlich.
@ Joe Wreschnig Ich verstehe. Ich gab nur einen Weg, um das Problem zu lösen. Dieses Beispiel ist in Java geschrieben und nicht für eine Engine oder ein bestimmtes Framework vorgesehen. Aber wenn es nicht implementiert werden kann, wie Sie sagen, ist meine Antwort nichtig.
Kymully