Classificação de algoritmos para geração procedural de conteúdo em jogos digitais.

Abstract

Atualmente, os jogos digitais tentam atingir um realismo cada vez maior. Com esse objetivo, a geração de conteúdo para os jogos tende a ser cada vez mais complexa e custosa. Neste cenário, a utilização de técnicas de geração procedural de conteúdo pode diminuir tanto os custos quanto o tempo de produção do conteúdo necessário aos jogos digitais. Esta dissertação propõe comparações entre técnicas responsáveis pela geração procedural de conteúdo para jogos digitais. Nesse sentido, os algoritmos das técnicas tratadas nesta pesquisa foram implementados nas linguagens C++ e, quando aplicável, GLSL. A partir dessas implementações, foram realizadas análises pautadas por algumas métricas, tais como complexidade algorítmica, tempo de execução, consumo de memória, qualidade dos resultados, tipo de conteúdo gerado, método de geração, momento da geração, corretude do conteúdo, reprodutibilidade dos resultados e condição de parada dos algoritmos. Essas análises foram realizadas por meio do estudo de cada algoritmo, no caso da complexidade algorítmica, consumo de memória, método e momento de geração, reprodutibilidade dos resultados e condição de parada; ou da análise do conteúdo gerado, no caso da qualidade dos resultados e tipo de conteúdo gerado; ou, ainda, instrumentação do código, no caso da medição do tempo de execução. As métricas complexidade algorítmica, tempo de execução, consumo de memória e condição de parada foram definidas para auxiliar o desenvolvedor a selecionar técnicas que sejam adequadas às quantidades de tempo e memória disponíveis para a execução do código; as métricas de qualidade e tipo do conteúdo gerado foram escolhidas visando à seleção de técnicas que gerem conteúdo necessários ao jogo e sejam similares ao estilo da arte usada; as métricas de momento de geração, corretude e reprodutibilidade dos resultados têm como objetivo guiar o desenvolvedor às melhores técnicas para cada necessidade, evitando que os resultados não sejam corretos e causem problemas que atrapalhem os jogadores; por fim, o método de geração também foi selecionado como métrica pois auxilia os desenvolvedores e pesquisadores a escolher técnicas que sejam algoritmicamente parecidas, o que pode diminuir o tempo gasto para se estudar e desenvolver novas técnicas. Foram selecionadas técnicas que possuem implementações abertas e disponíveis na Internet. Estas foram reimplementadas, com o objetivo de padronizar e otimizar o código disponível. Após isso, os resultados obtidos em cada técnica foram comparados com o objetivo de se obter uma base de dados que possa ser utilizada por pesquisadores e desenvolvedores, proporcionando a eles informações que auxiliem a escolha da melhor técnica para cada situação. Por fim, os códigos implementados foram disponibilizados em um repositório aberto, de livre acesso para consulta e uso das técnicas.