Colapso da função de onda: um algoritmo inspirado na mecânica quântica

O algoritmo Wave Function Collapse gera bitmaps localmente semelhantes ao bitmap de entrada.

Aparência local significa que

• (C1) Cada padrão de pixels NxN na saída deve ocorrer pelo menos uma vez na entrada.
• (Condição fraca C2) A distribuição dos padrões NxN na entrada deve ser semelhante à distribuição dos padrões NxN em um número significativamente grande de conjuntos de saída. Em outras palavras, a probabilidade de um certo encontro de padrões na saída deve estar próxima da densidade de tais padrões na entrada.

Nos exemplos, o valor padrão de N é 3.


O algoritmo WaveFunctionCollapse (WFC) inicializa o bitmap de saída como um estado completamente não observável, no qual o valor de cada pixel é uma superposição das cores do bitmap de entrada (por isso, se a imagem de entrada for em preto e branco, os estados não observáveis ​​serão exibidos em diferentes tons de cinza). Os coeficientes dessas superposições são reais, não números imaginários; portanto, o algoritmo não usa mecânica quântica real, mas foi inspirado por ele. Em seguida, o programa entra no ciclo de observação-propagação:

• Em cada estágio de observação, entre o espaço não observado, a região NxN com a menor entropia de Shannon é selecionada. O estado dessa região entra em colapso para um estado de certeza, de acordo com os coeficientes e a distribuição dos padrões NxN nos dados de entrada.
• Em cada estágio da distribuição, novas informações obtidas durante o colapso do estágio anterior são disseminadas de acordo com o resultado.

Em cada estágio, a entropia total diminui e, no final, obtemos um estado completamente observável, o colapso da função de onda termina.

Pode acontecer que, durante o processo de propagação, todos os coeficientes de um pixel específico sejam iguais a zero. Isso significa que o algoritmo chegou a uma contradição e não pode ser executado mais. A tarefa de determinar se um determinado bitmap fornece outros bitmaps não triviais que satisfazem a condição (C1) é NP-difícil, portanto, é impossível criar uma solução rápida que sempre complete o algoritmo. No entanto, na prática, o algoritmo encontra contradições surpreendentemente raramente.

O algoritmo de colapso da função de onda é implementado em C ++ , Python , Kotlin , Rust , Julia , Haxe , JavaScript e adaptado para Unity . Arquivos executáveis ​​oficiais podem ser baixados do itch.io ou executados em um navegador . O WFC gera níveis em Bad North , Caves of Qud , vários jogos menores , além de muitos protótipos. Sua criação levou a um novo estudo . Para outros trabalhos relacionados , explicações , demonstrações interativas , guias , tutoriais e exemplos, consulte a seção de portas, bifurcações e derivações .

Assista a uma demonstração do algoritmo WFC no YouTube: https://youtu.be/DOQTr2Xmlz0

Algoritmo

1. Leia o bitmap recebido e conte o número de padrões NxN.
   
   1. (opcional) Complemente os dados do padrão com padrões girados e refletidos.
2. Crie uma matriz com os tamanhos dos dados de saída (chamados de "onda" na fonte). Cada elemento dessa matriz indica o estado de uma região de tamanho NxN na saída. O estado da região NxN é uma superposição de padrões NxN de dados de entrada com coeficientes booleanos (ou seja, o estado de um pixel na saída é uma superposição de cores recebidas com coeficientes reais). O coeficiente False significa que o padrão correspondente é proibido, o coeficiente true significa que o padrão correspondente ainda não é proibido.
3. Inicialize a onda em um estado completamente não observável, ou seja, onde todos os coeficientes booleanos são verdadeiros.
4. Repita as seguintes etapas:
   
   1. Observação:
      
      1. Encontre o elemento onda com entropia mínima diferente de zero. Se não houver tais elementos (se todos os elementos tiverem entropia zero ou indefinido), conclua o ciclo (4) e vá para a etapa (5).
      2. Recolha este elemento em um estado de certeza de acordo com seus coeficientes e a distribuição dos padrões NxN dos dados de entrada.
   2. Divulgação: disseminar as informações obtidas na etapa de observação anterior.
5. Nesse ponto, todos os elementos da onda têm um estado totalmente observável (todos os coeficientes, exceto um, são iguais a zero) ou estão em estado de contradição (todos os coeficientes são zero). No primeiro caso, retorne a saída. No segundo caso, saia sem retornar nada.

Geração de cartão lado a lado

