Desvendando Labirintos #3: Algoritmo Depth-First Search (DFS)

Esse é o terceiro 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 Depth-First Search.

O algoritmo Depth-First Search (DFS) é uma técnica clássica para geração e resolução de labirintos que explora células a partir de um ponto inicial, avançando o máximo possível em uma direção antes de voltar e tentar outra rota. Primeiramente, vamos explorar essa técnica para gerar labirintos, e mais futuramente vamos explorar o seu uso para encontrar um caminho.

Passo-a-passo

1. Inicialize a grade de vértices com todas as arestas marcadas como parede.
2. Escolha um vértice inicial e a marque como visitada.
3. Empilhe esse vértice em uma pilha.
4. Enquanto a pilha não estiver vazia:
   • Pegue o topo da pilha (vértice atual).
   • Encontre um vizinho não visitado da célula atual.
     • Se houver um vizinho não visitado:
       • Escolha esse vizinho aleatoriamente.
       • Remova a parede entre a célula atual e o vizinho.
       • Marque o vizinho como visitado e empilhe-o.
     • Se não houver vizinhos, desempilhe a célula do topo da pilha (retrocede para a última célula com vizinhos não visitados).
5. Repita o passo 4 até visitar todas as células.

Algoritmo

Acesse o repositório no GitHub aqui.

Importante! O algoritmo Depth-First Search, 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 DepthFirstSearch : MazeBuilderBaseAlgorithm
{
    public DepthFirstSearch(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);

        var visited = new bool[Rows, Columns];

        // Initialize DFS stack
        Stack<IntPoint> stack = new Stack<IntPoint>();

        // Choose a random first vertex
        var startX = randomStream.Next(Rows);
        var startY = randomStream.Next(Columns);
        stack.Push(new IntPoint(startX, startY));
        visited[startX, startY] = true;

        // Execute DFS
        while (stack.Count > 0)
        {
            var current = stack.Peek();
            var x = current.X;
            var y = current.Y;

            // Get all unvisited neighbors
            var unvisitedNeighbors = GetUnvisitedNeighbors(x, y, visited);

            if (unvisitedNeighbors.Count > 0)
            {
                // Choose random neighbor
                var next = unvisitedNeighbors[randomStream.Next(unvisitedNeighbors.Count)];

                // Remove wall between current vertex and neighbor
                HandleWallBetween(x, y, next.X, next.Y, true);

                // Stack and check neighbor as visited
                visited[next.X, next.Y] = true;
                stack.Push(next);
            }
            else
            {
                stack.Pop();
            }
        }
    }

    private List<IntPoint> GetUnvisitedNeighbors(int x, int y, bool[,] visited)
    {
        var neighbors = new List<IntPoint>();

        foreach (var direction in Directions)
        {
            int nx = x + direction.X;
            int ny = y + direction.Y;

            if (IsValidVertex(nx, ny) && !visited[nx, ny])
            {
                neighbors.Add(new IntPoint(nx, ny));
            }
        }
        return neighbors;
    }
}

Desafio

Reescreva o algoritmo utilizando recursão no trecho de execução da DFS, para uma implementação mais elegante e limpa. Isso significa substituir o loop while por uma nova função que vai fazer chamas à ela mesma enquanto stack.Count > 0.

Análise de complexidade

• Complexidade de Tempo: O(V+E) – Onde V é o número de vértices (células) e E é o número de arestas (conexões entre as células). Assim, em um labirinto, E é geralmente proporcional a V, então a complexidade pode ser simplificada para O(V) ou O(n), onde n é o número de células.
• Complexidade de Espaço: O(V) – A complexidade de espaço é dominada pelo tamanho da pilha, então pode crescer até o número de vértices no pior caso (um caminho longo e linear).

Prós

• Crie Labirintos Progressivamente Desafiadores: Empregue o DFS para gerar labirintos que inicialmente apresentam passagens longas e diretas, mas que, gradualmente, desenvolvem uma complexa rede de ramificações. Dessa forma, você oferece aos jogadores um desafio crescente e envolvente, que exige cada vez mais habilidade e estratégia para ser superado.
• Simplifique a Implementação Através da Recursão: Opte pela recursão ao implementar o DFS, pois essa abordagem elegante e concisa não apenas facilita o desenvolvimento, mas também torna o código mais fácil de compreender e manter. Contudo, lembre-se de monitorar a profundidade da recursão para evitar problemas de estouro de pilha em labirintos extensos.

Contras

• Dificuldade em Otimizar o Caminho: Embora eficiente na geração, o DFS dificulta a otimização do caminho mais curto entre dois pontos, uma vez que não foi projetado inerentemente para encontrar a solução mais eficiente. Por isso, considere outras opções se a otimização do caminho for crucial.
• Tendência a Labirintos Monótonos: Em certas situações, o DFS pode gerar labirintos monótonos, com longos corredores e poucas ramificações, o que, por sua vez, pode não ser ideal para jogos ou aplicações que exigem variedade e surpresas.
• Requer Gestão Cuidadosa da Pilha de Recursão: Devido à sua natureza recursiva, esteja ciente do risco de estouro da pilha, especialmente ao gerar labirintos grandes. Assim, torna-se essencial gerenciar cuidadosamente a profundidade da recursão ou optar por uma implementação com pilha explícita.
• Gera Labirintos Desbalanceados: Por fim, observe que o DFS tende a explorar um lado do labirinto mais profundamente antes de explorar outros, o que, em última análise, pode resultar em um labirinto desbalanceado, com algumas áreas mais densas que outras.

Quando utilizar este algoritmo?

• Crie Labirintos Progressivamente Desafiadores: Utilize o DFS para gerar labirintos que se tornam mais complexos à medida que o jogador avança. De fato, o DFS naturalmente cria áreas iniciais com caminhos mais longos e diretos, enquanto as seções mais profundas do labirinto apresentam uma teia intrincada de becos sem saída e bifurcações, desse modo proporcionando uma curva de aprendizado suave e envolvente.
• Aproveite a Não Uniformidade para Experiências Únicas: Explore a tendência do DFS de criar labirintos não uniformes, com áreas mais densas e outras mais esparsas. Em vez de tentar forçar a uniformidade, abrace essa característica para criar ambientes distintos e memoráveis, o que pode ser particularmente útil para jogos que exploram diferentes temas ou regiões.
• Priorize a Simplicidade do Código (Com Consciência): Escolha o DFS quando a simplicidade e a facilidade de manutenção do código forem prioridades. Embora existam, algoritmos mais complexos que ofereçam maior controle sobre a estrutura do labirinto, o DFS oferece uma solução elegante e facilmente compreendida e modificada. Contudo, lembre-se sempre de considerar as limitações da recursão e o potencial para estouro da pilha em labirintos muito grandes.

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