♥️ 🐹 🐑 Dicas para usar o algoritmo de recolhimento da função Wave 👩🏽‍🤝‍👩🏻 🚁 🙄

Recentemente, experimentei muito a geração baseada em restrições processuais. Em particular, com o algoritmo Wave Function Collapse (WFC, wave function collapse). Eu até escrevi minha própria biblioteca de código aberto e o recurso de unidade .

O WFC é um algoritmo muito flexível, especialmente com as melhorias que desenvolvi. Mas, ao mesmo tempo, achei difícil criar níveis práticos aplicáveis aos jogos de computador com sua ajuda . A principal dificuldade é que o WFC não possui estrutura global. Tudo o que ele faz é fazer a geração de saída parecer localmente semelhante à entrada, por exemplo, observando pequenos retângulos individuais da saída.

Neste artigo, vou contar o que aprendi e o que será capaz de elevar os geradores com base nas restrições para um novo nível.

O básico

É difícil usar o WFC se você não sabe como ele funciona. Este é um algoritmo de geração de procedimentos baseado em restrições que tem recebido muita atenção recentemente. De fato, praticamente nada tem a ver com o conceito de física quântica em cuja honra foi nomeado.

O WFC é fácil de configurar - você fornece apenas um exemplo de cartão ao algoritmo, após o qual ele gera novos cartões que se parecem com o cartão original devido ao uso repetido de seus pequenos fragmentos.

Tem dois tipos - com um arranjo vizinho ou com uma sobreposição de elementos. Isso pode ser feito em 2D ou 3D, e mesmo em grades de hexágonos ou irregularesgrades. A maioria das minhas dicas se aplica independentemente de como você usa o algoritmo.

Sugiro que você jogue com esta demonstração para ter uma idéia do algoritmo e leia esta introdução [ tradução em Habré] se estiver interessado em detalhes técnicos.

Design do conjunto de peças

O algoritmo WFC é baseado em blocos. Nesse sentido, sua qualidade depende dos blocos que você transfere para o trabalho. Eu não sou um artista, por isso posso ajudar pouco no desenho de belos conjuntos de peças (embora você possa ver aqui ), mas um bom conjunto de peças também requer conhecimento técnico.

Cubos de marcha

Cubos de marcha é um algoritmo que seleciona quais blocos definir, dependendo de cada vértice do bloco estar cheio ou vazio. Aqui está a lista de blocos usados para 2D.

Se você criar ladrilhos para que os cantos preto e branco sempre correspondam, as linhas vermelhas sempre serão conectadas corretamente.

Aqui não precisamos entender todo o algoritmo, mas deve-se notar que a ideia de projetar blocos levando em consideração apenas o comportamento nos cantos é uma técnica muito poderosa. É usado em muitos dos melhores conjuntos de peças, pois garante que as peças sempre se conectem bem.

Essa técnica é especialmente poderosa para o WFC. Aconteceu, porque se você perder algumas peças, o WFC não importará. Ele contornará esse problema e nunca criará configurações que exijam blocos ausentes. Isso é muito conveniente para o 3D, pois existem dezenas de blocos em potencial e alguns deles são necessários apenas em situações muito difíceis. Veja a seção “Fundação” abaixo, na qual eu uso esse truque ainda mais amplamente.

Conhecer outros padrões de ladrilhos também pode ser útil , mas o Marching Cubes é o melhor.

Os quartos

Às vezes, é mais fácil trabalhar com conjuntos de peças simples. Esta combinação de 4 peças (uma peça está vazia) gera facilmente salas quadradas.

O tamanho das salas pode ser facilmente alterado alterando o peso de cada ladrilho. Depois de adicionar os ladrilhos da porta e do corredor, você pode criar a diversidade característica das plantas das pessoas.

Fundação

Ao trabalhar com o WFC, é interessante experimentar conjuntos de peças. Se você simplesmente colocar um bloco, o WFC procura extrair o máximo do espaço restante. Às vezes, isso leva a resultados radicalmente diferentes, como pode ser visto na imagem de Maxim Gumin:

Podemos usar esse comportamento para estimular o WFC a gerar muitas estruturas reconhecíveis.

Aqui está um exemplo de castelo (inspirado em @greentecq ):

Nele, usei o seguinte conjunto de peças:

Esses ladrilhos têm uma propriedade importante - todos os ladrilhos na base têm uma largura não inferior à do topo. Isso significa que não é possível construir esses blocos de maneira não suportada. O WFC responde imediatamente a isso e cria edifícios com uma boa base.

Aproximação de Fractal Split

Estudando o tópico de estimular certos comportamentos escolhendo o conjunto de peças apropriado, descobri que se o conjunto de peças consiste em estradas e galhos retos, mas sem cantos, é possível obter uma boa aproximação da divisão recursiva (sem a parte "recursiva"). Isso é muito bom para os níveis da grade.

Big tiles

Você pode adicionar o WFC para oferecer suporte a blocos que são várias vezes maiores que um bloco regular. Por exemplo, isso é suportado no meu complemento Tessera .

Ladrilhos grandes podem ser usados de várias maneiras. Como eles se estendem além dos limites da grade, você pode usá-los para adicionar curvas mais suaves e amplas do que normalmente é possível ao fazer snap na grade. Eles também são ótimos para elementos de um grande número de blocos, ou simplesmente para mascarar que a geração é baseada em blocos.

