Autômatos celulares em geração procedural: maximizando a conectividade em cavernas na Godot Engine

Abstract

One of the most widely used methods by the gaming industry for cave generation is cellular automata; however, if not applied appropriately, they can create environments that are unsuitable for a gaming context. Therefore, the present study aims to analyze and optimize the parameters used in this generation system to increase the connectivity rate of navigable areas while maintaining the desirable aesthetics of organic caves. Tests were conducted in the Godot Engine by varying the initial fill rate and the number of iterations, with the results subsequently analyzed by a Flood-fill algorithm. It was discovered that higher fill rates easily increase connectivity but fail to meet the requirements of a game environment, creating wide-open areas with almost no obstacles. It was then concluded that the ideal scenario consists of lower fill rates combined with a higher number of iterations, as this ensures the desired aesthetics and challenge for a game, even if the initial percentage of connected areas is lower. Furthermore, dead areas can be eliminated through a pruning method, delivering a fully navigable map with a low CPU processing cost.