Lidamos com o algoritmo de colapso da função de onda

Desde o advento de DeBroglie e Tessera, fui solicitado muitas vezes a explicar como eles funcionam. Gerar pode parecer mágica, mas as regras por trás disso são realmente simples.

Então, qual é o algoritmo Wave Function Collapse (WFC)? Foi desenvolvido por Maxim Gumin para criar imagens "lado a lado" com base em uma configuração simples ou amostras de imagens. O algoritmo pode fazer muito: veja os exemplos fornecidos por Maxim e Twitter #wavefunctioncollapse , assista a este vídeo . A variedade é incrível.


Maxim no README explicou brevemente o trabalho do WFC, mas parece-me que esse problema exige uma divulgação mais detalhada, desde o básico. Como o algoritmo está relacionado à programação de restrições , a maior parte do artigo é dedicada a explicar o conceito de programação em restrições e, no final, retornaremos ao WFC .

A programação restrita é uma maneira de instruir os computadores. Diferentemente da programação imperativa, quando você especifica uma lista de funções explícitas, ou programação funcional, quando você especifica funções matemáticas, aqui você fornece ao computador uma descrição estrita do problema e ele usa os algoritmos internos para encontrar uma solução.

Nota:Este guia descreve vários conceitos, não métodos e código. Se você estiver mais interessado na implementação, poderá usar minha biblioteca de código-fonte WFC ( github , documentação ). Embora seja melhor iniciar o estudo com a implementação do Maxim . Se você usa o Unity, pode comprar o Tessera , esta é a minha ferramenta para aplicar o WFC neste mecanismo.

Mini sudoku

Como uma tarefa ilustrativa, peguei um mini Sudoku . Este é um quebra-cabeça que se parece com uma grade 4 × 4 com números em algumas células.


O objetivo é preencher cada célula vazia com um número de 1 a 4, de acordo com as regras:

• Cada número de 1 a 4 deve estar presente em cada linha em uma única cópia.
• Cada número de 1 a 4 deve estar presente em cada coluna em uma única cópia.
• Cada número de 1 a 4 deve estar presente em cada quadrado de canto 2 × 2 em uma única cópia.

De acordo com essas regras, a solução será a seguinte:


Você pode ter resolvido facilmente esse quebra-cabeça. Mas estamos interessados ​​em como um computador pode fazer isso. O problema pode ser dividido em duas partes: uma descrição das condições do computador e, em seguida, uma solução usando o algoritmo.

Descrição das condições

Normalmente, uma linguagem de programação com restrições é usada para isso. Existem várias dessas linguagens e seus princípios de ação são semelhantes.

Primeiro, definimos as variáveis . Aqui eles não são os mesmos da programação convencional. No contexto de um solucionador de problemas, uma variável é um valor desconhecido que deve ser resolvido para resolver um problema. No nosso exemplo de Sudoku, criaremos variáveis ​​para todas as células vazias. Por conveniência, você também pode criar variáveis ​​para células preenchidas.

Então, para cada variável, definimos um domínio : um conjunto de valores possíveis. No nosso sudoku, para cada célula vazia, o domínio será {1, 2, 3, 4}. E para uma célula na qual 1 já foi inserido, o domínio será {1}.

Por fim, definimos as restrições: regras que vinculam nossas variáveis. Na maioria das linguagens de programação, já existe uma função com restrições all_distinct(..)que precisa passar valores únicos. Portanto, as regras do Sudoku podem ser traduzidas em 12 restrições all_distinct- uma para cada linha e coluna, bem como para quadrados de canto 2 × 2. Precisamos de apenas um tipo de restrição para resolver esse problema; no entanto, os solucionadores de problemas para atender às restrições geralmente vêm com uma grande biblioteca de diferentes tipos de restrições para descrever seu problema.

Nota : na prática, as linguagens de programação suportam matrizes com restrições, portanto, existem maneiras mais precisas de formular esta tarefa. Existem muitos artigos na rede sobre como resolver o sudoku.

Algoritmos para resolver problemas de satisfação de restrições

Existem várias técnicas de solução diferentes. Mas vou considerar o mais simples deles para demonstrar a você o princípio de seu trabalho. Os domínios para cada célula são mostrados aqui:


Todos esses são valores possíveis em domínios variáveis.

Agora pegue a primeira limitação. Requer que todos os valores na linha superior sejam exclusivos. Em uma célula, o valor 4 já está inscrito; portanto, em outras células da série, esse valor não pode ser . Nós o removemos dos domínios dessas células.


