Lancer de sorts - Comment optimiser les dégâts par seconde

23

Imaginez que nous ayons un sorcier qui connaît quelques sorts. Chaque sort a 3 attributs: Dégâts, temps de refroidissement et temps d'incantation. Trucs RPG assez standard.

Temps de recharge: le temps (t) qu'il faut avant de pouvoir lancer à nouveau ce sort. Un sort est "cooldown" au moment où il commence à être lancé.

Temps d'incantation: le temps (t) nécessaire pour utiliser un sort. Pendant que l'assistant lance quelque chose, un autre sort ne peut pas être lancé et il ne peut pas être annulé.

La question est la suivante: comment maximiser les dégâts compte tenu des différents ensembles de sorts?

Il est facile de calculer les dégâts les plus élevés par temps d'incantation. Mais qu'en est-il dans les situations où il vaut mieux attendre puis se retrouver "bloqué" en lançant un sort de dégâts faibles quand un sort beaucoup plus élevé est disponible?

Par exemple,

  1. Boule de feu: 3000 points de dégâts, 3 secondes d'incantation, 6 secondes de récupération.

  2. Éclair de givre: 20 points de dégâts, 4 secondes d'incantation, 4 secondes de refroidissement.

  3. Fireblast: 3 dégâts, 3 secondes d'incantation, 3 secondes de refroidissement.

Dans ce cas, vos dégâts par seconde sont plus élevés si vous choisissez d'opter pour le sort DPCT inférieur (explosion de feu) au lieu de l'éclair de givre. Nous devons donc considérer les conséquences du choix d'un sort. texte alternatif

Dans l'exemple suivant, il y a des cas de «sur-diffusion» et «d'attente». texte alternatif

aaronfarr
la source
Pourquoi devrais-je faire 1-3-1 dans cette situation? Pourquoi pas 1-2-1? Pourquoi pas 1-2-3-1, qui est plus efficace que 1-3-1-X si 1-3-1 seul ne tue pas la cible?
@Joe Wreschnig: Merci de l'avoir signalé. C'était une erreur dans mon exemple. Simplifié maintenant à seulement 2 cas.
aaronfarr
1
Gourmand, comme dans le choix du sort dps disponible le plus élevé possible. Ignorer toute autre logique, c'est-à-dire attendre.
aaronfarr
1
Juste pour brouiller l'eau. Prenons un sort qui inflige ∞ dégâts, mais met 50 secondes à être lancé. Son dps / dpct est ∞, mais il ne devrait jamais être choisi si la cible peut être tuée par d'autres moyens en moins de 50 secondes.
deft_code du
1
Vous devez créer un lien vers le dupe sur math.stackexchange.com/questions/10414/…
Sparr

Réponses:

23

Toute l'IA est à la recherche!

Lorsque vous entrez dans les tripes de l'IA, il est incroyable de voir à quel point il s'agit vraiment de recherche .

  • état : le temps de recharge restant de tous les sorts disponibles.
  • fitness : dommages totaux causés
  • coût : temps total pris
  • branches : tout sort connu. Si le sort est toujours dans le temps de recharge, ajoutez simplement cette valeur à son temps d'incantation.
  • objectif : santé totale de la cible. L'objectif doit être une quantité limitée de dégâts, donc dans le cas d'une cible inconnue, choisissez la santé la plus grande possible.
    Alternativement, l'objectif pourrait être de passer moins de 50 secondes et la recherche trouverait le maximum de dégâts qui pourrait être fait en 50 secondes.

Branchez ces paramètres dans une recherche de coût uniforme (UCS) et presto, plan de bataille optimal garanti. Encore mieux si vous pouvez trouver une heuristique, recherchez A * ou IDA * et vous obtiendrez la même réponse beaucoup plus rapidement.

