O que é geração procedural?

A geração de procedimentos inclui muitos algoritmos generativos, cujo princípio não é criar dados manualmente, mas algoritmicamente: em vez de fabricar manualmente o que queremos criar (mapas, música, terreno ...), um algoritmo é escrito que pode criar com êxito vários exemplos sem executando o mesmo processo várias vezes. Essa abordagem é especialmente útil em videogames onde um mapa ou nível inteiro pode ser gerado aleatoriamente (por exemplo, mapas em Minecraft, Terraria ou Factorio ou esquemas de nível na maioria dos roguelike).

O algoritmo de colapso da função de onda e seu escopo

Neste artigo, examinamos o algoritmo de colapso da função de onda (WaveFunctionCollapse, WFC) proposto por Maxim Gumin (em seu Twitter, há uma coleção de conteúdo incrível criado usando esse algoritmo por outros desenvolvedores!) Para geração procedural de imagens ou terrenos, criando imagens localmente semelhantes às imagem em uma grade de um determinado tamanho.

O algoritmo baseia-se na ideia de criação passo a passo de uma imagem finalizada, com rastreamento de quais blocos "correspondem" a uma imagem já parcialmente construída. Para obter uma descrição detalhada do algoritmo, recomendamos que você consulte o repositório WFC original no Github e a quarta seção do artigo " WaveFunctionCollapse está resolvendo restrições de maneira natural ".


Exemplos de imagens de sementes geradas proceduralmente

Além de criar imagens semelhantes, outra área de aplicação do algoritmo WFC é a geração de cartões lado a lado. A geração de mapas de blocos será o tópico principal do artigo, porque é mais fácil de usar para explicar claramente nossas idéias. Em vez de uma imagem de exemplo, você pode armazenar apenas blocos e pares de blocos que podem ser conectados entre si por turnos. Nesse caso, o algoritmo pode ser usado para criar imagens semelhantes às mostradas abaixo.


Exemplos de blocos gerados aleatoriamente

O desafio e a nossa solução

Assumimos a tarefa de gerar um cartão de peças com base no jogo de tabuleiro Carcassonne (“Carcassonne”), no qual o campo é gerado pelos jogadores “manualmente” (veja a animação abaixo) a partir de peças que devem ser combinadas entre si.


Surpreendentemente, conceitualmente, isso é muito semelhante ao algoritmo WFC para criar cartões lado a lado arbitrários, adicionando novas peças a uma solução incompleta. E como o WaveFunctionCollapse pode ser usado como um gerador de cartão lado a lado, ele também pode gerar campos "Carcassonne"!

No entanto, no jogo em si, existem muitos blocos diferentes, e codificar todas as suas proporções é uma tarefa excessivamente volumosa para um hackathon de 24 horas. Por isso, decidimos jogar uma versão muito simplificada de "Carcassonne" sem castelos e rios, apenas com estradas, grama e mosteiros. Então, nós temos 6 peças possíveis com suas rotações e simetria. Mas, mesmo nessas condições, o resultado é bonito e parece um jogo de verdade em Carcassonne!


Visualização do preenchimento no algoritmo de campo de Carcassonne


Exemplo de regras introduzidas no algoritmo

A imagem acima contém um exemplo de regras de entrada adicionadas ao algoritmo. No entanto, ainda precisamos controlar certos aspectos da aparência do campo. O algoritmo deve criar “ruas” a partir de estradas cheias de mosteiros e similares a uma cidade, ou o campo deve consistir no máximo de grama com aldeias espalhadas ao redor? No algoritmo original, não há como controlar essas condições (como qualquer outra), mas, para a possibilidade de controle, é possível fazer uma simples melhoria.

Distribuição de probabilidade bayesiana a priori

Como mencionado acima, em cada etapa, o algoritmo adiciona um novo bloco ao campo para que ele corresponda aos blocos já colocados, mas não dissemos o que aconteceria se vários blocos diferentes pudessem ser colocados no local selecionado (também não falamos sobre como geralmente escolha esse local, mas no artigo não o consideraremos!). No algoritmo original, qualquer bloco adequado é selecionado aleatoriamente de maneira uniforme. No entanto, em nossa decisão, podemos preferir ladrilhos específicos, por exemplo, grama, para que ocorram com mais frequência no campo. Isso pode ser conseguido através da criação de uma distribuição desigual de “probabilidade prévia” de ladrilhos, na qual a grama tem uma chance maior de ser usada que a estrada, se ambos os tipos de ladrilhos puderem ser usados. Isso lembra as técnicas bayesianas. No caso simplificado de escolher entre duas opções, grama e estradas, podemos adicionar grama com probabilidade p> 0,5, e não com o usual 0,5, obtido com probabilidade uniforme. Essa tarefa pode ser facilmente generalizada atribuindo um valor de prioridade a cada bloco e usando esse valor para definir a probabilidade como um valor dividido pela soma dos valores de todos os blocos possíveis. A figura abaixo mostra duas soluções adequadas com valores de coeficiente muito diferentes, fornecendo uma compreensão de quão sensível o algoritmo pode ser.


Soluções diferentes para diferentes distribuições iniciais de probabilidade a priori

Outro exemplo: probabilidades condicionais e agrupamento

Você pode expandir essa idéia e, para ilustrar isso, geraremos, em vez dos campos de Carcassonne, mapas bidimensionais do minério de Minecraft. Diferentes tipos de minério no Minecraft são geralmente encontrados em grandes formações, portanto, juntamente com a definição das probabilidades de cada minério, faremos com que as probabilidades dependam dos vizinhos já colocados no mapa. Mesmo que não haja nada "proibido" na disposição do ferro perto do carvão, outro carvão recebe maior prioridade ao lado do carvão já colocado.

Embora isso não seja levado em consideração na imagem abaixo, no jogo a probabilidade também depende da altura dos ladrilhos, portanto, a posição na imagem também pode afetar as condições de distribuição das probabilidades do ladrilho.


Exemplo de mapa de minério de minério de Minecraft criado por WFC

Conclusão

A geração de procedimentos é uma ferramenta poderosa que vale a pena ter em estoque. Em particular, o WFC é usado ativamente na geração mundial, e vale a pena considerar a possibilidade de que a distribuição de novos blocos seja desigual e possa ser influenciada por outros fatores, por exemplo, vizinhos já colocados no mapa, novos blocos e posição na imagem. Criamos uma aplicação muito simples, mas as possibilidades de desenvolvimento são quase infinitas!