Geração de missão usando aprendizado de máquina clássico e redes neurais recorrentes no estado zumbi

Talvez você esteja familiarizado com a geração de nível processual; bem, neste post é tudo sobre geração de missão processual. Analisaremos o panorama geral da geração de missões usando aprendizado de máquina clássico e redes neurais recorrentes para jogos roguelike.

Olá a todos! Meu nome é Lev Kobelev e sou Game Designer na MY.GAMES. Neste artigo, gostaria de compartilhar minha experiência no uso de ML clássico e redes neurais simples enquanto explico como e por que decidimos pela geração de missão processual, e também nos aprofundaremos na implementação do processo em Zombie Estado.

O básico da “caixa” da missão: ondas, spawns e muito mais

☝🏻 Primeiramente, algumas terminologias: “ arenas ”, “ níveis ” e “ locais ” são sinônimos neste contexto, assim como “ área ”, “ zona ” e “ área de spawn ”.

Agora, vamos definir “ missão ”. Uma missão é uma ordem predeterminada na qual os inimigos aparecem em um local de acordo com certas regras . Como mencionado, em Zombie State são gerados locais, por isso não estamos criando uma experiência “encenada”. Ou seja, não colocamos os inimigos em pontos pré-determinados – na verdade, esses pontos não existem. No nosso caso, um inimigo aparece em algum lugar próximo a um jogador ou a uma parede específica. Além disso, todas as arenas do jogo são retangulares, portanto qualquer missão pode ser jogada em qualquer uma delas.

Vamos apresentar o termo “ desova ”. Spawning é o aparecimento de vários inimigos do mesmo tipo de acordo com parâmetros pré-determinados em pontos de uma zona designada . Um ponto – um inimigo. Se não houver pontos suficientes dentro de uma área, ela será expandida de acordo com regras especiais. Também é importante entender que a zona é determinada somente quando um spawn é acionado. A área é determinada pelos parâmetros de spawn, e consideraremos dois exemplos abaixo: um spawn próximo ao jogador e outro próximo a uma parede.

O primeiro tipo de spawn está próximo ao jogador . A aparência próxima ao jogador é especificada através de um setor, que é descrito por dois raios: externo e interno (R e r), a largura do setor (β), o ângulo de rotação (α) em relação ao jogador, e o visibilidade desejada (ou invisibilidade) da aparência do inimigo. Dentro de um setor estão a quantidade necessária de pontos para os inimigos – e é daí que eles vêm!

O segundo tipo de spawn está perto da parede . Quando um nível é gerado, cada lado é marcado com uma etiqueta – uma direção cardeal. A parede com saída fica sempre ao norte. A aparência de um inimigo próximo a uma parede é especificada pela etiqueta, a distância dela (o), o comprimento (a), a largura de uma zona (b) e a visibilidade (ou invisibilidade) desejada da aparência do inimigo. O centro de uma zona é determinado em relação à posição atual do jogador.

As crias vêm em ondas . Uma onda é a forma como os spawns aparecem, ou seja, o atraso entre eles – não queremos atacar os jogadores com todos os inimigos de uma vez. As ondas são combinadas em missões e lançadas uma após a outra, de acordo com uma certa lógica. Por exemplo, uma segunda onda pode ser lançada 20 segundos após a primeira (ou se mais de 90% dos zumbis dentro dela forem mortos). Assim, uma missão inteira pode ser considerada como uma caixa grande, e dentro dessa caixa existem caixas de tamanho médio (ondas), e dentro das ondas existem caixas ainda menores (spawns).

Então, antes mesmo de trabalhar nas missões propriamente ditas, já definimos algumas regras:

1. Para manter um senso de ação constante, certifique-se de gerar zumbis regulares perto do jogador em pontos visíveis com frequência.
2. Para destacar a saída ou empurrar o jogador de um determinado lado, esforce-se para gerar principalmente inimigos de batalha de longo alcance perto das paredes
3. Ocasionalmente, crie inimigos especiais na frente do jogador, mas em pontos invisíveis.
4. Nunca gere inimigos a menos de X metros do jogador
5. Nunca gere mais de X inimigos ao mesmo tempo

A certa altura, tínhamos cerca de cem missões prontas, mas depois de um tempo, precisávamos de ainda mais. Os outros designers e eu não queríamos gastar muito tempo e esforço criando mais cem missões, então começamos a procurar um método rápido e barato para geração de missões.