Certains avantages supplémentaires de l'utilisation du SCU sont qu'il peut trouver un ordre de distribution optimal pour des situations beaucoup plus compliquées que celui que vous avez fourni avec seulement 3 variables. Quelques autres aspects qui pourraient facilement être ajoutés:

  • dommages au fil du temps
  • rafraîchir le sort pour réduire le temps de recharge des autres sorts
  • sort de hâte provoquant un lancement plus rapide des autres sorts.
  • Booster de dégâts causant plus de dégâts aux autres sorts.

Le SCU n'est pas omnipotent. Il ne peut pas modéliser les avantages des sorts de protection. Pour cela, vous devrez passer à la recherche alpha-bêta ou minimax.
De plus, il ne gère pas très bien les zones affectées et les combats de groupe. Le SCU peut être modifié pour donner des solutions raisonnables dans ces situations, il n'est pas garanti de trouver la solution optimale.

deft_code
la source
2

Il s'agit d'un problème d'optimisation combinatoire spécialisé. À mesure que le nombre de sorts augmente, la difficulté de trouver la combinaison / configuration optimale de sorts augmente considérablement. Des heuristiques similaires à celles utilisées pour le problème du sac à dos seraient utiles pour résoudre ce problème.

Sparr
la source
1

Vous devez penser en termes de `` dégâts par unité de temps d'incantation '' (DPCT) - par exemple, une boule de feu avec un lancer de 3 secondes et infligeant 3000 dégâts ferait 1000 DPCT.

