- Projeto que gera automaticamente um mapa insular com estética medieval composto por cerca de 4.100 tiles hexagonais usando o algoritmo Wave Function Collapse (WFC)
- Cada tile inclui informações de terreno como estradas, rios, costa, penhascos, florestas e vilas, e é gerado em cerca de 20 segundos com Three.js WebGPU e shaders TSL
- Para resolver falhas que surgem em grades grandes, o mapa é dividido em 19 subgrades hexagonais, com backtracking e um sistema de recuperação Local-WFC garantindo taxa de sucesso acima de 86%
- Visualmente, aplica materiais PBR, shaders baseados em WebGPU, reflexos e ondas na água, e pós-processamento (iluminação, profundidade de campo e grain) para reforçar a sensação de volume
- Com renderização via BatchedMesh e compartilhamento de um único material, renderiza milhares de tiles a 60fps, mostrando o potencial da combinação entre geração procedural e gráficos em tempo real
Visão geral da geração procedural de mapas
- O projeto foi inspirado no método de geração com dados de masmorra de AD&D, em que o algoritmo constrói o mundo por conta própria sem exigir que o usuário o desenhe manualmente
- O mapa gerado tem a forma de uma ilha medieval com estradas, rios, linha costeira, penhascos, florestas e vilas, composta por cerca de 4.100 células hexagonais
- Usa Three.js WebGPU e shaders TSL para concluir o mapa inteiro em cerca de 20 segundos
Algoritmo Wave Function Collapse (WFC)
- O WFC monta o terreno com base na restrição de que as bordas (edges) dos tiles adjacentes devem coincidir
- Como os tiles hexagonais têm 6 bordas, eles possuem 50% mais restrições do que tiles quadrados
- Cada tile define tipos de borda em 6 direções e um peso (
weight); por exemplo, um cruzamento de estrada em 3 direções alterna bordas de estrada e grama
- O algoritmo
- inicializa todas as células com todos os estados possíveis
- escolhe a célula mais restrita e a “colapsa” em um único estado
- propaga removendo estados impossíveis das células vizinhas
- repete até que todas as células sejam resolvidas
Grades grandes e solução modular
- Em grades pequenas, ele é estável, mas acima de 4.000 células a probabilidade de falha cresce rapidamente
- Para resolver isso, o mapa é dividido em 19 subgrades hexagonais, cada uma resolvida de forma independente enquanto os tiles de borda permanecem como restrições fixas
- Quando as restrições de borda entram em conflito, só o backtracking não consegue resolver
Backtracking e sistema de recuperação
- Backtracking desfaz escolhas erradas para tentar outros tiles, com até 500 tentativas
- Porém, conflitos entre grades são tratados com um sistema de recuperação separado
- Etapa 1: Unfixing — a célula em conflito volta a um estado variável e as células ao redor passam a ser novas restrições
- Etapa 2: Local-WFC — uma área com raio de 2 células (19 células) é resolvida novamente para garantir compatibilidade na fronteira, com até 5 tentativas
- Etapa 3: Drop & Hide — se falhar, a célula é removida e coberta com um tile montanhoso para esconder o problema de forma natural
- Com essa recuperação em múltiplas camadas, a taxa de sucesso da geração do mapa chega a cerca de 86%
Tratamento de elevação em 3D
- O mapa tem 5 níveis de elevação, e tiles de inclinação e penhasco conectam níveis superiores e inferiores
- Se a ligação estiver errada, podem surgir erros como estradas bloqueadas por penhascos ou rios fluindo para cima
- As informações de elevação são codificadas como cores de instância, permitindo ao shader misturar paletas de cores de áreas baixas e altas
Sistema de coordenadas hexagonais
- Por causa da estrutura em 6 direções, hexágonos tornam o cálculo de adjacência complicado em um sistema 2D simples
- O projeto usa o sistema de coordenadas cúbicas (q, r, s) para simplificar a busca por vizinhos
- Como o WFC foca mais na estrutura de grafo de correspondência de bordas do que na geometria em si, o sistema de coordenadas é usado principalmente na renderização e no posicionamento de múltiplas grades
Posicionamento de árvores e construções
- O WFC é forte em padrões locais, mas inadequado para distribuições em larga escala
- Árvores e construções usam um campo de ruído Perlin para definir densidade e formar agrupamentos naturais de florestas e vilas
- Lógicas adicionais colocam construções no fim das estradas, portos e moinhos na costa, e um henge nas colinas
Implementação dos efeitos de água
- O mar não é apenas um plano simples, mas inclui brilho e ondas costeiras
- Os brilhos (Sparkles) são implementados com uma pequena textura em rolagem + máscara de ruído, em vez de ruído Voronoi, reduzindo a carga na GPU
- As ondas costeiras (Coast Waves) desfocam a máscara da costa para gerar faixas senoidais baseadas em distância
- No problema das enseadas (Cove), o cálculo de distância baseado em blur é impreciso, então a CPU inspeciona as células vizinhas para gerar uma máscara de área onde as ondas devem ficar mais finas
Criação e alinhamento dos tiles
- O modelo base usa o KayKit Medieval Hexagon Pack, mas tiles de conexão ausentes (como rio em inclinação e variações de penhasco) foram criados manualmente no Blender
- Todos os tiles foram padronizados com largura de 2 unidades, e qualquer erro no alinhamento de UV revela emendas nas bordas, exigindo mapeamento preciso
Efeitos visuais e renderização
- Implementado com Three.js WebGPU + shaders TSL, usando shaders baseados em nós em vez de GLSL
- Pilha de pós-processamento
- GTAO para reforçar o sombreamento
- Profundidade de campo (Depth of Field) para efeito de miniatura
- Vignette e film grain para dar textura analógica
- O mapa de sombras dinâmico é reajustado a cada frame de acordo com o campo de visão da câmera, mantendo sombras nítidas mesmo ao ampliar
Otimização de desempenho
- Com BatchedMesh, os tiles e enfeites de cada grade são agrupados para renderização em uma única draw call
- Todas as malhas compartilham um único material, minimizando trocas de estado do shader
- O resultado são 38 BatchedMesh, 4.100+ células e renderização a 60fps
Principais números e stack técnica
- 30 tipos de tile, 19 grades, ~4.100 células, 500 backtrackings, 5 tentativas de Local-WFC, 20 segundos de geração, 100% de sucesso (500 testes)
- Uso de Three.js r183, shaders TSL, Web Workers, build com Vite, BatchedMesh e Seeded RNG
Experiência e código-fonte
- O demo ao vivo permite expandir o mapa e gerar o mundo inteiro
- O código-fonte no GitHub está disponível, com mais de 50 parâmetros para ajustar iluminação, cores, água e configurações de WFC
Resumo
- Em vez de dados, o algoritmo oferece a experiência de criar um mundo, permitindo explorar terrenos diferentes e novas conexões entre estradas e rios a cada execução
- Um experimento de geração de mapas baseado em WebGPU que combina geração procedural, otimização gráfica e tecnologia de shaders
1 comentários
Comentários no Hacker News
O texto diz que simplesmente limitou o backtracking a 500 etapas, mas, na prática, programação por restrições é uma área muito interessante e complexa
Usando o Algorithm X do Knuth e dancing links, parece que daria para resolver a área de "Layer 2" mencionada no texto com uma taxa de sucesso maior que 86%
Além disso, com várias heurísticas, dá para explorar muito mais rápido do que com brute force simples. Quem já fez um solver de Sudoku sabe bem como o brute force fica lento
Por exemplo, o MiniZinc oferece uma linguagem de modelagem de alto nível com suporte a vários backends de solver
Em vez de escrever o algoritmo na mão, é mais eficiente modelar o problema com esses solvers de nível industrial e deixar que o solver encontre a resposta com busca aleatória ou exaustiva
Assim, em vez de gastar tempo escrevendo o solver, você pode focar em ajustar a definição do problema para criar mapas mais interessantes
No meu notebook (Core i5 de 11ª geração, Iris Xe, versão mais recente do Chrome), a demo roda a 5 FPS. Parece que o gargalo é a GPU
O texto dizia que rodava a 60 FPS no mobile, então eu esperava algo mais eficiente
O mapa é bonito, mas as restrições em nível de tile do WFC acabam gerando resultados pouco naturais, porque é difícil refletir influência não local (non-local influence)
Para jogos em que se explora tile por tile, tudo bem, mas não parece adequado para gerar o mapa inteiro
A abordagem baseada em ruído do Red Blob Games mostra resultados melhores. Rios podem ser feitos com rastreamento de umidade, e estradas ou pontes podem ser tratadas em um passo separado, ficando mais rápido e robusto
Ainda assim, WFC é um problema de programação interessante, então implementar isso provavelmente foi divertido. No geral, foi um ótimo texto e uma demo impressionante
Oskar Stålberg usou Wave Function Collapse (WFC) em vários jogos. Um exemplo representativo é Townscaper
O vídeo da apresentação relacionada pode ser visto em SGC21 - Beyond Townscapers
Isso me lembrou o tutorial de Unity Hex Terrain do Jasper Flick
Enquanto este projeto encaixa tiles pré-fabricados com base em restrições, o tutorial do Jasper gera dinamicamente as bordas dos tiles
As duas abordagens são interessantes e prazerosas de ler
Foi um projeto realmente incrível
Aliás, caso o autor veja isso, fiquei curioso se considerou representar o estado de superposição do tile (o conjunto de opções possíveis) como um bitfield
Quando implementei WFC no passado, trocar para bitfield deu um ganho de desempenho enorme. Recalcular o chunk inteiro ficou mais rápido do que fazer backtracking
Ele funciona salvando o estado na pilha em intervalos regulares e, quando trava, volta ao último estado
Ver uma variável chamada
tenperme faz guardar um leve ressentimento do meu eu do passadoParece que a parte mais difícil é encontrar uma disposição que satisfaça as restrições
Fiquei pensando se haveria uma alternativa usando SAT solver. Só que, nesse caso, talvez ele sempre encontre apenas soluções “fáceis” e a aleatoriedade diminua
Alguns SAT solvers permitem inicializar as variáveis aleatoriamente, mas isso não significa necessariamente uma solução aleatória. Fiquei curioso se alguém já tentou algo parecido
Já o WFC é um brute force simples, então é fácil de implementar e, desde que não haja becos sem saída demais, o custo computacional é baixo
Em jogos, muitas vezes basta um resultado “bom o suficiente” em vez da solução perfeita, então WFC pode ser mais prático
Foi um projeto inspirador. O material de referência também é excelente, e o código-fonte está aberto
Acho que ficaria ótimo combinar isso com o estilo visual de Here Dragons Abound
O OP talvez já saiba, mas a página sobre matemática de hexágonos do Red Blob Games tem muitos exemplos e códigos excelentes
É interessante ver uma exploração de WFC em grades não quadradas (non-square)
A complexidade da propagação de restrições parece bem maior do que nos exemplos tradicionais
Em topologias complexas assim, dá para imaginar que outros solvers de restrições, como Constraint Logic Programming, possam levar vantagem em expressividade e desempenho
Lembrou Dorfromantik. Link da Steam