Desvendando Labirintos #2: Algoritmo de Árvore Binária

Esse é o segundo 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 de Árvore Binária.

O que são árvores binárias?

Uma árvore binária é uma estrutura de dados em que cada nó pode ter, no máximo, dois filhos: um filho à esquerda e um filho à direita. Além disso, essa estrutura é amplamente usada em ciência da computação por ser eficiente para organizar e buscar dados. Dessa forma, cada só se conecta apenas com os seus filhos e não há ciclos (um ciclo é quando dois vértices podem se conectar por mais de um caminho). Em outras palavras, partindo da raíz da árvore, você consegue chegar em qualquer outro nó sem revisitar outros nós.

• Raiz: o nó mais alto da árvore.
• Nó: um elemento que contém um valor e referências para até dois nós filhos.
• Filhos: nós ligados a um nó superior (pai).
• Folha: um nó que não possui filhos.
• Altura: o número máximo de níveis da árvore.

Quais são os principais tipos de árvores binárias?

• Árvore binária completa: todos os níveis são completamente preenchidos, exceto o último, que é preenchido da esquerda para a direita.
• Árvore binária cheia: todos os nós têm zero ou dois filhos.
• Árvore binária balanceada: a altura da subárvore esquerda e da subárvore direita de cada nó diferem no máximo por um.
• Árvore binária de busca (BST): os valores à esquerda de um nó são menores que o valor do nó, e os valores à direita são maiores.

Por que o Algoritmo se chama “Árvore Binária”?

O nome “Árvore Binária” é dado porque o algoritmo segue um princípio de construção semelhante ao da estrutura de dados de mesmo nome.

• Em uma árvore binária, cada nó tem dois filhos possíveis.
• No algoritmo do labirinto, cada célula “decide” entre duas direções para criar passagens (norte ou esquerda, por exemplo).

A estrutura resultante do labirinto é similar a uma árvore: uma rede de células conectadas onde, partindo de qualquer célula, há um caminho único até outras células, sem ciclos, da mesma forma que uma árvore binária.

Passo-a-passo

1. Crie uma grade de vértices, com todas arestas marcadas como paredes.
2. Inicie no primeiro vértice (coordenada (0, 0))
3. Defina um par de arestas adjacentes para serem os possíveis filhos do nó. No nosso exemplo vamos usar norte e esqueda.
4. Para cada vértice, escolha aleatóriamente entre as aretas norte e esquerda e marque-a como passagem.
5. Gente, é isso. Mais simples impossível. Só repetir o passo 3 até percorrer todos os vértices.

Algoritmo

Acesse o repositório no GitHub aqui.

Importante! O algoritmo de Árvore Binária, 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.

using MazeBuilderAPI.Models.Internal;

namespace MazeBuilderAPI.Algorithms.Maze;

public class BinaryTreeAlgorithm : MazeBuilderBaseAlgorithm
{
    public BinaryTreeAlgorithm(int columns, int rows)
    {
        Columns = columns;
        Rows = rows;
    }

    public void Run(int seed = -1)
    {
        if (Maze is null)
        {
            var bIsInitialized = Initialize(true);
            if (!bIsInitialized) return;
        }
        
        // Initializing the random stream
        var randomStream = seed == -1 ? new Random() : new Random(seed);
        
        for (int y = 0; y < Columns; y++)
        {
            for (int x = 0; x < Rows; x++)
            {
                bool canGoLeft = x > 0; // Can go left, if it's not in the first column
                bool canGoUp = y > 0; //Can go up, if it's not in the first row

                // If it can go Up and Left, choose a random path between them
                if (canGoLeft && canGoUp)
                {
                    if (randomStream.Next(2) == 0) // 0 = Up, 1 = Left
                    {
                        HandleWallBetween(x, y, x, y - 1, true); // Remove Up wall
                    }
                    else
                    {
                        HandleWallBetween(x, y, x - 1, y, true); // Remove Left wall
                    }
                }
                else if (canGoLeft)
                {
                    // If it can't go Up, go Left
                    HandleWallBetween(x, y, x - 1, y, true);
                }
                else if (canGoUp)
                {
                    // If it can't go Left, go Up
                    HandleWallBetween(x, y, x, y - 1, true);
                }
            }
        }
    }
}

Desafio

Se quiser aprimorar o algoritmo, você pode implementar para que ele escolha um par de arestas adjacentes aleatóriamente. Dessa forma, aquele grande corredor no norte e na esqueda, pode ficar em outras posições, gerando mais diversidade.

Análise de complexidade

• Complexidade de Tempo: O(n) – O algoritmo visita cada célula na grade uma vez, o que implica que o tempo de execução é linearmente proporcional ao número de células. Portanto, o tempo de geração do labirinto aumenta de forma relativamente previsível com o tamanho da grade.
• Complexidade de Espaço: O(1) a O(n) – A complexidade de espaço depende da implementação. Se, por exemplo, a grade for armazenada em memória, a complexidade de espaço será O(n), onde n é o número de células. Por outro lado, se a grade for gerada dinamicamente, a complexidade de espaço pode ser reduzida para O(1), pois apenas uma célula precisa ser mantida em memória por vez.

Prós

• Simplicidade Excepcional: O Algoritmo da Árvore Binária, antes de mais nada, se destaca pela sua facilidade de compreensão e implementação.
• Implementação Rápida e Direta: Além disso, a simplicidade do algoritmo permite uma codificação rápida, ideal para prototipagem e projetos com prazos apertados.
• Excelente Ponto de Partida para Aprendizado: Ademais, sua natureza intuitiva o torna uma ferramenta valiosa para iniciantes que desejam aprender os conceitos fundamentais da geração de labirintos e algoritmos.
• Baixo Consumo de Recursos: Finalmente, o algoritmo apresenta um baixo consumo de memória e poder de processamento, tornando-o adequado para dispositivos com recursos limitados.

Contras

• Bias Significativo e Textura Diagonal: Em contrapartida, o Algoritmo da Árvore Binária introduz um bias notável, resultando em corredores longos e ininterruptos nas bordas norte e leste do labirinto. Consequentemente, isso cria uma textura diagonal que pode tornar a navegação previsível e menos desafiadora.
• Aleatoriedade Limitada: Devido a essa característica, a natureza determinística do algoritmo (escolher apenas entre norte ou leste) limita a variedade dos labirintos gerados, tornando-os menos interessantes em comparação com algoritmos mais complexos.
• Não Adequado para Todos os Cenários: Por fim, e em decorrência dos pontos anteriores, o Algoritmo da Árvore Binária pode não ser a melhor escolha para jogos ou aplicações que exigem labirintos complexos e imprevisíveis.

Quando usar este algoritmo?

• Para Ensinar Geração de Labirintos: Use o Algoritmo da Árvore Binária para demonstrar os fundamentos da criação de labirintos de forma simples e direta.
• Em Prototipagem Rápida: Empregue este algoritmo quando precisar gerar protótipos de labirintos rapidamente, priorizando a velocidade de desenvolvimento.
• Em Sistemas com Recursos Limitados: Escolha este algoritmo para sistemas embarcados ou dispositivos móveis, onde a eficiência e o baixo consumo de recursos são essenciais.
• Quando o Bias é Aceitável ou Desejável: Explore o bias do algoritmo de forma criativa para gerar labirintos com características específicas, como facilitar a navegação em uma direção.

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