Geração Missionária

Decomposição da missão

Todos os geradores operam de acordo com algum conjunto de regras, e nossas missões criadas manualmente também foram realizadas de acordo com certas recomendações. Então, levantamos uma hipótese sobre os padrões das missões, e esses padrões funcionariam como regras para o gerador.

✍🏻 Alguns termos que você encontrará no texto:

• Clustering é a tarefa de dividir uma determinada coleção em subconjuntos (clusters) não sobrepostos, de modo que objetos semelhantes pertençam ao mesmo cluster e objetos de clusters diferentes sejam significativamente diferentes.

• Recursos categóricos são dados que obtêm um valor de um conjunto finito e não possuem representação numérica. Por exemplo, a tag da parede de spawn: Norte, Sul, etc.

• A codificação de características categóricas é um procedimento para converter características categóricas em uma representação numérica de acordo com algumas regras previamente especificadas. Por exemplo, Norte → 0, Sul → 1, etc.

• A normalização é um método de pré-processamento de características numéricas para trazê-las a alguma escala comum sem perder informações sobre a diferença nos intervalos. Eles podem ser usados, por exemplo, para calcular a semelhança de objetos. Conforme mencionado anteriormente, a similaridade de objetos desempenha um papel fundamental nos problemas de agrupamento.

  
  

A pesquisa manual de todos esses padrões consumiria muito tempo, por isso decidimos usar clustering. É aqui que o aprendizado de máquina se torna útil, pois lida bem com essa tarefa.

O clustering funciona em algum espaço N-dimensional e o ML funciona especificamente com números. Portanto, todos os spawns se tornariam vetores:

• Variáveis categóricas foram codificadas
• Todos os dados foram normalizados

Assim, por exemplo, o spawn que foi descrito como “gerar 10 atiradores de zumbis na parede norte em uma área com um recuo de 2 metros, largura de 10 e comprimento de 5” tornou-se o vetor [0,5, 0,25, 0,2 , 0,8,…, 0,5] (←esses números são abstratos).

Além disso, o poder do conjunto de inimigos foi reduzido mapeando inimigos específicos em tipos abstratos. Para começar, esse tipo de mapeamento facilitou a atribuição de um novo inimigo a um determinado grupo. Isso também tornou possível reduzir o número ideal de padrões e, como resultado, aumentar a precisão da geração – mas falaremos mais sobre isso mais tarde.

O algoritmo de agrupamento

Existem muitos algoritmos de cluster: K-Means, DBSCAN, espectral, hierárquico e assim por diante. Todos são baseados em ideias diferentes, mas têm o mesmo objetivo: encontrar clusters nos dados. Abaixo, você vê diferentes maneiras de encontrar clusters para os mesmos dados, dependendo do algoritmo escolhido.

O algoritmo K-Means teve melhor desempenho no caso de spawns.

Agora, uma pequena digressão para quem nada sabe sobre este algoritmo (não haverá raciocínio matemático estrito já que este artigo é sobre desenvolvimento de jogos e não sobre o básico de ML). K-Means divide iterativamente os dados em K clusters, minimizando a soma das distâncias quadradas de cada recurso para o valor médio de seu cluster atribuído. A média é expressa pela soma intracluster das distâncias quadradas.

É importante entender o seguinte sobre este método:

• Não garante o mesmo tamanho de clusters — para nós, isto não foi um problema, uma vez que a distribuição de clusters dentro de uma missão pode ser desigual.
• Ele não determina o número de clusters dentro dos dados, mas requer um certo número K como entrada, ou seja, o número desejado de clusters. Às vezes, esse número é determinado antecipadamente e, às vezes, não. Além disso, não existe um método geralmente aceite para encontrar o “melhor” número de clusters.

Vejamos esse segundo ponto com um pouco mais de detalhes.

O número de clusters

O método do cotovelo é frequentemente usado para selecionar o número ideal de clusters. A ideia é muito simples: executamos o algoritmo e tentamos todos os K de 1 a N, onde N é algum número razoável. No nosso caso, foram 10 – foi impossível encontrar mais clusters. Agora, vamos encontrar a soma dos quadrados das distâncias dentro de cada cluster (uma pontuação conhecida como WSS ou SS). Exibiremos tudo isso em um gráfico e selecionaremos um ponto após o qual o valor no eixo y parará de mudar significativamente.

