Algoritmo de posicionamento de bloco baseado em restrições

Esta publicação descreve o algoritmo usado no Generate Worlds , uma ferramenta que permite aos usuários criar e explorar mundos procedimentais criando pequenos conjuntos de blocos de voxel. Vou dar uma breve descrição do algoritmo e, nos posts seguintes, falarei sobre suas vantagens em velocidade e flexibilidade em comparação com outros métodos. Para saber mais sobre o que é a geração de procedimentos com base em restrições e o que é interessante, recomendo a leitura da minha postagem anterior .

Se você deseja testar seus pontos fortes na criação de mundos procedimentais usando esse sistema, pode comprar Generate Worlds. Se o preço for alto demais para você, continue lendo: este post fornecerá informações sobre como implementar independentemente o algoritmo Generate Worlds.

Conjuntos de peças

Em Gerar Mundos, cada mundo é montado a partir de um conjunto de peças ( conjunto de peças ). Em essência, os azulejos são apenas pequenos modelos de voxel. Vamos começar com um exemplo. A imagem abaixo é composta por 9 peças. Como você pode ver, cada bloco consiste em voxels que aparecem como cubos coloridos.


Se você organizar esses modelos de voxel de maneira lógica, poderá criar uma bela cena pastoral, como na animação abaixo. Por "lógica", quero dizer que os ladrilhos se encaixam se suas cores ao longo da borda da junta combinam.


A tarefa do algoritmo Generate Worlds é concluir rápida e automaticamente essa montagem. Antes de embarcar no algoritmo, vejamos a declaração do problema.

Nós conectamos telhas entre si

Dê uma olhada no conjunto de peças contendo 4 peças:


Essas peças são semelhantes às peças tridimensionais mostradas acima.

O algoritmo Generate Worlds cria combinações válidas de ladrilhos usando uma regra simples: se dois ladrilhos se tocam, todas as cores ao longo da borda do toque devem corresponder . Esta regra formaliza a abordagem usada por um designer vivo para criar um mundo 3D a partir de ladrilhos voxel.

Em uma combinação permitida dos 4 blocos apresentados acima, as células claras ao longo das bordas devem tocar apenas as células claras e uma célula escura deve tocar apenas as células escuras. Por exemplo:


Exemplos de conexões corretas e incorretas.

O exemplo à direita é inaceitável, porque ao longo da borda do toque do ladrilho, o quadrado claro toca o quadrado escuro. Duas combinações válidas geradas para este conjunto de peças são mostradas abaixo:


No caso geral, a criação de combinações válidas de blocos não é uma tarefa trivial. Por exemplo, considere a seguinte estratégia simples "gananciosa": começamos com uma grade vazia. Em cada iteração, colocamos o bloco em algum momento, escolhendo um bloco aceitável, considerando os blocos já colocados. O diagrama abaixo mostra os problemas dessa estratégia.


Se colocarmos blocos sem prever como a veiculação afetará as escolhas futuras, o algoritmo "ganancioso" rapidamente pára; no diagrama acima, nenhum bloco válido pode ser colocado no quadrado vermelho. E este é o principal problema: os blocos postados anteriormente podem reduzir o número de opções atuais para zero. Precisamos de alguma maneira de proteger contra a colocação de ladrilhos, o que pode nos levar a um beco sem saída. O algoritmo implementado em Generate Worlds começa considerando todos os blocos possíveis para colocar em todos os pontos da grade. Se colocarmos um bloco na grade, é óbvio que algumas das opções futuras se tornam inacessíveis. Depois que o algoritmo elimina essas opções, podemos reexaminar as opções restantes e eliminar outros blocos que agora são incompatíveis com o menor número possível de blocos restantes em pontos vizinhos.