Si vous deviez attendre 3 secondes pour le temps de recharge avant de le lancer, cela le réduirait à 500 DPCT (3000 dégâts, divisé par 6 secondes au total, y compris l'attente)

Il vous suffit donc de déterminer le temps de dégâts par lancement de chaque sort, y compris toute attente restante pour le temps de recharge. Choisissez celui avec le DPCT le plus élevé, attendez si nécessaire, puis lancez-le. Répétez jusqu'à ce que le patron soit mort :)

bluescrn
la source
le problème est que le DPCT peut être très trompeur. Supposons par exemple que nous ajoutons 2 sorts supplémentaires au mélange Boule de feu: 3000 dégâts, 3 secondes d'incantation, 6 secondes de temps de recharge, DPCT: 1000 Sort # 2: 20 dégâts, 4 secondes d'incantation, 4 secondes de recharge, DPCT: 5 Sort # 3: 3 dégâts, 3 secondes d'incantation, 3 secondes de temps de recharge, DPCT: 1 (rappelez-vous, le temps de recharge commence au moment où le sort est lancé) Même si le sort # 3 a un DPCT inférieur, il en résultera un DPS plus élevé (1-3-1-3 .. .) que le sort n ° 2 (1-2-1-2 ...).
aaronfarr du
1

En utilisant votre exemple, vous voudriez probablement que les deux sorts soient plus efficaces, mais vous donnerait peut-être un avantage différent. Avoir un temps d'incantation court (ou aucun temps d'incantation d'ailleurs) serait très utile, donc cela peut valoir la peine d'être utilisé même s'il fait moins de dégâts et prend plus de temps à réutiliser.

Vous pouvez toujours imposer un autre élément dans l'équation. Les points de mana / magie peuvent servir à cet effet, en permettant au joueur de déterminer si l'utilisation de ces points en vaut la peine.

Dans l'ensemble, cependant, comme l'a dit bluescrn, le DPCT (ou DPS comme il est appelé dans de nombreux jeux qui sont hautement réglés et discutés par les joueurs à la recherche du meilleur mix) est vraiment l'élément principal que vous voudrez équilibrer, surtout si vous avez une sorte de arbres technologiques / compétences qui permettent à différents joueurs de progresser avec différentes compétences, mais avec la possibilité de faire des quantités similaires de dégâts à leur position donnée dans le jeu.

Jeff Gray
la source
0

Compris cet algorithme qui fonctionne bien pour mes besoins.

Les gens ont soulevé de grands points. Lui donner des paramètres de but ultimes permettrait aux algorithmes de recherche normaux de faire leur travail. c'est à dire. faire des dégâts optimaux en t secondes, faire x dommages en un temps optimal.

Mon algorithme renvoie simplement la séquence de sorts avec le DPS le plus élevé. C'est un algorithme rapide car il réduit la taille de l'ensemble que vous parcourez, ne nécessite pas de connaissance d'autres techniques d'arbre de recherche.

La première étape consiste à identifier le sort avec le plus de dégâts par temps d'incantation. Ce sort devient le sort "de base" car il garantit les dégâts les plus élevés par seconde. Ce qui signifie que vous devriez toujours lancer ce sort si les 2 conditions suivantes sont remplies: 1) Le sort de base est disponible (pas lors du temps de recharge). 2) Vous ne lancez pas de sort actuellement.

Il s'agit donc de remplir d'autres sorts pendant que le sort de base est en recharge. Entre (temps d'incantation) et (temps de recharge - temps d'incantation). Cependant, certains chevauchements peuvent se produire (la règle 2 ci-dessus est fausse).

Il s'agit alors de revenir à travers tous les sorts non-baseline pour trouver toutes les séquences de sorts qui ne violent pas les 2 règles.

Pour les sorts qui se chevauchent, vous devez les pénaliser pour les dommages potentiels que le sort de base aurait pu faire (jusqu'à ses dégâts maximum).

Prenons par exemple, 2 sorts

1: 300 dégâts, 3s de temps d'incantation, 10s de temps de recharge

2: 290 dégâts, 3s d'incantation, 3s de recharge

Les dégâts les plus importants proviennent de la séquence 1 - 2 - 2 - 2. Ce qui provoque un chevauchement de 2 secondes dans un lancer potentiel n ° 1. Cependant, cela est toujours bénéfique car si vous ne lancez pas le troisième sort (c'est-à-dire 1 - 2 - 2), vous ferez 880 dégâts avec 1 seconde à perdre. Si vous lancez le sort # 2 supplémentaire, vous ferez 1170 - 2 secondes de # 1, soit 200. Les dégâts 970 sont donc vos dégâts relatifs.

aaronfarr
la source
-2

Vous pouvez faire un simple boîtier de commutateur de style "niveau de sécurité".

C'est juste au dessus de ma tête, alors méfiez-vous des erreurs de logique au-delà du niveau de pensée de mon état de fatigue, mais j'espère que cela pourra vous aider à démarrer.

En supposant que votre temps se fait en nombres entiers de blocs -

// 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;
}

Certains appels de méthode sont inutiles en raison de la durée de votre sort, mais il y a toujours de la place pour les mises à jour de cette façon.

Edit: Je viens de réaliser que vous auriez besoin de réinitialiser le temps restant après le lancement du nouveau sort, probablement mieux pour en faire un attribut / champ de classe et le définir à partir d'un appel dans les méthodes castSpell.

kymully
la source
Je n'ai vraiment aucune idée de ce que vous essayez d'obtenir ici, mais aucun moteur de jeu moderne n'a de fonctions comme castSpell1 et castSpell2.
1
@Joe Wreschnig Je les considérais comme étant ses propres méthodes dans ses classes de jeu personnalisées, ce n'est qu'un exemple abstrait, pas détaillé.
kymully
1
Ce n'est pas ainsi que les sorts fonctionnent dans les moteurs modernes. Il existe une fonction castSpell qui prend un objet dont les champs sont lus dans un fichier. Une telle instruction de commutation serait impossible à maintenir dans n'importe quel moteur réel, et une sorte d'algorithme de planification est nécessaire.
@Joe Wreschnig Je comprends. Je donnais simplement un moyen de résoudre le problème. Cet exemple est écrit en java, non destiné à un moteur ou un framework spécifique. Mais si cela ne peut pas être mis en œuvre comme vous le dites, ma réponse est nulle.
kymully