Voltar para o Blog
Quest Log

Labirinto Procedural na Godot 4 com Recursive Backtracker

Vista de cima de um labirinto quadriculado gerado por computador, com um único caminho sinuoso entre corredores

Aprenda a gerar labirinto procedural na Godot 4 com o algoritmo recursive backtracker (DFS) e pilha. Código GDScript tipado completo, seed e renderização.

Ferramenta:Godot

Todo labirinto que você já viu num jogo top-down, de Pac-Man a roguelike de dungeon, é um grid de corredores com uma regra por trás. Neste tutorial a gente vai gerar labirinto procedural na Godot 4 do zero, em GDScript tipado, usando o algoritmo clássico recursive backtracker, que é um DFS (busca em profundidade) com pilha. No final você vai ter um gerador que produz um labirinto perfeito, aceita seed pra reproduzir o mesmo mapa e desenha o resultado na tela sem depender de nenhum asset.

O que é um labirinto procedural perfeito (e por que não é uma dungeon)

Antes do código, vale separar dois conceitos que muita gente mistura.

Um labirinto perfeito é um grid onde existe exatamente um caminho entre quaisquer duas células. Sem ciclos, sem áreas abertas, sem atalho. Se você entra de um canto e quer chegar no outro, só há uma rota possível. É o tipo de labirinto que o recursive backtracker gera por construção, e é o que a maioria das pessoas imagina quando pensa em "labirinto": corredores de uma célula de largura, cheios de becos sem saída.

Uma dungeon com salas é outra coisa. Ali você quer espaços abertos pra combate, vários caminhos ligando os mesmos pontos, laços pra o jogador não ficar preso num corredor só. A dungeon é feita pra exploração e luta, não pra o desafio de "achar a saída". Os algoritmos são diferentes: dungeon costuma usar salas retangulares ligadas por corredores, enquanto o labirinto perfeito usa escavação célula a célula. Se é dungeon que você quer, o caminho é o tutorial de dungeon procedural na Godot, e os dois assuntos fazem parte do mesmo pilar de geração procedural.

Neste post o foco é o labirinto perfeito. Ele é mais simples de entender, roda rápido e é a base pra muita variação depois (é fácil abrir alguns ciclos no fim pra deixar menos linear, por exemplo).

Como representar o grid de células e as paredes

A decisão mais importante de todo gerador de labirinto é como guardar as paredes. A representação que funciona bem é esta: cada célula do grid tem quatro paredes possíveis, norte, leste, sul e oeste, e você guarda quais delas ainda estão de pé.

A forma enxuta de fazer isso é uma máscara de bits. Cada direção é um bit, e a célula guarda um inteiro com os bits das paredes que existem. Uma célula "fechada" (todas as paredes de pé) vale N | E | S | W. Derrubar a parede norte é limpar o bit N.

extends Node2D

const LARGURA: int = 20
const ALTURA: int = 15
const CELULA: int = 32

# Cada parede e um bit numa mascara por celula
const N: int = 1
const E: int = 2
const S: int = 4
const O: int = 8

# Deslocamento de cada direcao no grid
const DIRECOES: Dictionary = {
    N: Vector2i(0, -1),
    E: Vector2i(1, 0),
    S: Vector2i(0, 1),
    O: Vector2i(-1, 0),
}

# A parede oposta, pra derrubar dos dois lados
const OPOSTA: Dictionary = {
    N: S,
    E: O,
    S: N,
    O: E,
}

var paredes: PackedInt32Array = PackedInt32Array()
var rng: RandomNumberGenerator = RandomNumberGenerator.new()

O PackedInt32Array guarda a máscara de cada célula num vetor plano: a célula (x, y) fica no índice y * LARGURA + x. Isso evita um array de arrays e é mais rápido de percorrer. Dois helpers deixam o resto do código legível:

func indice(c: Vector2i) -> int:
    return c.y * LARGURA + c.x

func dentro(c: Vector2i) -> bool:
    return c.x >= 0 and c.x < LARGURA and c.y >= 0 and c.y < ALTURA

O dicionário OPOSTA resolve um detalhe fácil de errar: quando você derruba a parede entre a célula A e a célula B, tem que derrubar nos dois lados. A parede norte de A é a mesma parede sul de B. Se você só limpa o bit de um lado, a renderização desenha uma linha fantasma depois.

O recursive backtracker é um DFS, e DFS pede pilha

O recursive backtracker funciona assim, em quatro passos:

  1. Comece numa célula qualquer, marque como visitada e coloque na pilha.
  2. Olhe a célula no topo da pilha. Liste os vizinhos que ainda não foram visitados.
  3. Se existe pelo menos um, escolha um ao acaso, derrube a parede entre os dois, marque o vizinho como visitado e empilhe ele.
  4. Se não existe nenhum (beco sem saída), tire a célula do topo da pilha. Isso é o "backtrack": você volta pelo caminho até achar uma célula que ainda tem vizinho livre.