Para ilustrar, usaremos um conjunto de dados bem conhecido, o Conjunto de dados de flores de íris . Vamos executar o algoritmo com K de 1 a 10 e ver como a estimativa acima muda dependendo de K. Aproximadamente K = 3, a estimativa para de mudar muito - e é exatamente quantas classes havia no conjunto de dados original.

Se você não consegue ver o cotovelo, pode usar o método Silhouette, mas está além do escopo do artigo.

Todos os cálculos acima e abaixo foram feitos em Python usando bibliotecas padrão para ML e análise de dados: pandas, numpy, seaborn e sklearn. Não estou compartilhando o código, pois o objetivo principal do artigo é ilustrar os recursos, em vez de entrar em detalhes técnicos.

Analisando cada cluster

Após obter o número ideal de clusters, cada um deles deve ser estudado detalhadamente. Precisamos ver quais spawns estão incluídos nele e os valores que eles assumem. Vamos criar nossas próprias configurações para cada cluster para uso em gerações futuras. Os parâmetros incluem:

• Pesos inimigos para calcular a probabilidade. Por exemplo, um zumbi normal = 5 e um zumbi com capacete = 1. Portanto, a probabilidade de um zumbi normal é 5/6 e um zumbi com capacete é 1/6. Os pesos são mais convenientes de operar.
• Limites de valor, por exemplo, o ângulo mínimo e máximo de rotação da zona ou a sua largura. Cada parâmetro é descrito por seu próprio segmento, cujo valor é igualmente provável.
• Valores categóricos, por exemplo, uma etiqueta de parede ou visibilidade de ponto, são descritos como configurações do inimigo, e isso é feito por meio de pesos.

Vamos considerar as configurações do cluster, que podem ser descritas verbalmente como “a geração de inimigos simples em algum lugar próximo ao jogador, a uma curta distância e, provavelmente, em pontos visíveis”.

Tabela do cluster 1

Aqui estão dois truques úteis:

• Não é um número fixo do inimigo que é especificado, mas um segmento a partir do qual seu número será selecionado. Isto ajuda a operar com o mesmo inimigo em grupos diferentes, mas em quantidades diferentes.
• Não é o raio externo (R) que é especificado, mas o delta (R-delta) relativo ao raio interno (r), de modo que a regra R > r seja respeitada. Assim, R-delta é adicionado a r aleatório, r+R-delta > r para qualquer R-delta > 0, o que significa que tudo está bem.

Isso foi feito com cada cluster e havia menos de 10 deles, então não demorou muito.

Algumas coisas interessantes sobre clustering

Só tocamos um pouco nesse assunto, mas ainda há muita coisa interessante para estudar. Aqui estão alguns artigos para referência; eles fornecem uma boa descrição dos processos de trabalho com dados, agrupamento e análise de resultados.

• Pokmean — KMean Clusting na Pokedex
• Agrupando jogos de League of Legends
• Agrupamento de jogadores de campo do FIFA20

Hora de uma missão

Além dos padrões de spawn, decidimos estudar a dependência da saúde total dos inimigos dentro de uma missão em relação ao tempo esperado de sua conclusão para utilizar este parâmetro durante a geração.

No processo de criação de missões manuais, a tarefa era construir um ritmo coordenado para o capítulo — uma sequência de missões: curta, longa, curta, curta novamente e assim por diante. Como você pode obter a saúde total dos inimigos dentro de uma missão se você conhece o DPS esperado do jogador e seu tempo?

💡 A regressão linear é um método de reconstruir a dependência de uma variável de outra ou de várias outras variáveis com uma função de dependência linear. Os exemplos abaixo considerarão regressão exclusivamente linear de uma variável: f(x) = wx + b.

Vamos apresentar os seguintes termos:

• HP é a saúde total dos inimigos na missão
• DPS é o dano esperado do jogador por segundo
• O tempo de ação é o número de segundos que o jogador gasta destruindo os inimigos na missão
• O tempo livre é o tempo adicional dentro do qual o jogador pode, por exemplo, alterar o alvo
• O tempo esperado da missão é a soma da ação e do tempo livre

Então, HP = DPS * tempo de ação + tempo livre. Ao criar um capítulo manual, registramos o tempo previsto de cada missão; agora, precisamos encontrar tempo para agir.

