Lanzamiento de hechizos: cómo optimizar el daño por segundo

23

Imagina que tenemos un mago que conoce algunos hechizos. Cada hechizo tiene 3 atributos: Daño, tiempo de enfriamiento y tiempo de lanzamiento. Bastante material de rol estándar.

Tiempo de enfriamiento: la cantidad de tiempo (t) que toma antes de poder lanzar ese hechizo nuevamente. Un hechizo comienza a "enfriamiento" en el momento en que comienza a lanzar.

Tiempo de lanzamiento: la cantidad de tiempo (t) que lleva usar un hechizo. Mientras el mago está lanzando algo, no se puede lanzar otro hechizo y no se puede cancelar.

La pregunta es: ¿cómo maximizarías el daño dados diferentes conjuntos de hechizos?

Es fácil calcular el mayor daño por tiempo de lanzamiento. Pero, ¿qué pasa en situaciones en las que es mejor esperar que quedarse atascado y lanzar un hechizo de bajo daño cuando hay uno mucho más alto disponible?

Por ejemplo,

  1. Bola de fuego: 3000 de daño, 3 segundos de tiempo de lanzamiento, 6 segundos de enfriamiento.

  2. Descarga de hielo: 20 daños, 4 segundos de tiempo de lanzamiento, 4 segundos de enfriamiento.

  3. Explosión de fuego: 3 daños, 3 segundos de tiempo de lanzamiento, 3 segundos de enfriamiento.

En este caso, tu daño por segundo es mayor si eliges el hechizo DPCT más bajo (chorro de fuego) en lugar del rayo de hielo. Entonces debemos considerar las consecuencias de elegir un hechizo. texto alternativo

En el siguiente ejemplo hay casos de "sobre casting" y "espera". texto alternativo

algorithm ai optimization aaronfarr
fuente
¿Por qué haría 1-3-1 en esta situación? ¿Por qué no 1-2-1? ¿Por qué no 1-2-3-1, que es más eficiente que 1-3-1-X si 1-3-1 solo no matará al objetivo?
@ Joe Wreschnig: Gracias por señalarlo. Fue un error en mi ejemplo. Ahora lo simplifiqué a solo 2 casos.
aaronfarr
1
Codicioso, como en elegir el hechizo dps más alto disponible siempre que sea posible. Sin tener en cuenta otra lógica, es decir. esperando.
aaronfarr
1
Solo para enturbiar el agua. Considera un hechizo que hace ∞ daño, pero tarda 50 segundos en lanzarse. Su dps / dpct es ∞, pero nunca se debe elegir si el objetivo se puede matar con otros medios en menos de 50 segundos.
deft_code el
1
Debe vincular al engaño en math.stackexchange.com/questions/10414/…
Sparr

Respuestas:

23

¡Toda la IA es búsqueda!

Cuando entras en las entrañas de la IA, es sorprendente cuánto de eso realmente se busca .

  • estado : el tiempo de reutilización restante de todos los hechizos disponibles.
  • aptitud : daño total hecho
  • costo : tiempo total empleado
  • ramas : cualquier hechizo conocido. Si el hechizo aún está en tiempo de reutilización, solo agrega ese valor a su tiempo de lanzamiento.
  • objetivo : salud total del objetivo. El objetivo tiene que ser una cantidad finita de daño, por lo que en el caso de un objetivo desconocido, elige la mayor salud posible.
    Alternativamente, el objetivo podría pasar menos de 50 segundos y la búsqueda encontraría el daño máximo que podría hacerse en 50 segundos.

Conecta estos parámetros en una búsqueda uniforme de costos (UCS) y listo, plan de batalla óptimo garantizado. Aún mejor si puede encontrar una heurística, busque con A * o IDA * y obtendrá la misma respuesta mucho más rápido.

Algunas ventajas más de usar UCS es que puede encontrar un orden de conversión óptimo para situaciones mucho más complicadas que la que proporcionó con solo 3 variables. Algunos otros aspectos que podrían agregarse fácilmente:

  • daño durante tiempo transcurrido
  • actualizar hechizo para reducir el enfriamiento de otros hechizos
  • hechizo de prisa que hace que otros hechizos se lancen más rápido.
  • refuerzo de daño que hace que otros hechizos hagan más daño.

UCS no es omnipotente. No puede modelar los beneficios de los hechizos de protección. Para eso, tendrá que actualizar a la búsqueda alfa-beta o minimax.
Además, no maneja muy bien el área de afecto y las peleas grupales. UCS se puede ajustar para dar soluciones razonables en estas situaciones, no se garantiza que encuentre la solución óptima.

deft_code
fuente
2

Este es un problema especializado de optimización combinatoria. A medida que aumenta el número de hechizos, la dificultad para encontrar la combinación / patrón óptimo de hechizos aumenta significativamente. Las heurísticas similares a las utilizadas para el problema de la mochila serían valiosas para resolver este problema.

Sparr
fuente
1

Debes pensar en términos de "daño por unidad de tiempo de lanzamiento" (DPCT); por ejemplo, una bola de fuego con un lanzamiento de 3 segundos y hacer 3000 daños haría 1000 DPCT.

Si tuviera que esperar 3 segundos para el enfriamiento antes de lanzarlo, eso lo reduciría a 500 DPCT (3000 de daño, dividido por 6 segundos en total, incluida la espera)

Entonces solo necesitas determinar el daño por tiempo de lanzamiento de cada hechizo, incluyendo cualquier espera restante para el enfriamiento. Elija el que tenga el DPCT más alto, espere si es necesario y luego eche. Repita hasta que el jefe esté muerto :)

