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.
Isenção de responsabilidade: este artigo é apenas para fins informativos/entretenimento e, ao usar uma solução específica, aconselhamos que você verifique cuidadosamente os termos de uso de um determinado recurso e consulte a equipe jurídica!
☝🏻 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:
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.
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:
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.
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:
Vejamos esse segundo ponto com um pouco mais de detalhes.
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
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.
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:
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
Inimigos | Tipo | R | R-delta | rotação | largura | visibilidade |
---|---|---|---|---|---|---|
zumbi_common_3_5=4, zumbi_heavy=1 | Jogador | 10-12 | 1-2 | 0-30 | 30-45 | Visível=9, Invisível=1 |
Aqui estão dois truques úteis:
Isso foi feito com cada cluster e havia menos de 10 deles, então não demorou muito.
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.
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:
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:
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:
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.
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.
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 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:
O modelo treinado é facilmente
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:
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.
Vejamos o processo de geração:
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