Aqui está um exemplo para aprender com Oscar Stalberg do jogo Bad North . Oscar demonstra como ele usou telhas grandes para adicionar costas curvas, casas grandes e variabilidade do penhasco.

Limitações

Na sua essência, o WFC é um algoritmo baseado em restrições. Isso significa que ele procura gerar níveis que correspondam a um conjunto específico de critérios. No WFC puro, há apenas um critério - que os níveis pareçam localmente como uma entrada de amostra. Abaixo, falarei sobre aprimoramentos do WFC para adicionar novos tipos de restrições.

Ladrilhos fixos

É muito fácil corrigir blocos individuais antes de gerar um nível no WFC. Mais tarde, eles se integram perfeitamente ao nível gerado.

Antes da geração

Após a geração

Esta técnica pode ser usada de várias maneiras diferentes. Aqui estão algumas idéias:

- , WFC .
,
/ WFC

Caminhos de limitação (restrição de caminho) - esta é minha própria contribuição para o WFC. Essa é uma técnica extremamente poderosa, mas um artigo completo provavelmente exigirá um artigo separado.

Essa restrição verifica globalmente toda a saída gerada e indica à força que um caminho deve passar entre os blocos marcados. Ou, em outras palavras, diz a um subconjunto de blocos para formar um único componente do gráfico . Devido à sua natureza global, ele complementa o comportamento usual do WFC, que leva em conta apenas os blocos locais.

Descobri que adicionar essa restrição afeta fortemente a aparência do nível gerado. Sem ele, o WFC geralmente gera várias salas ou áreas divididas que parecem irreais e não criadas por seres humanos.

. .

Outra situação em que a limitação do caminho é apropriada é ... desenhar caminhos. Por padrão, a restrição de caminho garante apenas a existência de uma rota entre blocos. Não garante que o caminho seja o mais simples possível. Portanto, no caso de rios e estradas, ele desenha juntas em forma de T em locais opcionais. O truque é simplesmente remover todos os ladrilhos das juntas em T ou dar-lhes um peso muito baixo, para que sejam selecionados apenas se for absolutamente necessário.

Adoro usar blocos fixos para corrigir os pontos finais de um caminho. Por esse motivo, a restrição de caminho é necessária para inserir blocos que conectam o restante do caminho.

Os caminhos gerados pela fixação de todos os quatro cantos como pontos finais dos caminhos

Se você quiser experimentar caminhos, tenho uma pequena demonstração em javascript que é apresentada aqui .

Diversidade

Azulejos alternativos

É muito fácil adicionar opções de mosaico ao algoritmo WFC. Basta adicionar os blocos à lista de possíveis blocos, fazendo com que ele tenha as mesmas conexões que o bloco que ele substitui. Ou pode ser feito no estágio de pós-processamento, como geralmente é feito em outros estilos de geração de procedimentos.

Dois azulejos, um deles com uma janela. Eles são completamente intercambiáveis e simplesmente adicionam variabilidade ao design.

Variabilidade do bloco por nível

Se você se esforçar bastante para criar um design de conjunto de peças, notará que a aleatoriedade do WFC começa a prejudicá-lo. Ele usa todo o conjunto de peças, ou seja, você pode obter um nível com lava, neve e deserto misturados. Muitas vezes isso parece completamente ilógico.

Você pode restaurar a integridade de uma maneira simples: decida com antecedência a qual bioma o nível pertencerá e, em seguida, desative todos os blocos que não são adequados para esse bioma.

Bad North (novamente) é um excelente exemplo disso. Em alguns níveis, as rochas são completamente proibidas, em outros há muita vegetação, nas terceiras ruínas e nos cemitérios são adicionados. Isso confere a cada nível um estilo único, sem a necessidade de uma mudança significativa no estilo de geração.

Apenas cerca de 10% das ilhas têm elementos de cavernas, visíveis no canto superior direito.

Variabilidade de blocos dentro do mapa

A mistura de conjuntos de peças pode ir ainda mais longe.

Se você usar o WFC para gerar um cartão grande, ele começará a parecer muito uniforme. Essa é outra conseqüência do fato de o algoritmo ser um solucionador de restrições locais .

A melhor solução para esse problema que eu vi no jogo Caves of Qud . Na história dos desenvolvedores sobre a geração ( 1 , 2 ), eles dizem que dividem o mapa em áreas diferentes e iniciam o WFC com parâmetros separados para os subconjuntos do mapa. Isso significa que no mapa pode haver uma área de ruínas e uma área de uma cidade na qual modelos e azulejos completamente diferentes são usados.

Exemplo de matemática para desenvolvedores de jogos: geração de mapa com base em blocos usando o colapso da função Wave em 'Caves of Qud'

Conclusão

O algoritmo WFC, como todas as técnicas de geração baseadas em restrições, tem o princípio de ser cuidadoso com seus desejos . É fácil personalizar e obter resultados com aparência bonita, mas pode ser muito difícil implementar os detalhes específicos necessários para o seu jogo.

Espero que as técnicas apresentadas por mim ajudem você a domesticar esse monstro, mas, no final, é melhor criar um design de jogo baseado nos pontos fortes da geração de procedimentos, e não tentar forçá-lo a criar demais para você.

Eu recomendo que você jogue Bad North e Caves of Qud . Ambos os jogos são ótimos exemplos de uso do WFC em condições reais, e os desenvolvedores pensaram bem no uso ideal do algoritmo em seus jogos.

Dicas para usar o algoritmo de recolhimento da função Wave