O caso não trivial mais simples do algoritmo é o padrão NxN = 1x2 (mais precisamente, NxM). Se simplificarmos ainda mais, preservando não as probabilidades dos pares de cores, mas as probabilidades das próprias cores, obteremos o que é chamado de "modelo simples de ladrilhos". A fase de propagação neste modelo é simplesmente a propagação de uma dependência de vizinhança. É conveniente inicializar um modelo de bloco simples com uma lista de blocos e seus dados de vizinhança (dados de vizinhança podem ser considerados como um grande número de amostras muito pequenas), em vez de um bitmap de amostra.

GIF | GIFV

As listas de todos os pares possíveis de peças vizinhas em conjuntos de peças práticas podem ser bastante longas; portanto, para encurtar a enumeração, implementei um sistema de simetria para peças. Nesse sistema, cada bloco deve receber seu tipo de simetria.


Observe que os ladrilhos têm a mesma simetria que as letras atribuídas a eles (em outras palavras, as ações do grupo diédro D4 são isométricas para os ladrilhos e as letras correspondentes). Graças a esse sistema, basta listar os pares de ladrilhos vizinhos apenas por sua simetria, reduz a lista de vizinhos de conjuntos de ladrilhos com muitos ladrilhos simétricos várias vezes (mesmo nos ladrilhos do terreno de verão, apesar de as figuras não serem simétricas, o sistema considera simétricos).









Observe que um conjunto ilimitado de blocos de nós (nos quais todos os 5 blocos são válidos) não é interessante para o algoritmo WFC, porque você não pode entrar em uma situação em que é impossível colocar um bloco. Chamamos de tilesets com essa propriedade de "simples". Sem heurísticas complexas, conjuntos de blocos simples não criam estruturas globais interessantes, porque as correlações em conjuntos de blocos simples à distância diminuem rapidamente. Muitos blocos simples podem ser encontrados em cr31 . Veja lá o conjunto de peças dupla "Dual". Como ele pode criar nós (sem conexões em forma de T, isto é, difícil) e, ao mesmo tempo, ser simples? A resposta é que ele pode gerar apenas um tipo restrito de nós e não pode criar um nó arbitrário.

Também é importante notar que os conjuntos de peças Circuit, Summer e Rooms não são peças Van. Ou seja, os dados de sua vizinhança não podem ser gerados a partir da coloração das bordas. Por exemplo, no conjunto de placas de circuito (circuito integrado), dois cantos não podem ser adjacentes, embora possam ser conectados a uma conexão (Conexão), e as faixas diagonais não podem mudar de direção.

Dimensões mais altas

O algoritmo WFC em dimensões mais altas funciona exatamente da mesma forma que em duas dimensões, mas o desempenho se torna um problema aqui. Esses modelos de voxel foram gerados em N = 2 no modelo de ladrilhos com sobreposição usando blocos 5x5x5 e 5x5x2 e heurísticas adicionais (alturas, densidades, curvaturas ...).


Capturas de tela de dimensões mais altas: 1 , 2 , 3 .

Os modelos Voxel gerados usando o WFC e outros algoritmos estarão em um repositório separado.

Síntese Restrita

O algoritmo WFC suporta restrições. Portanto, ele pode ser facilmente combinado com outros algoritmos generativos ou criação manual.

Veja como o WFC conclui automaticamente um nível iniciado por pessoa:

GIF | GIFV

O algoritmo ConvChain satisfaz a versão estrita da condição (C2): a distribuição dos limites dos padrões NxN nos dados de saída criados é exatamente igual à distribuição dos padrões nos dados de entrada. No entanto, o ConvChain não satisfaz (C1): geralmente cria artefatos visíveis. É lógico iniciar o ConvChain primeiro para obter uma configuração bem amostrada e, em seguida, o WFC para corrigir artefatos locais. Isso é semelhante a uma estratégia comum em otimização: primeiro, executamos o método Monte Carlo para encontrar o ponto. próximo ao ideal global e, em seguida, execute a descida do gradiente a partir deste ponto para obter maior precisão.

O algoritmo de síntese de textura de P.F. Harrison é muito mais rápido que o WFC, mas tem problemas com longas correlações (por exemplo, esse algoritmo é difícil de sintetizar texturas de paredes de tijolos com tijolos construídos corretamente). É nesses casos que o WFC demonstra sua superioridade e o algoritmo de Harrison suporta limitações. Faz sentido primeiro gerar o esquema ideal da parede de tijolos usando o WFC e depois executar um algoritmo de síntese de textura limitado para esse esquema.

Comentários

Por que a heurística de entropia mínima é usada? Percebi que, quando as pessoas desenham algo, geralmente seguem a heurística da entropia mínima. É por isso que o algoritmo é tão interessante de assistir.

O modelo sobreposto corresponde a um modelo simples, da mesma maneira que cadeias de Markov de alta ordem correspondem a cadeias de Markov de primeira ordem.

