Algoritmo do Colapso da Função de Onda

Em 2016, foi criado por Maxim Gummin um algoritmo que se baseia no comportamento da física quântica, mais especificamente, no fenômeno do colapso da função de onda. Antes de explicar o funcionamento do algoritmo em si e suas aplicações, seria interessante abordamos de forma breve o fenômeno do colapso da função de onda.

O fenômeno do colapso da função de onda

A mecânica quântica, área da física que investiga o comportamento de objetos sub-atômicos, estipula, em uma de suas principais interpretações, que sistemas quânticos estão em um estado de superposição, no qual vários estados individuais coexistem. Quando alguma medição ocorre em um sistema quântico, sua função de onda entraria em colapso e o sistema convergiria em um único estado definido, como pode ser visto nas figuras abaixo.

O algoritmo do colapso da função de onda

Chamado em sua versão original de Wave Function Colapse Algorithm (WFC), esse algoritmo utiliza princípios da superposição e o colapso da função de onda com a finalidade principal de realizar a geração procedural de imagens, soluções de problemas, mapas de videogames e estruturas complexas a partir de inputs arquetípicos ou “modelo”. Se eu fosse definir de forma geral e resumida o funcionamento desse algoritmo, diria que ele é usado em problemas onde várias combinações diferentes de elementos constituem soluções válidas para o problema, e à medida que um elemento é escolhido para constituir a solução, isso restringe a escolha de outros elementos para constituir a solução global, de acordo com regras pré-estabelecidas. Vejamos alguns exemplos para melhor entender esse conceito.

Resolvendo um jogo de Sudoku

Sudoku é um jogo lógico em que há um ‘tabuleiro’ de N x N quadrados, ou seja, um jogo onde há um quadrado com 4, 9, 16 ou qualquer número de quadrados ao quadrado. O objetivo desse jogo é completar os quadrados em branco com número que vão de 1 ao número da largura ou altura do quadro, como pode ser observado abaixo.

No caso do exemplo acima, temos que completar os quadrados em branco com números de 1 a 4 (já que o ‘tabuleiro’ é 4 x 4). Porém, existem algumas regras para compeltar os quadraos:

1- O números não podem se repetir em nenhuma linha

2 – Os números não podem se repetir em nenhuma coluna

3-Os números não podem se repetir nos “sub-quadrados” dos cantos

A princípio, podemos colocar todos os valores possíveis ao mesmo tempo nos quadrados não-preenchidos. Isso representa a função de onda desses quadrados.

Se aplicarmos todas as restrições, isto é:

1-de não repetir os números nas linhas

2-de não repetir os números nas colunas

3-de não repetir os números em cada 1/4 (1/N) do quadro maior (total)

Teremos as seguintes opções para cada quadrado em branco

Esse processo de restrições evidencia o colapso da função de onda do problema. No início, nossa função de onda compreende os números de 1 a 4, e à medida em que vamos propagando as restrições de escolha de acordo com as regras do problema, causamos o colapso da função de onda (veja a figura acima).

Nesse último caso, podemos perceber que em alguns quadrados, apenas um número (neste caso, o 1) sobrou. Nós devemos então estabelecer esse número como a escolha para esses quadrados. Com novos números adicionados e menos quadrados sobrando, devemos repetir o processo de propagação das restrições até que nenhum quadrado indeterminado esteja sobrando. Nos casos em que nenhum quadrado com apenas um número foi gerado, basta escolher aleatoriamente um número disponível e propagar as restrições a partir da escolha, até que não restem mais quadrados indeterminados.

Geração procedural de paisagens

Outra aplicação bem interessante que pode ser feita com esse algoritmo é a geração de paisagens. Nesse caso, cada paisagem é constituída de blocos ou peças diferentes, como na figura abaixo.

O exemplo mais clássico é uma paisagem onde temos costa, vegetação e água. Essas três peças diferentes possuem regras de vizinhança entre si, vejamos:

1-Água só pode estar ao lado de costa ou água

2-Costa pode estar ao lado de vegetação e mar, e costa

3- Vegetação pode estar ao lado de vegetação e costa

Vamos começar por uma paisagem que possui 100 peças (10 x 10). Se nenhum bloco da paisagem está preenchido, então a função de onda de cada peça possui três paisagens (mar, mata e costa)

Se escolhermos um bloco aleatório da paisagem e definirmos ele como sendo, por exemplo, mata, ele causa restrições que se propagam para seus vizinhos adjacentes

Na imagem acima, podemos observar a propagação da restrição para os blocos adjacentes. Como mata não pode ter contato direto com mar, essa opção desparece dos blocos vizinhos.

Após várias rodadas desse procedimento, o algoritmo deve ser capaz de gerar imagens como esta acima. Devemos ter em mente que esse exemplo em específico é bastante simples, e é possível haver implementações muito mais complexas, levando em consideração:

1- Tipos adicionais de blocos (nesse caso, montanha, lago, casas, etc)

2- Blocos compostos ou com formato não quadrangular

3-A frequência com que cada bloco aparece que em paisagens ‘modelo’, para gerar ‘pesos’ e produzir vieses na escolha dos blocos pelo algoritmos, gerando paisagens mais realistas

4-Paisagens tridimensionais tem que considerar uma terceira dimensão de blocos.

5- Um sistema de backtracking para tentar outras escolhas aleatórias caso a algoritmo caia em uma situação de contradição. Uma contradição é uma situação em que nenhuma escolha de elemento (peça de paisagem ou núemro, no caso do sudoku) é possível devido as restrições das regras. Sendo assim, o sistema deve desfazer a escolha que gerou a contradição e escolher outra opção.

6-Um mesmo bloco pode ter regras mais complexas, como quais lados podem fazer contato com quais outros blocos e em quais ordens