Repita esse processo com todas as 12 restrições. Isso é chamado propagação de restrições , porque as informações são distribuídas de uma variável para outra por meio de restrições.


E veja, temos variáveis, nos domínios dos quais resta um valor. Essas devem ser as soluções corretas para essas variáveis.


Parece que podemos obter ainda mais benefícios com a distribuição de restrições: as novas unidades vermelhas indicam que teremos ainda mais variáveis ​​com um único domínio, e isso também contribuirá para a distribuição. Repita o procedimento até que o quebra-cabeça seja resolvido.

Nós complicamos a tarefa

Infelizmente, nem todos os quebra-cabeças lógicos podem ser resolvidos tão rapidamente. Aqui está um grande sudoku, que funciona da mesma maneira, exceto que agora temos 9 valores diferentes, 9 linhas, 9 colunas e 9 quadrados 3 × 3.


Se tentarmos aplicar a técnica acima, ficaremos presos:


Agora todas as restrições são comuns, mas ainda existem variáveis ​​indefinidas.

Uma pessoa decidirá isso, mas um algoritmo de computador não poderá. Os manuais para pessoas dizem que agora precisamos procurar conclusões lógicas cada vez mais complicadas. Mas não precisamos de um algoritmo de computador para fazer isso, porque é difícil, mas precisamos de um algoritmo universal que possa funcionar com qualquer conjunto de restrições, e não apenas de acordo com as regras do sudoku.

Portanto, os computadores fazem a coisa mais estúpida: eles assumem . Primeiro, registramos o estado atual do quebra-cabeça. Depois, selecionamos uma variável arbitrária e a definimos como um dos valores possíveis. Digamos que atribuímos o valor 1 à célula central.

Agora podemos espalhar um pouco mais as restrições. Aqui está o que eu consegui para a coluna central:


Os valores azuis são as conclusões que tiramos após a suposição. Como você pode ver, algo aconteceu. Colocamos mais algumas variáveis, mas observamos a célula superior média. Está vazio: em seu domínio não há valores possíveis que satisfaçam as restrições (não pode haver 5, porque esse valor já existe no mesmo quadrado 3 × 3 e todos os outros números já estão nesta coluna).

Se obtivermos uma variável com um domínio vazio, isso significa que não podemos atribuir nenhum valor a ela. Ou seja, o quebra-cabeça não pode ser resolvido. Acontece que nossa suposição foi errada .

Diante de tal contradição, realizamos o processo de busca de retorno(retrocesso). Primeiro, restauramos o estado que estava antes de nossa suposição. Em seguida, removemos do domínio o valor que usamos como suposição - ele não pode mais ser a resposta correta.


Muito trabalho foi feito, mas eles avançaram. No entanto, mesmo após a exclusão de 1 da célula central, ainda estamos em um ponto morto. É hora de fazer uma suposição novamente, e novamente, e novamente.

Não há muitas ações algorítmicas aqui. Sempre que não podemos distribuir restrições, assumimos e seguimos em frente. E como você pode ficar preso várias vezes antes de encontrar uma contradição, acumulará vários estados e suposições salvos.

Com cada iteração com um retorno, você reduz o domínio em pelo menos uma variável, para que, apesar de inúmeras reversões, o algoritmo acabe por concluir o trabalho.

Este tópico é muito mais extenso do que eu descrevo. Na prática, otimizações como a escolha de premissas, o entendimento de quando distribuir e quando tirar conclusões lógicas mais complexas podem ter um enorme impacto na execução do programa. E como os problemas com restrições, em regra, crescem exponencialmente, você pode obter uma resposta amanhã ou depois de 5000 anos.

Voltamos ao colapso da função de onda

O colapso da função de onda é uma tarefa complicada, com uma limitação: existem milhares de soluções possíveis. Se fizermos suposições aleatoriamente, em vez de um solucionador, obteremos um gerador . Ao mesmo tempo, ainda cumprirá todas as restrições fornecidas, ou seja, será muito mais gerenciável do que a maioria dos outros geradores de procedimentos.

A tarefa do algoritmo WFC é preencher células com blocos para que as imagens nos blocos sejam combinadas entre si. Dentro da terminologia usada acima, cada bloco é um valor, cada célula é uma variável e as regras para colocar blocos são restrições.

Maxim, o autor do WFC, descobriu que, com uma escolha razoável de blocos e uma randomização apropriada, você raramente precisa usar o retorno, portanto esse procedimento não pode ser implementado. Assim, a essência do WFC é a seguinte:

