Resumo Técnico: Colapso da Função de Onda Evolucionário

Declaração do Problema

A Geração de Conteúdo Procedural (PCG) em videogames frequentemente enfrenta um compromisso entre controlabilidade e escalabilidade. O Colapso da Função de Onda (WFC) é um método popular para gerar conteúdo baseado em restrições de adjacência local aprendidas a partir de pequenos exemplos de entrada. Embora o WFC seja autossuficiente e rápido, ele carece de compreensão global; não consegue garantir a solucionabilidade ou impor restrições globais (ex: contagens específicas de entidades ou alcançabilidade entre pontos distantes). Por outroero, a PCG Baseada em Busca (SBPCG) permite a otimização explícita de objetivos complexos, mas é frequentemente dispendiosa computacionalmente e difícil de ser especificada por designers. O artigo investiga se essas abordagens podem ser hibridizadas: especificamente, se a busca evolucionária pode ser usada para otimizar os inputs (as pequenas imagens de exemplo) fornecidos ao WFC, em vez de evoluir diretamente os níveis finais. Isso trata o WFC como um mapeamento estocástico de genótipo-para-fenótipo.

Metodologia

O método proposto, Colapso da Função de Onda Evolucionário, evolui imagens de entrada compactas (genótipos) que servem como semente para o WFC gerar níveis de jogo maiores (fenótipos).

• Representação: Os indivíduos na população são representados por pequenas grades de azulejos (tiles) de $4 \times 4$. Essas grades são inicializadas com azulejos aleatórios do conjunto de azulejos (tileset) do jogo alvo.
• Mapeamento Genótipo-para-Fenótipo: O input $4 \times 4$ é passado para o algoritmo WFC. O WFC extrai todos os padrões de adjacência $2 \times 2$ deste input e os utiliza como restrições para gerar um nível de saída maior. A geração é estocástica; o mesmo genótipo pode produzir saídas diferentes dependendo da semente aleatória (random seed).
• Domínios Avaliados:
  1. Domínio de Labirinto (Maze): Gera mapas de $8 \times 8$. A função de aptidão (fitness) recompensa uma única região navegável conectada e caminhos navegáveis longos.
  2. Domínio de Zelda: Gera layouts de masmorras de $16 \times 16$. A função de aptidão é uma soma ponderada ($0,7 \cdot R_{entidade} + 0,3 \cdot R_{jogabilidade}$) que recompensa contagens específicas de entidades (um jogador, uma chave, uma porta, até 25 inimigos) e a jogabilidade (alcançabilidade entre jogador, chave e porta).
• Busca Evolucionária: O sistema utiliza um algoritmo evolucionário com seleção por torneio (tamanho 3), mutação e elitismo.
  • População: Tamanho de 10 sobre 100 gerações.
  • Mutação: Entre 1 e 5 posições de azulejos são mutadas por descendente. A probabilidade de mutação ($p$) começa em 0,5 e se adapta com base na melhoria da aptidão para equilibrar exploração e explotação.
  • Baseline: O método é comparado contra um baseline de Busca Aleatória, onde as populações são reamostradas aleatoriamente a cada geração, mantendo os melhores cromossomos.

Principais Resultados

O estudo avalia a eficácia desta abordagem híbrida em domínios com variadas dependências entre estrutura local e global.

• Domínio de Labirinto (Estrutura Local Dominante):

  • A busca evolucionária superou significativamente a busca aleatória, convergindo rapidamente para inputs de alto desempenho dentro das primeiras 40 gerações.
  • Os outputs evoluídos exibiram layouts coerentes e conectados, com caminhos contínuos longos.
  • Os resultados sugerem que propriedades desejadas, como conectividade, emergem naturalmente de relações de adjacência local repetidas, tornando este domínio altamente compatível com a representação WFC.

• Domínio de Zelda (Requer Estrutura Global):

  • A busca evolucionária produziu outputs mais estruturados que a busca aleatória (ex: salas reconhecíveis, posicionamento significativo de entidades) e alcançou valores de aptidão mais altos.
  • No entanto, a diferença de desempenho foi menor do que no domínio de Labirinto.
  • O sistema teve dificuldades em satisfazer restrições globais estritas simultaneamente (especificamente, garantir exatamente um jogador, uma chave e uma porta).
  • As curvas de aptidão mostraram uma melhoria rápida inicial seguida de estagnação próximo a um ótimo local, indicando que a dependência do WFC em padrões locais limita sua capacidade de modelar dependências de jogabilidade globais.

Significância e Alegações

O artigo afirma que o Colapso da Função de Onda Evolucionário é uma estratégia eficaz para guiar a geração procedural quando os objetivos alvo se alinham com regularidades estruturais locais.

• Vantagem Híbrida: A abordagem combina com sucesso a representação compacta e a velocidade do WFC com as capacidades de otimização da busca evolucionária.
• Dependência de Domínio: O método é mais eficaz em domínios onde propriedades globais (como conectividade) emergem indiretamente de relações locais. É menos eficaz em domínios que exigem restrições globais simbólicas explícitas (como contagens específicas de entidades ou ordem de progressão), porque o WFC não modela inerentemente essas dependências globais.
• Limitações: Os autores reconhecem que a natureza estocástica do WFC introduz ruído na avaliação da aptidão (uma vez que cada genótipo foi avaliado apenas uma vez). Além disso, a natureza local do WFC permanece uma restrição fundamental; a busca evolucionária não consegue superar a incapacidade do modelo subjacente de impor regras globais diretamente.

O artigo conclui que, embora este método melhore a qualidade e a organização da geração, trabalhos futuros devem explorar a integração de mecanismos explícitos de resolução de restrições globais no pipeline de WFC evolucionário para abordar domínios que exigem restrições simbólicas estritas.