Desvendando Labirintos #7: Algoritmo de Eller

Esse é o sétimo 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 Eller.

O algoritmo de Eller se destaca por sua abordagem linear e incremental. Ele processa o labirinto linha por linha, tomando decisões sobre a conectividade horizontal e vertical em cada etapa.

Passo-a-passo

1. Primeiramente, inicie com uma grade completamente vazia. Em seguida, considere a primeira linha: cada célula dessa linha será, inicialmente, um conjunto único.
2. Agora, para cada célula na linha que você está processando, decida aleatoriamente se irá uni-la com a célula adjacente à direita. Mas, atenção: essa união só pode ocorrer se as duas células não fizerem parte do mesmo conjunto. Caso contrário, ignore a união e siga para a próxima célula.
3. Após decidir sobre as uniões horizontais, é hora de criar as passagens verticais. Então, para cada conjunto existente na linha, escolha aleatoriamente pelo menos uma célula para conectar com a célula correspondente na linha seguinte. Essa etapa é crucial para garantir que o labirinto permaneça totalmente conectado, sem áreas isoladas.
4. As células que foram conectadas verticalmente herdam o conjunto da célula acima, indicando que fazem parte do mesmo caminho. Por outro lado, as células que não foram conectadas verticalmente iniciam um novo conjunto, representando o início de um novo caminho a ser explorado.
5. Quando chegar à última linha do labirinto, o tratamento é especial. Nessa etapa, garanta que todas as células sejam unidas em um único conjunto. Para isso, crie passagens horizontais entre conjuntos adjacentes até que todo o labirinto esteja interligado. Isso garante que haja um caminho único entre quaisquer dois pontos do labirinto.
6. Finalmente, repita os passos 2 a 4 para cada linha da grade, movendo-se sequencialmente até alcançar a última linha e finalizar a geração do labirinto.

Algoritmo

Acesse o repositório no GitHub aqui.

Importante! O algoritmo de Eller, 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 EllerAlgorithm : MazeBuilderBaseAlgorithm
{
    public EllerAlgorithm(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;
        }
        
        var randomStream = seed == -1 ? new Random() : new Random(seed);
        var sets = new Dictionary<int, int>();
        var nextSet = 1;

        for (int y = 0; y < Columns; y++)
        {
            for (int x = 0; x < Rows; x++)
            {
                if (!sets.ContainsKey(x))
                {
                    sets[x] = nextSet++;
                }

                if (x < Rows - 1 && (randomStream.Next(2) == 0 || y == Columns - 1))
                {
                    if (!sets.ContainsKey(x + 1))
                    {
                        sets[x + 1] = nextSet++;
                    }

                    if (sets[x] != sets[x + 1])
                    {
                        HandleWallBetween(x, y, x + 1, y, true);
                        int oldSet = sets[x + 1];
                        for (int i = 0; i < Rows; i++)
                        {
                            if (sets.ContainsKey(i) && sets[i] == oldSet)
                            {
                                sets[i] = sets[x];
                            }
                        }
                    }
                }
            }
            if (y < Columns - 1)
            {
                var nextRowSets = new Dictionary<int, int>();
                for (int x = 0; x < Rows; x++)
                {
                    if (randomStream.Next(2) == 0 || !nextRowSets.ContainsValue(sets[x]))
                    {
                        HandleWallBetween(x, y, x, y + 1, true);
                        nextRowSets[x] = sets[x];
                    }
                }
                sets = nextRowSets;
            }
        }
    }
}

Desafio

Conforme implementamos o algoritmo de Eller, podemos ver que a primeira coluna é sempre uma linha reta. Essa é uma caracteristica importante desse método de geração de labirintos. Então, para gerar mais aleatoriedade, o desafio é fazer com que essa linha reta fique na última coluna, ou na primera/última linha. Além disso, para adicionar uma dificuldade a mais, faça as 4 possibilidades e um mecanismo para escolher a posição da linha reta aleatóriamente.

Análise de complexidade

• Complexidade de Tempo: O algoritmo de Eller tem uma complexidade de tempo linear, O(n), onde n é o número de células na grade. Isso ocorre porque cada célula é visitada e processada um número constante de vezes.
• Complexidade de Espaço: A complexidade de espaço também é linear, O(m), onde m é a largura do labirinto. Isso se deve à necessidade de manter informações sobre os conjuntos para a linha atual.

Prós

• Eficiência Garantida: Opte pelo algoritmo de Eller para garantir um excelente desempenho, pois sua complexidade linear assegura um processamento rápido e eficiente, mesmo em grades extensas.
• Economia de Memória: Além disso, o algoritmo de Eller se destaca por sua capacidade de gerar labirintos linha a linha, eliminando a necessidade de armazenar o labirinto inteiro na memória. Isso o torna uma escolha inteligente para ambientes com recursos limitados.
• Labirintos Perfeitos: Por fim, o algoritmo de Eller assegura a criação de labirintos perfeitos, o que significa que existe um único e inequívoco caminho entre quaisquer dois pontos dentro do labirinto.

Contras

• Textura Menos Aleatória: É importante estar ciente de que o algoritmo de Eller tende a criar labirintos com longas passagens, e assim pode resultar em uma textura visualmente menos aleatória do que outros algoritmos.
• Primeira Coluna Linear: Adicionalmente, observe que a primeira coluna do labirinto gerado invariavelmente se torna uma linha reta, o que pode influenciar a estética geral do labirinto.

Quando usar este algoritmo?

• Priorize o Desempenho: Se a sua prioridade for a geração de um labirinto perfeito com o melhor desempenho possível, então o algoritmo de Eller é uma excelente escolha.
• Enfrente Limitações de Memória: Se você estiver trabalhando em um ambiente com restrições de memória, então o algoritmo de Eller se destaca por sua capacidade de gerar labirintos sem exigir o armazenamento do labirinto inteiro na memória.
• Tamanho é Fundamental: Se você precisa gerar labirintos grandes de forma eficiente, o algoritmo de Eller oferece um desempenho linear que o torna uma opção valiosa.
• Aleatoriedade Visual Limitada: Entretanto, se a aleatoriedade visual for um fator crucial, ou se você precisar de um algoritmo mais simples, considere outras opções. Avalie cuidadosamente suas necessidades antes de tomar uma decisão.

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