Conjuração de feitiços - Como otimizar danos por segundo

23

Imagine que temos um mago que conhece alguns feitiços. Cada feitiço tem 3 atributos: Dano, tempo de esfriamento e tempo de conjuração. Material bastante padrão de RPG.

Tempo de espera: a quantidade de tempo (t) que leva para ser capaz de lançar o feitiço novamente. Um feitiço continua "cooldown" no momento em que começa a ser lançado.

Tempo de conjuração: a quantidade de tempo (t) necessária para usar um feitiço. Enquanto o assistente estiver lançando algo, outro feitiço não pode ser lançado e não pode ser cancelado.

A pergunta é: como você maximizaria o dano devido a diferentes conjuntos de feitiços?

É fácil calcular o maior dano por tempo de lançamento. Mas e nas situações em que é melhor esperar do que ficar "preso" lançando um feitiço de baixo dano quando um muito mais alto está disponível?

Por exemplo,

  1. Bola de fogo: 3000 de dano, tempo de lançamento de 3 segundos e esfriamento de 6 segundos.

  2. Frostbolt: 20 de dano, 4 segundos de tempo de lançamento e 4 segundos de resfriamento.

  3. Fireblast: 3 de dano, 3 segundos de tempo de lançamento, 3 segundos de resfriamento.

Nesse caso, seu dano por segundo é maior se você optar pelo feitiço DPCT mais baixo (fireblast) em vez do congelador. Portanto, devemos considerar as consequências de escolher um feitiço. texto alternativo

No exemplo a seguir, há casos de "conversão excessiva" e "espera". texto alternativo

aaronfarr
fonte
Por que eu faria 1-3-1 nesta situação? Por que não 1-2-1? Por que não 1-2-3-1, que é mais eficiente que 1-3-1-X se 1-3-1 sozinho não mata o alvo?
@ Joe Wreschnig: Obrigado por apontar isso. Foi um erro no meu exemplo. Simplificado agora para apenas 2 casos.
precisa saber é o seguinte
1
Ganancioso, como em escolher o maior número de dps disponíveis sempre que possível. Desconsiderando outra lógica, ie. esperando.
aaronfarr
1
Apenas para enlamear a água. Considere um feitiço que causa ∞ de dano, mas leva 50 segundos para ser lançado. É dps / dpct é ∞, mas nunca deve ser escolhido se o alvo puder ser morto com outros meios em menos de 50 segundos.
Deft_code
1
Você deve criar um link para o dupe em math.stackexchange.com/questions/10414/…
Sparr

Respostas:

23

Toda IA ​​é pesquisa!

Quando você entra nas entranhas da IA, é incrível o quanto é realmente pesquisado .

  • estado : a recarga restante de todos os feitiços disponíveis.
  • fitness : dano total causado
  • custo : tempo total gasto
  • ramos : qualquer feitiço conhecido. Se o feitiço ainda estiver em recarga, adicione esse valor ao seu tempo de lançamento.
  • objetivo : saúde total do alvo. O objetivo deve ser uma quantidade finita de dano; portanto, no caso de um alvo desconhecido, escolha a maior saúde possível.
    Como alternativa, a meta poderia ser gasta menos de 50 segundos e a pesquisa encontraria o dano máximo que poderia ser feito em 50 segundos.

Conecte esses parâmetros a uma pesquisa de custo uniforme (UCS) e plano de batalha ideal garantido e pronto. Ainda melhor se você puder criar uma heurística, pesquisar com A * ou IDA * e obterá a mesma resposta muito mais rapidamente.

Mais algumas vantagens em usar o UCS é que ele pode encontrar uma ordem de conversão ideal para situações muito mais complicadas do que a que você forneceu com apenas 3 variáveis. Alguns outros aspectos que poderiam ser facilmente adicionados:

  • danos ao longo do tempo
  • atualizar feitiço para reduzir a recarga de outros feitiços
  • feitiço de aceleração, fazendo com que outros feitiços sejam lançados mais rapidamente.
  • impulsionador de dano, fazendo com que outros feitiços causem mais dano.

O UCS não é onipotente. Não pode modelar os benefícios dos feitiços de proteção. Para isso, você precisará atualizar para a pesquisa alfa-beta ou minimax.
Também não lida muito bem com as áreas afetadas e as brigas em grupo. O UCS pode ser ajustado para fornecer soluções razoáveis ​​nessas situações, não é garantido que você encontre a solução ideal.

deft_code
fonte
2

Esse é um problema especializado de otimização combinatória. À medida que o número de magias aumenta, a dificuldade em encontrar a combinação / padrão ideal de magias aumenta significativamente. Heurísticas semelhantes às usadas para o problema da mochila seriam valiosas na solução desse problema.

Sparr
fonte
1

Você precisa pensar em termos de 'dano por unidade de tempo de conjuração' (DPCT) - por exemplo, uma bola de fogo com um elenco de 3 segundos e causar 3000 danos causaria 1000 DPCT.

Se você tivesse que esperar 3 segundos pela recarga antes de lançá-la, isso a reduziria para 500 DPCT (3000 de dano, dividido por 6 segundos no total, incluindo a espera)

Então você só precisa determinar o dano por tempo de lançamento de cada feitiço, incluindo qualquer espera restante pela recarga. Escolha aquele com o DPCT mais alto, aguarde se necessário e depois o faça. Repita até que o chefe esteja morto :)