Se você souber o tempo esperado da missão , poderá calcular o tempo de ação e subtraí-lo do tempo esperado para obter o tempo livre : tempo livre = tempo de missão - tempo de ação = tempo de missão - HP * DPS. Esse número pode então ser dividido pelo número médio de inimigos na missão e você ganha tempo livre por inimigo. Portanto, tudo o que resta é simplesmente construir uma regressão linear do tempo esperado da missão até o tempo livre por inimigo.

Além disso, construiremos uma regressão da proporção do tempo de ação em relação ao tempo de missão.

Vejamos um exemplo de cálculos e vejamos por que essas regressões são usadas:

1. Insira dois números: tempo de missão e DPS como 30 e 70
2. Veja a regressão da parcela do tempo de ação em relação ao tempo de missão e obtenha a resposta, 0,8
3. Calcule o tempo de ação como 30*0,8=6 segundos
4. Calcule HP como 6*70=420
5. Veja a regressão do tempo livre por inimigo desde o tempo da missão e obtenha a resposta, que é 0,25 segundos.

Aqui está uma pergunta: por que precisamos saber o tempo livre para o inimigo? Como mencionado anteriormente, os spawns são organizados por tempo. Portanto, o tempo do i-ésimo spawn pode ser calculado como a soma do tempo de ação do (i-1)-ésimo spawn e o tempo livre dentro dele.

E aí surge outra pergunta: por que a divisão do tempo de ação e do tempo livre não é constante?

No nosso jogo, a dificuldade de uma missão está relacionada com a sua duração. Ou seja, as missões curtas são mais fáceis e as longas são mais difíceis. Um dos parâmetros de dificuldade é o tempo livre por inimigo. Existem várias linhas retas no gráfico acima e elas têm o mesmo coeficiente de inclinação (w), mas um deslocamento diferente (b). Assim, para alterar a dificuldade, basta alterar o deslocamento: aumentar b torna o jogo mais fácil, diminuir torna-o mais difícil e números negativos são permitidos. Essas opções ajudam você a alterar a dificuldade de capítulo para capítulo.

Acredito que todos os designers deveriam se aprofundar no problema da regressão, pois muitas vezes ela ajuda na desconstrução de outros projetos:

• Tutorial de regressão linear
• Projeto Básico de Aprendizado de Máquina - Regressão Linear
• Regressão Linear Scikit-learn para iniciantes

Gerando novas missões

Assim, conseguimos encontrar as regras do gerador e agora podemos passar para o processo de geração.

Se você pensar abstratamente, qualquer missão pode ser representada como uma sequência de números, onde cada número reflete um cluster de spawn específico. Por exemplo, missão: 1, 2, 1, 1, 2, 3, 3, 2, 1, 3. Isso significa que a tarefa de gerar novas missões se resume a gerar novas sequências numéricas. Após a geração, basta “expandir” cada número individualmente de acordo com as configurações do cluster.

Abordagem básica

Se considerarmos um método trivial de geração de uma sequência, podemos calcular a probabilidade estatística de uma desova específica seguir qualquer outra desova. Por exemplo, obtemos o seguinte diagrama:

O topo do diagrama é um cluster ao qual ele leva, um vértice, e o peso da aresta é a probabilidade do cluster ser o próximo.

Percorrendo esse gráfico, poderíamos gerar uma sequência. No entanto, esta abordagem tem uma série de desvantagens. Estes incluem, por exemplo, a falta de memória (ele só conhece o estado atual) e a chance de “ficar preso” em um estado se tiver uma alta probabilidade estatística de se transformar em si mesmo.

✍🏻 Se considerarmos este gráfico como um processo, obteremos uma cadeia de Markov simples.

Redes neurais recorrentes

Passemos às redes neurais, nomeadamente às recorrentes, uma vez que não apresentam as desvantagens da abordagem básica. Essas redes são boas para modelar sequências como caracteres ou palavras em tarefas de processamento de linguagem natural. Simplificando, a rede é treinada para prever o próximo elemento da sequência com base nos anteriores.

Uma descrição de como essas redes funcionam está além do escopo deste artigo, pois este é um tópico extenso. Em vez disso, vejamos o que é necessário para o treinamento:

• Um conjunto de N sequências de comprimento L
• A resposta para cada uma das N sequências é uma um-quente vetor, ou seja, um vetor de comprimento C composto por C-1 zeros e um 1, indicando a resposta.
• C é o poder do conjunto de respostas.