Repita até a pilha esvaziar. Quando ela esvazia, toda célula foi visitada e o labirinto está pronto.

O nome diz "recursive", e dá pra escrever com recursão de verdade, uma função que chama a si mesma. O problema é prático: um grid de 100 por 100 tem 10 mil células, e o caminho mais longo escavado pode passar por boa parte delas antes do primeiro backtrack. Cada nível vira uma chamada empilhada, e a pilha de chamadas da Godot não é infinita. Labirinto grande com recursão profunda trava o jogo com stack overflow, e o pior é que isso só aparece quando um jogador gera um mapa maior do que você testou.

Programar labirinto é um ótimo momento pra perceber que decorar nós da Godot não é a mesma coisa que programar. Entender por que a pilha explícita evita o estouro, por que a máscara de bits é mais rápida que quatro booleanos, por que o DFS gera becos sem saída, isso é lógica de programação, e é o que separa quem copia um script de quem constrói o próprio jogo. Se você quer aprender a programar na Godot de verdade, da lógica à arquitetura, sem assinatura mensal e sem precisar marcar "call" com ninguém, o curso foi feito pra isso.

Curso de Godot
Quer fazer seu primeiro jogo na Godot?

No curso de Godot da CursoGame.Dev você vai do zero ao primeiro jogo, com um desafio prático em cada level e suporte individual no WhatsApp quando travar.

Conhecer o curso de Godot
Suporte no WhatsAppAcesso vitalícioGarantia de 7 dias

A solução é trocar a recursão por uma pilha explícita num Array. Você mesmo empilha e desempilha as células, a profundidade mora no heap em vez de na pilha de chamadas, e aí não tem limite prático: gera grid gigante sem risco.

O gerador completo em GDScript tipado

Aqui está a função inteira. Ela recebe uma seed, zera o grid com todas as paredes de pé e escava com a pilha explícita.

func gerar_labirinto(semente: int) -> void:
    rng.seed = semente

    # Toda celula comeca fechada: as 4 paredes de pe
    paredes.resize(LARGURA * ALTURA)
    paredes.fill(N | E | S | O)

    var visitado: Array[bool] = []
    visitado.resize(LARGURA * ALTURA)
    visitado.fill(false)

    var pilha: Array[Vector2i] = []
    var inicio: Vector2i = Vector2i(0, 0)
    visitado[indice(inicio)] = true
    pilha.push_back(inicio)

    while not pilha.is_empty():
        var atual: Vector2i = pilha.back()

        # Lista as direcoes com vizinho dentro do grid e nao visitado
        var candidatas: Array[int] = []
        for direcao: int in DIRECOES:
            var vizinho: Vector2i = atual + DIRECOES[direcao]
            if dentro(vizinho) and not visitado[indice(vizinho)]:
                candidatas.append(direcao)

        # Beco sem saida: faz o backtrack
        if candidatas.is_empty():
            pilha.pop_back()
            continue

        # Escolhe uma direcao ao acaso e avanca
        var escolha: int = candidatas[rng.randi_range(0, candidatas.size() - 1)]
        var destino: Vector2i = atual + DIRECOES[escolha]

        # Derruba a parede entre atual e destino, dos dois lados
        paredes[indice(atual)] &= ~escolha
        paredes[indice(destino)] &= ~OPOSTA[escolha]

        visitado[indice(destino)] = true
        pilha.push_back(destino)

    queue_redraw()

Três pontos que merecem atenção:

  • paredes[indice(atual)] &= ~escolha limpa o bit da parede escolhida com um AND do complemento. Se escolha é E (valor 2), ~escolha tem todos os bits ligados menos o segundo, então a operação apaga só a parede leste e preserva as outras três.
  • O continue depois do pop_back() é o backtrack puro: a célula sem vizinho livre sai da pilha e o laço volta a olhar a nova célula do topo, que é por onde você veio.
  • rng.randi_range(0, candidatas.size() - 1) é o único ponto de aleatoriedade. Trocar a seed muda toda a sequência de escolhas, e com ela o labirinto inteiro.

Uma propriedade bonita desse algoritmo: como cada célula só é visitada uma vez e a parede só cai quando você entra numa célula nova, nunca se forma um ciclo. É isso que garante que o labirinto é perfeito, com caminho único entre dois pontos quaisquer. O recursive backtracker também tende a gerar corredores longos e sinuosos, com poucos becos curtos, o que dá aquele visual de labirinto difícil.

Renderizar o labirinto na tela

Com as paredes guardadas, desenhar é direto. A forma mais simples de ver o resultado sem montar tileset é o _draw() do Node2D, uma linha por parede de pé:

func _draw() -> void:
    var cor: Color = Color.WHITE
    var espessura: float = 2.0
    for y: int in ALTURA:
        for x: int in LARGURA:
            var mascara: int = paredes[indice(Vector2i(x, y))]
            var canto: Vector2 = Vector2(x * CELULA, y * CELULA)
            var canto_dir: Vector2 = canto + Vector2(CELULA, 0)
            var canto_baixo: Vector2 = canto + Vector2(0, CELULA)
            var canto_diag: Vector2 = canto + Vector2(CELULA, CELULA)
            if mascara & N:
                draw_line(canto, canto_dir, cor, espessura)
            if mascara & E:
                draw_line(canto_dir, canto_diag, cor, espessura)
            if mascara & S:
                draw_line(canto_baixo, canto_diag, cor, espessura)
            if mascara & O:
                draw_line(canto, canto_baixo, cor, espessura)

E o ponto de entrada que amarra tudo:

func _ready() -> void:
    gerar_labirinto(12345)

Rode a cena e você vê o labirinto. draw_line é perfeito pra prototipar e pra entender a estrutura, mas num jogo de verdade você provavelmente quer tiles.

Pra renderizar num TileMapLayer, a lógica é a mesma, só muda o destino. Você percorre o grid célula a célula e, pra cada parede de pé, chama set_cell na coordenada correspondente com o tile de parede. Um jeito comum é trabalhar num grid de resolução dobrada: cada célula do labirinto vira um bloco de 2x2 ou 3x3 no TileMapLayer, onde o centro é chão e as bordas recebem parede conforme a máscara. Assim os corredores ganham largura e o resultado fica jogável em top-down. Se o nome TileMapLayer te pegou de surpresa, desde a Godot 4.3 o antigo nó TileMap saiu de cena e cada camada virou um TileMapLayer separado, com a mesma API de set_cell.

Seed: por que fixar a aleatoriedade

Repare que o gerador recebe semente e a passa pro rng.seed. Isso não é detalhe, é o que torna o labirinto reproduzível.

O RandomNumberGenerator é determinístico: com a mesma seed, ele devolve a mesma sequência de números. Como toda escolha do backtracker sai de rng.randi_range, a mesma seed com o mesmo código gera o mesmo labirinto, pixel por pixel. Na prática isso vale ouro em dois momentos. No debug, quando um labirinto aparece com um bug (um beco que não devia existir, um corredor cortado), você anota a seed e reproduz o caso exato quantas vezes precisar, em vez de ficar gerando mapas aleatórios torcendo pra o bug voltar. E no design, uma seed fixa vira um desafio diário: todo mundo joga o mesmo labirinto no mesmo dia, dá pra comparar tempos sem o mapa favorecer ninguém.

Se você quiser labirinto novo a cada partida, basta sortear a seed antes de gerar, com rng.randomize() ou passando Time.get_unix_time_from_system() como semente. O importante é guardar qual seed foi usada, pra poder voltar nela depois.

Onde ir a partir daqui

Você tem um gerador de labirinto perfeito completo: representação por máscara de bits, escavação com recursive backtracker e pilha explícita (sem risco de stack overflow), seed pra reproduzir e renderização pronta. A partir dessa base, as extensões mais comuns são abrir alguns ciclos no fim pra deixar o labirinto menos linear, marcar entrada e saída nas células mais distantes (um BFS resolve isso) e misturar o labirinto com salas pra um híbrido de maze e dungeon.

A Godot dá conta de tudo isso sem plugin nem motor pago, e é um ótimo projeto pra firmar lógica de grid, pilha e aleatoriedade controlada. Se você ainda está decidindo em qual motor investir seu tempo pra esse tipo de projeto 2D, o comparativo Godot vs Unity ajuda a pesar os dois lados antes de mergulhar.

Perguntas frequentes

Como gerar um labirinto procedural na Godot 4?

Represente o grid como células com paredes nas quatro direções, todas fechadas no começo. Depois escave com o algoritmo recursive backtracker: parta de uma célula, escolha um vizinho não visitado ao acaso, derrube a parede entre os dois e avance. Quando travar, volte pela pilha. No fim pinte as paredes num TileMapLayer ou desenhe com draw_line.

Qual a diferença entre labirinto perfeito e dungeon com salas?

Um labirinto perfeito tem exatamente um caminho entre quaisquer dois pontos, sem ciclos nem áreas abertas, que é o que o recursive backtracker gera. Uma dungeon com salas tem espaços abertos, caminhos alternativos e laços, pensada pra combate e exploração, e usa outros algoritmos como salas com corredores.

Por que usar uma pilha em vez de recursão no backtracker?

O recursive backtracker é um DFS. Em recursão pura, um labirinto grande pode estourar a pilha de chamadas da Godot e travar o jogo. Com uma pilha explícita num Array você controla a profundidade na memória do heap e gera grids enormes sem risco de stack overflow.

Como reproduzir o mesmo labirinto com seed na Godot?

Use um RandomNumberGenerator e defina rng.seed com um valor fixo antes de gerar. Com a mesma seed e o mesmo código, a sequência de sorteios é idêntica e o labirinto sai igual toda vez, o que serve pra debug e pra desafios diários.