Analysis and development of a game of roguelike genre

Abstract

Games are primarily a source of entertainment, but also a substrate for developing, testing and proving theories. When video games started to popularize, more ambitious projects demanded and pushed forward the development of sophisticated algorithmic techniques to handle real-time graphics, persistent large-scale virtual worlds and intelligent non-player characters. Our goal in this work is to develop a game of the roguelike genre, and to analyze and compare the algorithmic techniques used to address the challenges of such process. More specifically, we are going to focus on two design features, the first one being the procedural generation of dungeons, and the second being the artificial intelligence for enemies. Some of the results we have shown include, concerning generating procedural dungeons, that the techniques of basic iteration and BSP trees can be applied to any practical dungeon size, while cellular automata and maze generation through depth-first search must be optimized or restricted in some ways to increase scalability. Also, when it comes to the artificial intelligence for enemies, we concluded that both stateless and state-based techniques can be used with any practical number of concurrent actors without noticeable delay. However, we argued that state-machine actors can be designed to present more complex, flexible intelligent behavior. Regarding path-finding, we have shown that breadth-first search is satisfactory in terms of effectiveness, while in terms of efficiency it performs poorly if no substantial reductions of the search space are employed.

Jogos são primeiramente uma fonte de entretenimento, mas também um substrato para o desenvolvimento, teste e prova de teorias. Quando os jogos eletrônicos começaram a se popularizar, projetos mais ambiciosos exigiram e empulsionaram o desenvolvimento de sofisticadas técnicas algorítmicas para lidar com gráficos em tempo real, mundos virtuais persistentes de larga escala e personagens não-jogadores inteligentes. Nosso objetivo neste trabalho é desenvolver um jogo do gênero roguelike, e analisar e comparar as técnicas algorítmicas usadas para lidar com os desafios desse processo. Mais especificamente, focaremos em duas características de design, sendo a primeira a geração procedural de geração de masmorras, e a segunda a inteligência artificial de inimigos. Alguns dos resultados que mostramos incluem, em relação à geração procedural de masmorras, que as técnicas de iteração básica e árvores de partição de espaço binário podem ser aplicadas para qualquer tamanho prático de masmorra, enquanto que autômatos celulares e a geração de labirintos utilizando busca em profundidade precisam ser otimizadas ou restringidas de alguma forma para aumentar a escalabilidade. Além disso, no que concerne a inteligência artificial de inimigos, concluímos que tanto as técnicas de atores que não guardam estados quanto as que possuem máquinas de estados podem ser utilizadas para qualquer número prático de atores concorrentes sem atraso notável. Porém, argumentamos que atores com máquinas de estados podem ser projetados para apresentar comportamento inteligente mais complexo e flexível. Em relação à busca de caminhos, mostramos que a busca por amplitude é satisfatória em termos de efetividade, porém em termos de eficiência ela tem baixo desempenho se não há reduções substanciais no espaço de buscas.