Deve-se notar que a entropia de qualquer nó não pode aumentar no estágio de propagação, ou seja, as probabilidades não aumentam, mas podem ser redefinidas para zero. Quando o estágio de propagação não pode reduzir ainda mais a entropia, ativamos o estágio de observação. Se o estágio de observação não puder reduzir a entropia, isso significa que o algoritmo terminou o trabalho.

A fase de propagação no algoritmo WFC é muito semelhante ao algoritmo de propagação de crenças em loop. Na verdade, originalmente programei a propagação de crenças (BP), mas depois mudei para a propagação com restrições com uma distribuição fixa fixa, porque a BP é muito mais lenta sem paralelização maciça (na CPU) e não produziu resultados significativamente melhores para minhas tarefas.

Observe que as amostras “Nó Simples” e “Nó Truque” não possuem 2, mas 3 cores.

Uma dimensão pode ser o tempo. Em particular, o WFC tridimensional exibe o comportamento de qualquer autômato celular dimensional (d-1).

Referências

Este projeto baseia-se no trabalho de Paul Merrell na síntese de modelos, em particular no capítulo sobre síntese discreta de modelos de sua dissertação . Paul espalha as limitações da vizinhança no que chamamos de modelo simples de ladrilhos, com uma heurística que procura calcular a propagação em uma pequena área móvel.

Meu projeto também foi fortemente influenciado pelo capítulo sobre síntese declarativa de texturas da dissertação de Paul F. Harrison . Paul define os dados na vizinhança de blocos, marcando seus limites e usando a pesquisa de retorno para preencher o mapa de blocos.

Assembléia

O WFC é um aplicativo de console que depende apenas da biblioteca padrão. Faça o download do .NET Core para Windows, Linux ou macOS e execute

 dotnet run WaveFunctionCollapse.csproj 

Ou você pode usar as instruções de construção da comunidade para diferentes plataformas na edição correspondente . Casey Marshall criou uma solicitação pull que simplifica o uso de um programa de linha de comando e inclui um pacote de snap.

Portos, garfos e spin-offs interessantes

