Tarefa 7: RPG

A tarefa 07 de MC202 consistia em simular uma batalha de RPG em turnos. São dados 2 equipes inimigas, cada qual com vários personagens com atributos diferentes, tais como força, velocidade, resistência e pontos de vida. Cada personagem tem um “período” inversamente proporcional a sua velocidade. Dados os períodos, podemos determinar os instantes de ataque de cada personagem. Quando dois personagens têm mesmo instante de ataque, existem alguns critérios de desempate que não cabe detalhar aqui.

Humano vs. Orc

Para determinar a ordem dos ataques, poderíamos fazer uma simulação discreta, por exemplo iterando sobre o tempo segundo a segundo e a cada instante verificar quem tinha um instante de tempo que caía bem naquele momento. A primeira desvantagem de tal método é que esse algoritmo é proporcional ao valor dos períodos, e a gente acaba iterando sobre instantes de tempo em que ninguém ataca. Além do mais, se os períodos forem números reais, esse tipo de abordagem pode ser impossível! Uma alternativa consiste em usar uma estrutura de dados chamada de fila de prioridades. A prioridade utilizada no caso é o próximo instante de ataque de cada personagem. Com uma fila de prioridades temos acesso ao elemento de maior prioridade em O(1). Assim, sabemos quem será o próximo atacante. Após efetuar o ataque, o próximo instante de ataque de uma personagem é a soma do instante atual e o período. Desta forma, basta reinseri-lo na fila com essa nova prioridade que em O(log n) conseguimos atualizar o heap mantendo suas propriedades.

Fila de Prioridades visualizada como árvore

Outro aspecto importante é a escolha do atacado. A estratégia de ambos os times consiste em atacar sempre o membro do time adversário com menos vida (mais alguns critérios de desempate). Uma observação importante é que todos do mesmo time “miram” no mesmo personagem inimigo até que este morra (porque se este já tinha menos pontos de vida, depois de sofrer os ataques continuará sendo o mais frágil). Isso nos possibilita ordenar inicialmente os membros dos times por ordem de não-decrescente de pontos de vida e, usando lista ligada, descobrir o membro a ser atacado em O(1), removendo-o da lista em caso de morte (também em O(1)). Aqui porém, eu permiti fazer do jeito força-bruta O(n) para escolher o mais fraco.

Esse método de simulação é mais eficiente do que a primeira proposta, sendo O(m log m), onde m é o número de turnos realizados antes de o jogo terminar. Porém, m pode ser proporcional aos valores de entrada, tornando nosso algoritmo pseudo-polinomial. Um exemplo seria dois times com um jogadores cada, um deles o personagem tem ataque 1 e no outro o personagem tem velocidade 0 e vida V. É fácil ver que o número de turnos é O(V), que pode ser tão grande quanto quisermos. Neste caso poderíamos ter feito algo mais eficiente, tal como calcular quantas vezes o personagem do time 1 ia atacar antes do personagem do time 2, mas acho que precisamos de uma ideia mais elaborada para funcionar em casos mais gerais. Porém, não cheguei a nenhuma conclusão se é possível resolver a simulação “analiticamente”.

Os comentários estão fechados.

%d bloggers like this: