Desvendando Labirintos #4: Algoritmo Recursive Division

Esse é o quarto post da série “Desvendando Labirintos”. Se quiser saber mais geração e resolução de labirintos e suas práticas, acesse este post! E agora vamos nos aprofundar sobre como funciona o algoritmo Recursive Division.

Passo-a-passo

1. Inicialize a grade de vértices com todas as arestas marcadas como passagem.
2. Em seguida, escolha um vértice inicial.
3. Se o número de linhas:
   • For menor do que o número de colunas: escolha partir a grade na horizontal.
   • For maior do que o número de colunas: escolha partir a grade na vertical.
   • For igual ao número de colunas: escolha aleatóriamente se em qual orientação vai partir a grade.
4. Se a orientação para repartir for na horizontal:
   • Escolha aleatóriamente a aresta de cima ou de baixo, desde que não colida com os limites da grade.
   • Em seguida marque para todos os vértices da linha a aresta escolhida como parede.
5. Caso contrário:
   • Escolha aleatóriamente a aresta da esquerda ou da direita, desde que não colida com os limites da grade.
   • Em seguida marque para todos os vértices da coluna a aresta escolhida como parede.
6. Agora escolha aleatóriamente uma aresta recém marcada como parede, e marque-a como passagem.
7. Então, para cada lado da divisão, atualize o número de linhas e colunas e volte para o passo 3.
8. Por fim, termine quando não for mais possível realizar divisões.

Algoritmo

Acesse o repositório no GitHub aqui.

Importante! O algoritmo recursive division, apresentado abaixo, depende de classes que foram definidas no primeiro post dessa série. Então, aconselho a dar um pulinho lá antes de continuar.

namespace MazeBuilderAPI.Algorithms.Maze;

public class RecursiveDivision : MazeBuilderBaseAlgorithm
{
    private Random _randomStream;
    
    public RecursiveDivision(int columns, int rows)
    {
        Columns = columns;
        Rows = rows;
        _randomStream = new Random();
    }

    public void Run(int seed = -1)
    {
        if (Maze is null)
        {
            var bIsInitialized = Initialize(false);
            if (!bIsInitialized) return;
        }

        // Initializing the random stream
        if (seed != -1) _randomStream = new Random(seed);
        
        Divide(0, 0, Rows, Columns);
    }

    private void Divide(int minX, int minY, int maxX, int maxY)
    {
        // Stop if the area is too small
        if (maxX - minX < 2 || maxY - minY < 2) return;

        // Choose if it should divide horizontally or vertically
        var isHorizontal = ChooseOrientation(maxX - minX, maxY - minY);

        if (isHorizontal)
        {
            // Horizontal division
            var y = _randomStream.Next(minY + 1, maxY);
            var passageX = _randomStream.Next(minX, maxX);

            // Draw passage
            for (var x = minX; x < maxX; x++)
            {
                if (x != passageX)
                {
                    HandleWallBetween(x, y, x, y - 1, false);
                }
            }

            // Use recursion to divide the new areas
            Divide(minX, minY, maxX, y);       // Upper area
            Divide(minX, y, maxX, maxY);       // Lower area
        }
        else
        {
            // Vertical division
            var x = _randomStream.Next(minX + 1, maxX);
            var passageY = _randomStream.Next(minY, maxY);

            // Draw passage
            for (var y = minY; y < maxY; y++)
            {
                if (y != passageY)
                {
                    HandleWallBetween(x, y, x - 1, y, false);
                }
            }

            // Use recursion to divide the new areas
            Divide(minX, minY, x, maxY);       // Left area
            Divide(x, minY, maxX, maxY);       // Right area
        }
    }
    private bool ChooseOrientation(int width, int height)
    {
        if (width < height) return true; // Horizontal
        if (height < width) return false; // Vertical
        return _randomStream.Next(2) == 0; // Random
    }
}

Desafio

Adaptar o algoritmo Recursive Division para terminar a recursão em tempos diferentes em alguns casos, formando salas dentro do labirinto. Além disso, tente passar como parâmetro a quantidade de salas que deseja ter, para uma dificuldade maior.

Análise de complexidade

• Complexidade de Tempo: O(n log n) (em média) – A complexidade de tempo do Recursive Division depende da estratégia de divisão. Em média, a complexidade é O(n log n), onde n é o número de células. Isso ocorre porque o algoritmo divide o espaço em duas partes a cada passo, resultando em um comportamento logarítmico.
• Complexidade de Espaço: O(log n) – A complexidade de espaço é dominada pela profundidade da recursão, que é logarítmica em relação ao tamanho do labirinto.

Prós

• Gera Labirintos com Estrutura Hierárquica Distinta: O Recursive Division cria labirintos com uma clara organização hierárquica, o que permite aos jogadores identificarem áreas distintas e compreenderem a estrutura geral do desafio.
• Implementação Relativamente Simples: Apesar de sua natureza recursiva, o algoritmo é relativamente fácil de implementar, tornando-o uma boa escolha para projetos onde a simplicidade do código é importante.
• Criação Fácil de “Salas” e Áreas Abertas: Além disso, o Recursive Division facilita a criação de áreas abertas ou “salas” no labirinto, o que pode ser usado para adicionar variedade e pontos de interesse ao jogo.

Contras

• Tendência a Gerar Labirintos “Boxy”: Devido à sua natureza de divisão em linhas retas, o Recursive Division tende a gerar labirintos com uma aparência “boxy” ou retilínea, o que pode ser indesejável em alguns contextos.
• Pode Resultar em Caminhos Previsíveis: Em alguns casos, a estrutura hierárquica do Recursive Division pode tornar os caminhos no labirinto mais previsíveis, o que diminui o desafio para o jogador.
• Dificuldade em Criar Labirintos Altamente Complexos: Embora seja possível criar labirintos complexos com o Recursive Division, a estrutura hierárquica inerente ao algoritmo pode limitar a criação de labirintos com um alto grau de interconexão e caminhos intrincados.

Quando utilizar este algoritmo?

• Crie Labirintos com Estrutura Hierárquica Clara: Utilize o Recursive Division quando precisar de labirintos com uma organização hierárquica bem definida, o que pode ser útil para jogos que exploram conceitos de níveis ou áreas interconectadas.
• Gere Labirintos com “Salas” e Áreas Abertas: Empregue este algoritmo quando desejar incorporar áreas abertas ou “salas” ao labirinto, tornando-o mais interessante e diversificado do ponto de vista visual e de jogabilidade.
• Controle a Complexidade com a Profundidade da Recursão: Ajuste a profundidade da recursão para controlar a complexidade geral do labirinto, o que permite criar desafios adequados para diferentes públicos e níveis de habilidade.
• Explore a Estética “Boxy” para Fins Criativos: Aproveite a tendência do Recursive Division de gerar labirintos com uma aparência “boxy” para criar um estilo visual único, que pode ser adequado para jogos com temas arquitetônicos ou urbanos.

Quer se aprofundar no mundo da criação de labirintos?