Wave Function Collapse na Godot: geração procedural por restrições

Se você já gerou mapas por salas conectadas ou por ruído de altura e sentiu que o resultado ficava ou muito repetitivo ou sem coerência local, o Wave Function Collapse na Godot é a ferramenta que faltava. O Wave Function Collapse (WFC) é um método de geração procedural por restrições: em vez de sortear tiles soltos ou empilhar valores de altura, você declara regras de quais tiles podem ficar vizinhos de quais, e o algoritmo monta um mapa inteiro que respeita todas essas regras ao mesmo tempo. Neste post da CursoGame.Dev a gente vai construir a intuição, os passos e uma implementação simples e tipada em GDScript para a Godot 4.

Antes de mais nada, vale separar o WFC dos outros dois métodos que já cobrimos por aqui. A geração por salas parte de retângulos de cômodo e liga eles com corredores, ótima para dungeons. O ruído gera terreno atribuindo um número contínuo (altura, umidade) a cada ponto e classificando por faixas. O WFC não pensa em nenhuma dessas coisas: ele só sabe que "areia pode encostar em grama e em água, mas grama não pode encostar direto em água". A coerência do mapa emerge dessas restrições locais.

A intuição do Wave Function Collapse

Imagine cada célula da sua grade como uma caixa que, no começo, contém todos os tiles possíveis ao mesmo tempo. Essa lista de possibilidades é a "superposição" daquela célula. Nenhuma decisão foi tomada ainda: a célula pode virar grama, areia ou água.

O algoritmo repete três ações até acabar:

1. Observar: escolhe a célula com menos opções restantes (a de menor entropia) e a colapsa, ou seja, fixa ela em um único tile válido. Escolher a de menor entropia é o pulo do gato: é a célula mais "decidida", onde há menos margem para erro.
2. Propagar: olha para os vizinhos da célula recém colapsada e remove das listas deles qualquer tile que agora ficou proibido pelas regras de adjacência. Se um vizinho mudou, a mudança se propaga para os vizinhos dele, como um efeito dominó.
3. Repetir: volta ao passo 1, sempre pegando a célula mais restrita, até que todas estejam colapsadas.

Se em algum momento uma célula ficar com zero opções, você tem uma contradição: as regras se contradizem naquele ponto e não há tile válido. Aí é hora de recomeçar (ou desfazer jogadas, se você tiver backtracking). O nome "collapse" vem justamente dessa ideia de reduzir a superposição de muitas possibilidades para uma só, célula por célula.

Os passos concretos

Vamos fixar o vocabulário em quatro etapas de implementação, que é o que o código vai refletir depois:

• Definir tiles e regras de adjacência. Cada tile ganha um id inteiro. Para cada direção (cima, baixo, esquerda, direita) você declara quais tiles são permitidos ao lado.
• Representar a grade de possibilidades. Cada célula guarda um conjunto (ou array) com os ids ainda possíveis. No início, todas contêm todos os ids.
• Loop de observar e propagar. Ache a menor entropia, colapse, propague. Repita.
• Lidar com contradição. Detecte a célula vazia e decida a estratégia: recomeçar é o mais simples e honesto para um post didático.

Um detalhe importante sobre entropia: na versão mais simples, a entropia de uma célula é só a quantidade de tiles ainda possíveis nela. Uma célula com 1 opção já está praticamente decidida, uma com 3 ainda está aberta. Você quer sempre colapsar a de menor contagem (maior que 1), porque assim minimiza a chance de criar contradições lá na frente.

Definindo tiles e regras em GDScript tipado

Vamos ao código. O exemplo usa três tiles: grama (0), areia (1) e água (2). A regra do mundo é simples: a água só encosta em areia ou água, a grama só encosta em areia ou grama, e a areia é a ponte entre os dois. Como a regra é simétrica em todas as direções, dá para guardar as adjacências num dicionário único de "quem pode ser meu vizinho".

extends Node

const GRAMA: int = 0
const AREIA: int = 1
const AGUA: int = 2

const TILES: Array[int] = [GRAMA, AREIA, AGUA]

# Para cada tile, o conjunto de tiles que podem ficar ao lado dele.
var adjacencia: Dictionary = {
    GRAMA: [GRAMA, AREIA],
    AREIA: [GRAMA, AREIA, AGUA],
    AGUA: [AREIA, AGUA],
}

var largura: int = 12
var altura: int = 8

# A grade de possibilidades: cada celula guarda um Array de ids possiveis.
var grid: Array = []

O adjacencia é o coração das restrições. Se você quiser um mundo mais rico, é aqui que declara regras por direção (por exemplo, "montanha só em cima de rocha") ou adiciona novos tiles.

Inicializando a grade de possibilidades

No começo, toda célula está em superposição total: ela contém uma cópia de todos os ids. Guardamos a grade como um array bidimensional indexado por Vector2i.

func inicializar_grade() -> void:
    grid = []
    for y: int in range(altura):
        var linha: Array = []
        for x: int in range(largura):
            linha.append(TILES.duplicate())
        grid.append(linha)

func opcoes_em(cell: Vector2i) -> Array:
    return grid[cell.y][cell.x]

Reparou no TILES.duplicate()? Sem isso, todas as células apontariam para o mesmo array e colapsar uma bagunçaria as outras. Copiar é obrigatório.