bluescrn
fonte
o problema é que o DPCT pode ser muito enganador. Digamos, por exemplo, que adicionemos mais 2 feitiços à mistura Bola de Fogo: 3000 de dano, 3 segundos de lançamento, 6 segundos de recarga, DPCT: 1000 Feitiço # 2: 20 de dano, 4 segundos de lançamento, 4 segundos de recarga, DPCT: 5 Feitiço # 3: 3 dano, 3 segundos de lançamento, 3 segundos de recarga, DPCT: 1 (lembre-se, a recarga começa no momento em que a mágica é lançada) Mesmo que a Magia # 3 tenha um DPCT menor, resultará em DPS maior (1-3-1-3 .. .) do Feitiço # 2 (1-2-1-2 ...).
aaronfarr
1

Usando seu exemplo, você provavelmente desejaria que os dois feitiços tivessem maior eficácia, mas possivelmente lhe proporcionaria uma vantagem diferente. Ter um tempo de projeção curto (ou sem tempo de projeção) seria muito útil; portanto, pode valer a pena usá-lo mesmo que cause menos dano e demore mais para ser usado novamente.

Você sempre pode impor outro elemento à equação. Pontos de Mana / Mágica podem servir a esse propósito, permitindo ao jogador determinar se o uso desses pontos vale o benefício.

No geral, porém, como o bluescrn disse, o DPCT (ou DPS, como é chamado em muitos jogos que são altamente afinados e discutidos por jogadores que buscam o melhor mix) é realmente o principal elemento que você deseja equilibrar, especialmente se você tiver algum tipo de árvores de tecnologia / habilidade que permitem que diferentes jogadores progridam com habilidades diferentes, mas com a capacidade de causar quantidades semelhantes de dano em uma determinada posição no jogo.

Jeff Gray
fonte
0

Descobri esse algoritmo que funciona bem para meus propósitos.

As pessoas levantaram alguns grandes pontos. Fornecer parâmetros de objetivo final permitiria que algoritmos de pesquisa normais realizassem suas tarefas. ie faça o dano ideal em t segundos, faça x o dano no tempo ideal.

Meu algoritmo simplesmente retorna a sequência de feitiços com o DPS mais alto. É um algoritmo rápido, pois reduz o tamanho do conjunto que você está percorrendo, não requer conhecimento de outras técnicas da árvore de pesquisa.

O primeiro passo é identificar o feitiço com o maior dano por tempo de lançamento. Esse feitiço se torna o feitiço "linha de base", pois garante o maior dano por segundo. Ou seja, você sempre deve lançar esse feitiço se as 2 condições a seguir forem atendidas: 1) O feitiço da linha de base está disponível (não na recarga). 2) Você não está lançando um feitiço no momento.

Portanto, torna-se uma questão de preencher outros feitiços enquanto o feitiço da linha de base está em recarga. Entre (tempo de lançamento) e (tempo de espera - tempo de lançamento). No entanto, algumas sobreposições podem ocorrer (a regra 2 acima é falsa).

Torna-se então uma questão de recorrer a todos os feitiços que não são da linha de base para encontrar todas as sequências de feitiços que não violam as 2 regras.

Para feitiços que se sobrepõem, você deve penalizá-los por possíveis danos que o feitiço da linha de base poderia ter causado (até o dano máximo).

Tomemos, por exemplo, 2 feitiços

1: 300 de dano, tempo de lançamento de 3s, tempo de recarga de 10s

2: 290 de dano, tempo de lançamento de 3s, tempo de recarga de 3s

O maior dano vem da sequência 1 - 2 - 2 - 2. O que causa uma sobreposição de 2 segundos em um potencial número 1 de lançamento. No entanto, isso ainda é benéfico, pois se você não lançar o terceiro feitiço (por exemplo, 1 - 2 - 2), você causará 880 de dano com 1 segundo de sobra. Se você lançar o feitiço # 2 extra, fará 1170 - 2 segundos do número 1, que é 200. Portanto, 970 de dano é o seu dano relativo.

aaronfarr
fonte
-2

Você pode fazer um simples caso de alternância no estilo "nível de segurança".

Isso está fora da minha cabeça, portanto, cuidado com os erros de lógica além do nível de pensamento do meu estado de cansaço, mas espero que isso possa ajudá-lo a começar.

Supondo que seu tempo seja feito em números inteiros de bloco -

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

Algumas das chamadas de método são desnecessárias devido aos seus tempos de ortografia, mas sempre há espaço para atualizações dessa maneira.

Edit: Acabei de perceber que você precisaria redefinir o tempo restante após o lançamento do novo feitiço, provavelmente o melhor para torná-lo um atributo / campo de classe e defini-lo a partir de uma chamada nos métodos castSpell.

kymully
fonte
Eu realmente não tenho idéia do que você está tentando chegar aqui, mas nenhum mecanismo de jogo moderno tem funções como castSpell1 e castSpell2.
1
@ Joe Wreschnig, eu quis dizer que eles são seus próprios métodos em suas classes de jogos personalizadas, este é apenas um exemplo abstrato, não detalhado.
Kimully #
1
Certo, não é assim que os feitiços funcionam nos motores modernos. Há uma função castSpell que pega um objeto cujos campos são lidos de um arquivo. Tal declaração de comutação seria impossível de manter em qualquer mecanismo real e é necessário algum tipo de algoritmo de planejamento.
@ Joe Wreschnig eu entendo. Eu estava apenas dando uma maneira de resolver o problema. Este exemplo é escrito em java, não destinado a um mecanismo ou estrutura específica. Mas se não puder ser implementado como você diz, minha resposta será nula.
kymully