• Emil Ernerfeld criou uma porta em C ++ .
• Max Eller criou a Biblioteca Kotlin (JVM) chamada Kollapse . Joseph Roscopf criou uma porta linha a porta na versão otimizada do Kotlin do algoritmo de 2018. Edwin Jacobs criou outra biblioteca Kotlin .
• Kevin Chapelier criou uma porta em JavaScript .
• Oscar Stalberg programou um modelo tridimensional de ladrilhos, um modelo bidimensional de ladrilhos para grades irregulares em uma esfera. Aqui estão os belos conjuntos de peças 3D para eles: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 .
• Joseph Parker adaptou o WFC para Unity e o usou para gerar parques de skate no jogo Proc Skater 2016 , fantásticos planaltos nos níveis de jogo e plataforma Swapland 2017 no Bug 2018 com um jogo Gun de 2018.
• Martin O'Leary aplicou um algoritmo semelhante ao WFC para gerar poesia: 1 , 2 , 3 , 4 .
• Nick Nenov criou um tileset tridimensional de voxel com base no meu tileset Castle. Nick usa a opção de saída de texto no modelo de ladrilho para recriar modelos 3D no Cinema 4D.
• Sean Lefler implementou um modelo com uma sobreposição no Rust .
• rid5x cria uma versão do WFC no OCaml .
• Publiquei um modelo simples de blocos tridimensionais para que as pessoas possam criar seus próprios conjuntos de blocos 3D sem esperar por um repositório completo de um algoritmo tridimensional.
• Eu criei um modelo interativo do modelo sobreposto. O executável da GUI pode ser baixado das páginas do WFC em itch.io.
• Brian Buckley montou um pipeline de geração de nível para o jogo Caves of Qud , que usa o WFC em várias passagens: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 .
• Danny Wine implementou um modelo tridimensional de ladrilhos .
• Arvi Teikari programou um algoritmo de síntese de textura heurística de entropia em Lua. Headchant portou para trabalhar com LÖVE.
• Isaac Curt criou uma porta no modelo Python com sobreposição.
• Oscar Stalberg criou uma versão interativa do modelo de bloco que é executado no navegador.
• Matt Ricks implementou um modelo tridimensional de ladrilhos ( 1 , 2 , 3 , 4 ) e criou um modelo tridimensional de ladrilhos no qual uma das dimensões é o tempo ( 1 , 2 , 3 , 4 , 5 ).
• Nick Nenov criou um guia visual para o sistema de simetria de ladrilhos.
• Isaac Curt e Adam M. Smith escreveram um artigo de pesquisa no qual formulam o WFC como um problema ASP, usam o resolvedor de restrições gerais clingo generalizado para gerar bitmaps, experimentar com restrições globais, rastrear o histórico do WFC e fornecer uma descrição detalhada do algoritmo.
• Sylvain Lefebvre criou uma implementação em C ++ da síntese de modelos tridimensionais, descreveu o processo de criação de uma amostra e mostrou um exemplo em que as restrições de vizinhança garantem que a saída esteja conectada (você pode ignorá-la).
• Eu generalizei o WFC tridimensional para que ele funcione com o grupo de simetria de cubos e crie um conjunto de peças geradoras de cenas no estilo de Escher .
• Existem várias maneiras de visualizar estados de onda parcialmente observáveis. No código, os valores de cores das opções possíveis são calculados para obter a cor final. Oscar Stalberg mostra estados parcialmente observáveis ​​como retângulos translúcidos: quanto mais opções, maior o retângulo. Em um esquema de voxel, visualizo os estados de onda por votação pixel por pixel.
• Remy Devo implementou o modelo de bloco no PICO-8 e escreveu um artigo sobre geração de dados coerente com uma explicação do WFC.
• Para o seu jogo Bad North, Oscar Stalberg usa uma heurística que tenta selecionar esses ladrilhos para que em cada estágio a zona observada resultante seja aceitável.
• William Manning implementou um modelo sobreposto em C #; Primeiro, ele procurou tornar o código legível e complementou o WPF com uma interface gráfica.
• Joseph Parker escreveu um tutorial do WFC para o Procjam 2017.
• Aman Tiwari formulou a restrição de conexão como uma tarefa ASP para o clingo.
• O MatveyK programou um modelo tridimensional com sobreposição .
• Silvan Lefebvre , Lee Yu Wei e Connelly Barnes estão explorando a possibilidade de ocultar informações dentro de texturas. Eles criaram uma ferramenta que pode codificar mensagens de texto como blocos WFC e decodificá-las novamente. Essa técnica permite o uso de blocos WFC como códigos QR.
• Mathieu Fer e Nathaniel Kuran melhoraram significativamente o tempo de execução do WFC, para um modelo sobreposto por uma ordem de magnitude. Eu integrei seus aprimoramentos no código.
• Vasu Mahesh portou o modelo de bloco 3D para o TypeScript, criou um novo conjunto de blocos e visualizou o processo de geração no WebGL.
• Kim Huanghee experimentou o WFC tridimensional e criou / adaptou muitos conjuntos de voxel: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 .
• Oscar Stalberg fez uma apresentação sobre geração de nível em Bad North na Everything Procedural Conference 2018.
• Eu escrevi sobre como gerar (aproximadamente) caminhos não distorcidos entre dois pontos usando o WFC e outros algoritmos.
• Aiser Curt e Adam M. Smith publicaram uma pré - impressão descrevendo o sistema baseado no WFC, que aprende com exemplos positivos e negativos, e falou sobre isso no contexto geral de diálogos com geradores de amostras.
• Brandan Anthony usa o WFC para gerar decorações de parede em Rodina .
• Tim Kong implementou um modelo sobreposto no Haxe .
• Boris, o Bravo, aplicou o método de cinzelamento ao WFC para gerar estruturas conectadas. Ele publicou uma biblioteca que suporta malhas hexagonais, restrições adicionais e backtracking.
• Marian Kleineberg criou para o Procjam 2018 um gerador de cidades baseado no modelo de ladrilhos. Ele escreveu um artigo descrevendo suas abordagens para definir o bairro, voltar e variações on-line do WFC.
• Sol Bekic programou um modelo de bloco baseado em GPU usando PyOpenCL. Em vez de armazenar uma fila de nós a partir da qual a distribuição é realizada, esse modelo executa simultaneamente a distribuição de cada nó da grade.
• Wouter van Oortmerssen implementou o modelo de bloco em uma única função C ++ com uma estrutura para acelerar a observação, semelhante a uma fila de prioridade.
• Robert Hoenig implementou um modelo com sobreposição em Julia, com a opção de distribuir restrições apenas localmente.
• Edwin Jacobs aplicou o WFC ao estilo de transferência e pontilhamento .

Agradecimentos

Alguns exemplos são extraídos dos jogos Ultima IV e Dungeon Crawl . Círculos de Tileset retirados de Mario Klingemann . A idéia de gerar circuitos integrados foi proposta por Moonasaur , e seu estilo foi retirado do jogo Ruckingenur II pela Zachtronics. O exemplo de sobreposição de gato é retirado do vídeo Nyan Cat, o exemplo de Qud foi criado por Brian Buckley , os exemplos de Magic Office + Spirals são rid5x, os exemplos de sobreposições Cidade colorida + Link + Link 2 + Mazelike + Red Dot + Smile City são Arvi Teikari. O verão Tileset foi criado por Hermann Hillmann. Os modelos Voxel são renderizados no MagicaVoxel .