Um exemplo simples com N=2, L=3, C=5. Vamos pegar a sequência 1, 2, 3, 4, 1 e procurar subsequências de comprimento L+1 dentro dela: [1, 2, 3, 4], [2, 3, 4, 1]. Vamos dividir a sequência em uma entrada de L caracteres e uma resposta (destino) - o (L+1)ésimo caractere*.* Por exemplo, [1, 2, 3, 4] → [1, 2, 3] e [ 4]. Codificamos as respostas em vetores one-hot, [4] → [0, 0, 0, 0, 1].

A seguir, você pode esboçar uma rede neural simples em Python usando tensorflow ou pytorch. Você pode ver como isso é feito usando os links abaixo. Resta iniciar o processo de treinamento nos dados descritos acima, aguardar e... então você pode entrar em produção!

Os modelos de aprendizado de máquina possuem certas métricas, como precisão. A precisão mostra a proporção de respostas dadas corretamente. No entanto, deve ser visto com cautela, pois pode haver desequilíbrios de classe nos dados. Se não houver nenhuma (ou quase nenhuma), então podemos dizer que o modelo funciona bem se prever respostas melhor do que aleatoriamente, ou seja, precisão > 1/C; se estiver próximo de 1, funciona muito bem.

No nosso caso, o modelo apresentou boa precisão. Uma das razões para estes resultados é o pequeno número de clusters que foram alcançados graças ao mapeamento dos inimigos aos seus tipos e ao seu equilíbrio.

Aqui estão mais materiais sobre RNN para os interessados:

• Guia para iniciantes na geração de texto usando LSTMs
• Enfrentando tóxicos usando Keras
• Explorando os jogos avançados do Gameboy

Processo de Geração

Configuração do gerador

O modelo treinado é facilmente serializado , para que você possa usá-lo como um ativo na engine, no nosso caso, Unity. Assim, o gerador acessa o modelo por meio de uma API e cria iterativamente uma sequência. O resultado é expandido e salvo em um arquivo CSV separado.

Para interagir com o modelo, uma janela personalizada é criada no Unity onde os designers do jogo podem definir todos os parâmetros de missão necessários:

• Nome
• Duração
• Inimigos disponíveis, à medida que os inimigos aparecem gradualmente
• Número de ondas na missão e a distribuição da saúde entre elas
• Modificadores de peso específicos do inimigo, que ajudam a selecionar certos inimigos com mais frequência, por exemplo, novos
• E assim por diante

Depois de inserir as configurações, basta apertar um botão e obter um arquivo que pode ser editado se necessário. Sim, eu queria gerar missões com antecedência, e não durante o jogo, para que pudessem ser ajustadas.

As etapas da geração

Vejamos o processo de geração:

1. O modelo recebe uma sequência como entrada e produz uma resposta - um vetor de probabilidades de que o i-ésimo cluster será o próximo. O algoritmo lança os dados, se o número for maior que a chance de erro , então pegamos o mais provável, caso contrário aleatório. Este truque adiciona um pouco de criatividade e variedade.
2. O processo continua até um determinado número de iterações. É maior que o número de spawns em qualquer uma das missões criadas manualmente.
3. A sequência continua; ou seja, cada número acessa os dados salvos do cluster e recebe deles valores aleatórios.
4. A saúde dentro dos dados é resumida e tudo que for maior que a saúde esperada é descartado da sequência (seu cálculo foi discutido acima)
5. Os spawns são divididos em ondas dependendo da distribuição de saúde especificada e depois divididos em grupos (para que vários inimigos apareçam ao mesmo tempo), e seu tempo de aparecimento é dado como a soma da ação e do tempo livre do grupo anterior de spawns.
6. A missão está pronta!

Conclusões

Então, essa é uma boa ferramenta que nos ajudou a agilizar várias vezes a criação de missões. Além disso, ajudou alguns designers a superar o medo do “bloqueio de escritor”, por assim dizer, já que agora você pode obter uma solução pronta em poucos segundos.

No artigo, usando o exemplo de geração de missão, tentei demonstrar como métodos clássicos de aprendizado de máquina e redes neurais podem ajudar no desenvolvimento de jogos. Atualmente, há uma grande tendência para a IA generativa – mas não se esqueça de outros ramos do aprendizado de máquina, pois eles também são capazes de muito.

Obrigado por reservar um tempo para ler este artigo! Espero que você tenha entendido tanto a abordagem das missões em locais gerados quanto a geração de missões. Não tenha medo de aprender coisas novas, desenvolva-se e faça bons jogos!

Ilustrações de shabbyrtist