• Uma matriz booleana é criada para cada célula, que representa o domínio dessa variável. Os domínios contêm um registro por bloco e todos eles são inicializados com um valor true. Um bloco entra em um domínio se seu valor for igual true.
• Ao mesmo tempo, existem células nas quais os domínios contêm vários elementos:
  
  • Seleção de uma célula aleatória usando o método heurístico de "menor entropia".
  • Selecione um bloco aleatório no domínio da célula e remova todos os outros blocos de lá.
  • A atualização dos domínios de outras células com base nessas novas informações é a disseminação da restrição de células. Isso deve ser feito repetidamente, pois as alterações nas células podem ter consequências adicionais.

Nota : meus termos são diferentes dos termos de Maxim. Ele chama o conjunto de domínios de onda, e escolher um ladrilho aleatório é uma observação. Ou seja, uma analogia é desenhada com a mecânica quântica. Mas a comparação é superficial, então vamos ignorá-la.

Existem muitas adições aos princípios acima que adicionam graça e desempenho ao algoritmo. Mas vamos primeiro olhar para as etapas descritas.

Exemplo

Digamos que precisamos preencher uma grade 3 por 3 com quatro tipos de blocos:


As limitações são: as cores dos ladrilhos adjacentes devem coincidir.

Como no exemplo do Sudoku, ilustrarei o conteúdo dos domínios com imagens monocromáticas. Quando houver apenas um elemento no domínio, aumentarei em tamanho e mostrarei em cores.

Primeiro, em cada célula, blocos de qualquer tipo podem ser localizados:


Execute o loop WFC principal. Selecione aleatoriamente uma célula, por exemplo, no canto superior esquerdo. Agora selecione um bloco no domínio e exclua todos os outros.


Distribua as restrições. A única regra se aplica aos blocos adjacentes, portanto, precisamos atualizar duas células:


Podemos atualizar outros blocos devido aos domínios cada vez menores? Sim! Embora não tenhamos certeza sobre a escolha do primeiro bloco, vemos que as opções restantes levam à direita. Ou seja, alguns tipos de ladrilhos não podem ser colocados no canto superior direito. A mesma coisa com o canto inferior esquerdo.


Como não podemos mais distribuir as restrições, repetimos o ciclo principal: seleção de células, seleção e distribuição de blocos. Desta vez, pegamos a célula do meio superior:


Outro ciclo: pegue a célula do meio esquerda. Após a proliferação de restrições para a célula central, um possível valor permanece.


Em geral, você entende a ideia. Você pode preencher o resto das células você mesmo.

Se você quiser experimentar um exemplo interativo mais complexo , recomendo este .

Menor entropia

Ao escolher a próxima célula a ser preenchida, algumas opções serão preferíveis. Se você escolher aleatoriamente de qualquer lugar da grade, poderá ocorrer uma situação em que ao mesmo tempo você terá áreas diferentes da grade preenchidas. Isso pode causar problemas: dependendo dos ladrilhos disponíveis, as áreas preenchidas não podem ser unidas. Portanto, é melhor escolher células com menor probabilidade de levar a esses problemas no futuro. Em outras palavras, você precisa obter células com o menor número possível de valores no domínio (mas não menos que dois valores):

1. Provavelmente, eles estarão ao lado das células já preenchidas.
2. Se os deixarmos para o futuro, poderão surgir dificuldades, porque os valores disponíveis já são poucos.

A abordagem de domínio menor funciona bem se todos os blocos forem igualmente prováveis. Mas se você escolher entre uma distribuição aleatória ponderada , precisará considerar outra coisa. Maxima recomenda “entropia mínima”, ou seja, escolha uma célula que minimize:

$$

$$entropy = — \sum p_{i}log(p_{i})$$

Este é um somatório de blocos no domínio em que $$$p_{i}$- probabilidade para esse bloco.

Computação eficiente

Embora eu não queira entrar em detalhes, no entanto, existem duas otimizações que me permitem aumentar a velocidade tanto que não podem ser ignoradas.

Como nossa única regra está relacionada a blocos adjacentes, só podemos verificar as restrições que podem fornecer resultados diferentes dos anteriores. Ou seja, ao atualizar uma célula, a adicionamos à fila de células que aguardam uma decisão. Em seguida, removemos uma célula da fila, sempre verificando suas células adjacentes. Se essas verificações levarem à renovação de outras células, elas também cairão na fila. Repetindo esse procedimento até que a fila esteja vazia, garantimos que verifiquemos todas as restrições. Mas não as verificamos até que o domínio de pelo menos uma célula associada a essas restrições seja alterado.

