Algoritmo Genético para Geração de Ondas de Inimigos em Jogos
Alunos:
Daniel Yoshio Hotta
Rafael Gonçalves Pereira da Silva
Ricardo Akira Tanaka
Orientadores:
Prof. Marco Dimas Gubitoso
Wilson Kazuo Mizutani
Resumo:
Este trabalho se propõe a estudar a viabilidade de um algoritmo
evolutivo para geração de ondas de oponentes em jogos cujo o
objetivo do jogador é eliminá-los. Para ampliar o escopo do
projeto, foi definido que o algoritmo desenvolvido deveria ser
o mais genérico possível, possibilitando sua implementação em
diversos jogos, apenas com pequenos refatoramentos do código.
Considerando a existência de ondas de inimigos, cujos individuais
podem obter sucesso ou fracasso contra o jogador, definiu-se
que um algoritmo genético seria apropriado, já que o mesmo poderia
usar as ondas como população e conseguiria obter candidatos
de sucesso para a próxima onda, sem a necessidade de características
específicas do jogo, e se adaptando a mudanças nas condições
ou da estratégia de quem está jogando. Foram desenvolvidos dois
protótipos de jogos dentro das categorias delimitadas, um Tower Defense
e um Top-Down Shooter, com ferramentas de código aberto
como a game engine Godot. Os jogos foram selecionados
por possuírem suficientes características comuns entre sí, permitindo
a implementação do mesmo algoritmo com pequenas adaptações,
e ao mesmo tempo diferentes o suficiente para produzirem experiências
e resultados diferentes. Durante o desenvolvimento diversos
fatores e decisões se mostraram essenciais ao algoritmo, como
diferentes necessidades de fitness e mutações em cada
jogo e entre ondas de inimigos. Finalmente foram desenvolvidos
métodos de teste e métricas de avaliação para, com dados objetivos,
obter indícios de que o algoritmo seria superior a implementações
ingênuas como uma geração aleatória. Os resultados aparentam
maior adequação a jogos mais determinísticos, onde um ambiente
mais estático acaba favorecendo o algoritmo.
Abstract:
This project is a study around the viability of an evolutionary
algorithm for generating waves of enemies in games, where the
player's objective is eliminating them. To expand the subject,
it was defined that the algorithm should be as generic as possible
to allow its implementation in other games, with minor code
refactoring. Considering the enemy wave as a group of individuals
that can end up in a success or failure in the round, a genetic
algorithm seemed suitable, since it would be able to use the
waves as population, with each individual a candidate for the
next wave, representing the next generation of individuals.
The algorithm does not depend on extensive knowledge about the
game mechanics, being able to adapt to ambient changes and player
strategy. Two game prototypes were developed, a Tower Defense
and a Top-Down Shooter, using open source tools such as the
Godot Game Engine. The games were selected due to its common
characteristics in style, which allows using the same evolutionary
algorithm, but at the same time they diverge in gameplay and
strategy, producing different results and experiences. During
development several factors and decisions were key to the algorithm,
such as the fitness and mutation calculations for each game,
and each wave. To enable performance analysis, testing methods
and evaluation metrics were developed, enabling objective data
to be gathered and measured against randomly generating enemies.
Data analysis showed that the genetic algorithm performs above
other naive methods, but is more successful in deterministic
games, where a more stable environment favors the algorithm.
LINK PARA MONOGRAFIA