Considere o seguinte exemplo. O algoritmo começa com uma grade 3x3, no centro da qual existe um único bloco. A localização desse bloco implica que 9 blocos possíveis em pontos de grade vizinhos não são permitidos, portanto ele os descarta e não os considera mais. Após excluir esses blocos, ele pode excluir blocos incompatíveis com todos os blocos considerados candidatos para posicionamento em pontos de grade vizinhos. Os quadrados vermelhos no diagrama marcam os pontos nos quais os blocos são excluídos, porque são incompatíveis com todos os vizinhos que ainda estão sendo considerados. Se o algoritmo continuar esse processo até que haja blocos que possam ser excluídos, ele retornará ao estado mostrado no canto inferior esquerdo do circuito. Como você pode ver, muitos blocos foram excluídos de consideração. Se a estratégia de colocação de peças consistisse apenas na seleção de peças dos grupos restantes, a probabilidade de chegar a um beco sem saída seria muito menor do que na abordagem “gananciosa” descrita acima.


O problema dessa abordagem é que, toda vez que um bloco é colocado, é necessário um processo iterativo caro. Mas observe que toda vez que coloco um bloco com um T invertido, os 19 blocos removidos no exemplo acima podem ser removidos de consideração em torno desse canal. Eu chamo a coleção de blocos, que permanecem opções válidas em torno do bloco hospedado, uma vizinhança válida desse bloco.

Colocação rápida de blocos graças ao cache de informações

O princípio mais importante do algoritmo Generate Worlds é que as informações coletadas sobre possíveis vizinhos de bloco podem ser reutilizadas toda vez que esse bloco é colocado. Por exemplo, no caso de um T invertido para os oito quadrados circundantes da grade, podemos remover 19 peças imediatamente após a colocação dessa peça, observando a versão em cache da vizinhança permitida para essa peça.

Por exemplo, no exemplo abaixo, o algoritmo preenche a grade 5x5 com blocos usando uma vizinhança permitida em cache de 4 blocos. Depois de colocar o primeiro ladrilho, ele remove da consideração 19 ladrilhos impossíveis no exemplo acima. Após colocar cada bloco, todas as opções ausentes na vizinhança aceitável do bloco colocado são removidas da consideração.


Continuando dessa maneira, podemos preencher toda a grade apenas com atualizações locais rápidas para o conjunto de blocos, que ainda são opções válidas para cada um dos pontos.

As vizinhanças permitidas podem ter qualquer tamanho que você precisar, para que você possa remover blocos incompatíveis distantes sempre que colocar um bloco. Embora a geração de uma vizinhança aceitável seja bastante lenta, ela precisa ser feita apenas uma vez, após o que cada linearmente depende do tamanho da vizinhança para acomodar cada ladrilho.

Expandindo o sistema em 3D

O algoritmo Generate Worlds naturalmente se expande para mundos com uma terceira dimensão. Em vez de blocos 2D correspondentes em cores com quatro blocos vizinhos em faces comuns, agora temos blocos 3D que devem corresponder em cores aos vizinhos em seis faces. Considere os seguintes blocos 3D:


A montagem desses blocos em 3D é a seguinte:


Nesse caso, as vizinhanças admissíveis não são grades bidimensionais, mas tridimensionais, e o algoritmo as gera em um caso 2D semelhante.

Galeria de resultados

Abaixo, são mostrados os mundos gerados pelas implementações desse algoritmo, juntamente com breves descrições.


Captura de tela de Generate Worlds mostrando a sala com saída. As bordas no teto coincidem com as bordas dos ladrilhos.


Uma captura de tela de outra ferramenta criada que também usa o algoritmo Generate Worlds; diferentes tipos de salas e corredores são mostrados.


Um mundo semelhante ao anterior, mas agora em uma bela vista isométrica


O mundo, cuja criação me inspirou no nono círculo do inferno de Dante: pecadores que foram congelados no gelo. Renderizado em MagicaVoxel.


O mundo, cuja criação me inspirou na segunda rodada do inferno de Dante: a paisagem, que é irrigada pela chuva ardente, que atravessa a ponte. Renderizado em MagicaVoxel.


Um mundo de plataformas gramadas com cachoeiras e rios. Renderizado em MagicaVoxel.


Paisagem de uma cidade medieval com edifícios e paredes. Renderizado em MagicaVoxel.