bluescrn
fuente
El problema es que DPCT puede ser muy engañoso. Digamos, por ejemplo, que agregamos 2 hechizos más a la mezcla Bola de fuego: 3000 daños, 3 segundos de lanzamiento, 6 segundos de enfriamiento, DPCT: 1000 Hechizo # 2: 20 daños, 4 segundos de lanzamiento, 4 segundos de enfriamiento, DPCT: 5 Hechizo # 3: 3 daño, 3 segundos de lanzamiento, 3 segundos de enfriamiento, DPCT: 1 (recuerde, el enfriamiento comienza en el momento en que se lanza el hechizo) Aunque el Hechizo # 3 tiene un DPCT más bajo, dará como resultado un DPS más alto (1-3-1-3 .. .) que el Hechizo # 2 (1-2-1-2 ...).
aaronfarr el
1

Usando tu ejemplo, probablemente quieras que los dos hechizos tengan una efectividad más cercana, pero posiblemente te den una ventaja diferente. Sería muy útil tener un tiempo de lanzamiento corto (o ningún tiempo de lanzamiento), por lo que puede valer la pena usarlo incluso si hace menos daño y toma más tiempo volver a usarlo.

Siempre puedes imponer otro elemento en la ecuación. Los puntos de maná / magia pueden servir para este propósito, permitiendo que el jugador determine si el uso de esos puntos vale la pena.

Sin embargo, en general, como dijo bluescrn, el DPCT (o DPS como se lo llama en muchos juegos que están muy afinados y discutidos por los jugadores que buscan la mejor combinación) es realmente el elemento principal que querrás tener equilibrado, especialmente si tienes algún tipo de árboles de tecnología / habilidad que permiten a diferentes jugadores progresar con diferentes habilidades, pero con la capacidad de hacer cantidades similares de daño en su posición determinada en el juego.

Jeff Gray
fuente
0

Descubrí este algoritmo que funciona bien para mis propósitos.

La gente trajo algunos grandes puntos. Darle parámetros de objetivos finales permitiría que los algoritmos de búsqueda normales hicieran lo suyo. es decir. hacer daño óptimo en t segundos, hacer x daño en tiempo óptimo.

Mi algoritmo simplemente devuelve la secuencia de hechizos con el mayor DPS. Es un algoritmo rápido, ya que reduce el tamaño del conjunto que está atravesando, no requiere el conocimiento de otras técnicas de árbol de búsqueda.

El primer paso es identificar el hechizo con el mayor daño por tiempo de lanzamiento. Este hechizo se convierte en el hechizo "de referencia" ya que garantizará el mayor daño por segundo. Es decir, siempre debes lanzar este hechizo si se cumplen las siguientes 2 condiciones: 1) El hechizo de referencia está disponible (no en tiempo de reutilización). 2) Actualmente no estás lanzando un hechizo.

Entonces se convierte en una cuestión de completar otros hechizos mientras el hechizo de referencia está en enfriamiento. Entre (tiempo de lanzamiento) y (tiempo de reutilización - tiempo de lanzamiento). Sin embargo, pueden ocurrir algunas superposiciones (la regla 2 anterior es falsa).

Luego se convierte en una cuestión de recurrir a través de todos los hechizos que no sean la línea de base para encontrar todas las secuencias de hechizos que no violen las 2 reglas.

Para los hechizos que se superponen, debes penalizarlos por el daño potencial que podría haber causado el hechizo de referencia (hasta su daño máximo).

Toma por ejemplo 2 hechizos

1: 300 de daño, 3s de tiempo de lanzamiento, 10s de enfriamiento

2: 290 de daño, 3s de tiempo de lanzamiento, 3s de enfriamiento

El mayor daño proviene de la secuencia 1 - 2 - 2 - 2. Lo que provoca una superposición de 2 segundos en un lanzamiento potencial # 1. Sin embargo, esto sigue siendo beneficioso ya que si no lanzas el tercer hechizo (es decir, 1 - 2 - 2) harás 880 de daño con 1 segundo de sobra. Si lanzas el hechizo adicional n. ° 2, harás 1170 - 2 segundos del n. ° 1, que es 200. Entonces 970 daño es tu daño relativo.

aaronfarr
fuente
-2

Podría hacer un caso simple de cambio de estilo de "nivel de seguridad".

Esto está fuera de mi alcance, así que tenga cuidado con los errores lógicos más allá del nivel de pensamiento de mi estado cansado, pero espero que esto pueda ayudarlo a comenzar.

Asumiendo que su tiempo se hace en enteros de bloque,

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

Algunas de las llamadas a métodos son innecesarias debido a los tiempos de hechizo, pero siempre hay espacio para actualizaciones de esta manera.

Editar: Acabo de darme cuenta, que necesitarías restablecer el tiempo restante después de que se lanzó el nuevo hechizo, probablemente lo mejor para convertirlo en un atributo / campo de clase y configurarlo desde una llamada dentro de los métodos de castSpell.

kymully
fuente
Realmente no tengo idea de lo que estás tratando de obtener aquí, pero ningún motor de juego moderno tiene funciones como castSpell1 y castSpell2.
1
@ Joe Wreschnig Me refería a ellos como sus propios métodos en sus clases de juego personalizadas, este es solo un ejemplo abstracto, no uno detallado.
kymully
1
Correcto, no es así como funcionan los hechizos en los motores modernos. Hay una función castSpell que toma un objeto cuyos campos se leen de un archivo. Tal declaración de cambio sería imposible de mantener en cualquier motor real, y se requiere algún tipo de algoritmo de planificación.
@ Joe Wreschnig, entiendo. Simplemente estaba dando una manera de resolver el problema. Este ejemplo está escrito en Java, no destinado a un motor o marco específico. Pero si no se puede implementar como usted dice, mi respuesta es nula.
kymully