Além disso, para verificar a restrição de adjacência, precisamos responder à pergunta: “Dados os blocos no domínio da célula A, quais blocos são possíveis no domínio da célula B se as células forem adjacentes?”

Às vezes, essa pergunta é chamada de "suporte" da célula A. Para um determinado bloco "b" no domínio B, é fácil calcular os ciclos dos blocos no domínio A. Se A tiver pelo menos um bloco que pode ser colocado ao lado de "b", então "b" ainda adequado, pelo menos para o par de peças em questão. Se em A não houver esse bloco, não será possível colocar o bloco "b" no domínio B, e podemos descartá-lo.

Os loops facilitam a implementação disso no código, mas funcionarão extremamente lentamente. E se armazenarmos informações em uma estrutura de dados adicional, poderemos responder rapidamente à pergunta conforme necessário. Os novos dados são uma matriz grande com entradas para cada lado de cada célula e cada bloco. No nosso exemplo, existem 9 células, cada uma com 4 lados e 4 tipos de blocos. Então, precisamos de 9 * 4 * 4 registros. Salvaremos os contadores de suporte na matriz: para cada célula / bloco / lado, contamos o número de blocos no domínio da célula adjacente que pode ser colocado próximo ao bloco em questão. Se o contador cair para zero, esse bloco não poderá ser colocado, porque ninguém poderá ficar adjacente a ele.

Extensões de algoritmo

Como o WFC se baseia em um entendimento mais geral dos problemas restritos, existem muitas maneiras de estender o algoritmo alterando as restrições usadas.

Uma das mudanças óbvias é que ninguém nos obriga a usar células quadradas. O WFC funciona muito bem em células hexagonais, em três dimensões ou em superfícies ainda mais incomuns .




Você pode introduzir restrições adicionais: consertar determinados blocos ou criar "módulos" a partir de várias células.

A introdução de restrições adicionais pode desempenhar um papel muito importante do ponto de vista prático. Como o WFC limita apenas blocos adjacentes, raramente gera grandes estruturas que fornecem um alto nível de homogeneidade e parecem incomuns. Esse algoritmo funciona melhor na escolha de blocos, mas para trabalhar com algumas estruturas grandes, é melhor usar uma técnica diferente ou introduzir outras restrições.

Em outro artigo, falei sobre como você pode obter os melhores resultados do WFC.

Sobreposição de WFC

Uma das extensões interessantes do algoritmo é o WFC "sobreposto". Nos exemplos acima, a principal limitação estava relacionada a pares de peças adjacentes. Isso é suficiente para garantir a conexão das linhas e criar estruturas simples como cavernas, salas etc. Mas, ao mesmo tempo, muita informação é perdida. Se precisarmos, digamos, que os ladrilhos vermelhos estejam sempre localizados ao lado do azul, mas nunca foram adjacentes a eles, será difícil expressar isso apenas em termos de contiguidade.

Maxim propôs o conceito de sobreposição de WFC: substituímos a restrição de adjacência por uma nova restrição que afeta vários blocos ao mesmo tempo. Por exemplo, para que na saída cada grupo de células 3 × 3 corresponda a um grupo 3 × 3 de uma amostra de grade. Os padrões presentes na amostra serão repetidos repetidamente em diferentes variações na saída:


Essa restrição é muito mais sensível que as restrições de adjacência "simples". E, como depende de uma amostra, é muito adequado para resolver algum tipo de tarefa artística. Até agora, não encontrei nada tão interessante. Talvez a razão seja que esse algoritmo seja mais difícil de implementar, ou funcione mais devagar, ou às vezes reproduza muito bem a amostra original, o que causa a perda de algum tipo de naturalidade e naturalidade.

Qual é o próximo?

A solução de problemas com restrições é um campo amplo e em desenvolvimento ativo da ciência da computação, e eu apenas o toquei. O WFC - como qualquer outro algoritmo de geração de procedimentos para resolver problemas restritos - ainda é novo. Eu recomendo a leitura de r / proceduralgeneration , #wavefunctioncollapse , @exutumno e @osksta para ter uma idéia dos casos de uso recentes.

Você também pode ler meu artigo sobre o WFC , experimentar minha biblioteca de código-fonte aberto ou a ferramenta Unity . Não se esqueça dos meus outros artigos sobre geração de procedimentos .