Desvendando Labirintos #6 Algoritmo de Prim

Esse é o sexto 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 Prim.

O que é o Algoritmo de Prim?

O algoritmo de Prim é uma técnica poderosa para gerar labirintos, inspirada em um algoritmo clássico da teoria dos grafos para encontrar árvores geradoras mínimas (MST) em grafos ponderados. Além disso, diferentemente de outros, o algoritmo de Prim oferece diferentes abordagens para a criação de labirintos, resultando em texturas e desafios distintos. Neste artigo, exploraremos o algoritmo de Prim, suas variações e como você pode usá-lo para criar labirintos únicos e envolventes.

• Grafo Ponderado: É um grafo em que suas arestas contém pesos (as conexões entre os vértices e possuem custos).
• Árvore Geradora Mínima (MST): O objetivo do algoritmo de Prim. Queremos encontrar um subconjunto de arestas que conecte todos os vértices, sem ciclos, com o menor peso total possível.

O algoritmo de Prim, em sua essência, funciona construindo um labirinto a partir de uma célula inicial, expandindo-o gradualmente até que todas as células estejam conectadas. Então, para entender melhor, imagine que o algoritmo começa com uma única célula e, a cada passo, adiciona a célula vizinha mais próxima (ou mais “barata”) ao labirinto em construção.

O algoritmo de Prim possui duas implementações:

• Simplified Prim: essa é uma versão bastante comum entre os geradores de labirintos, e é frequentemente chamada de “Algoritmo de Prim”. Mas diferente da versão verdadeira, essa não leva em consideração os pesos das arestas. Embora simples de implementar, o Prim Simplificado tende a gerar labirintos com uma textura radial, com caminhos que se irradiam a partir da célula inicial.
• “True” Prim: Para evitar o padrão radial, o Prim “Verdadeiro” atribui um peso aleatório a cada célula e, em seguida, escolhe a célula vizinha com o menor peso para adicionar ao labirinto. Assim, essa abordagem resulta em labirintos com uma aparência mais orgânica e menos previsível.

Passo-a-passo

1. Inicialização:
   • Escolha uma célula aleatória para iniciar o labirinto.
   • Adicione essa célula a um conjunto de células “ativas”.
2. Iteração:
   • Enquanto houver células no conjunto “ativas”:
     • Escolha uma célula do conjunto “ativas” (a estratégia de escolha define a variação do algoritmo).
     • Encontre as células vizinhas da célula escolhida que ainda não fazem parte do labirinto.
     • Se houver vizinhos não visitados:
       • Escolha um vizinho não visitado (a estratégia de escolha define a variação do algoritmo).
       • Crie uma passagem entre a célula atual e o vizinho escolhido.
       • Adicione o vizinho escolhido ao conjunto “ativas”.
     • Caso contrário:
       • Remova a célula atual do conjunto “ativas”.

Algoritmo

Acesse o repositório no GitHub aqui.

Importante! O algoritmo Simplified Prim, 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 SimplifiedPrim : MazeBuilderBaseAlgorithm
{
    public SimplifiedPrim(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 startX = randomStream.Next(Rows);
        var startY = randomStream.Next(Columns);
        
        // The active cell list contains the cells that will be used to search for unvisited neighbors 
        var active = new List<IntPoint> { new IntPoint(startX, startY) };

        while (active.Any())
        {
            var currentIndex = randomStream.Next(active.Count);
            var current = active[currentIndex];
            
            var availableNeighbors = GetAvailableNeighbors(current);
            
            if (availableNeighbors.Any())
            {
                // Choose a random neighbor
                var neighbor = availableNeighbors[randomStream.Next(availableNeighbors.Count)];

                // Remove the wall between the current cell and the neighbor
                HandleWallBetween(current.X, current.Y, neighbor.X, neighbor.Y, true);

                // Add the neighbor to the active cells list
                active.Add(neighbor);
            }
            else
            {
                // Remove the cell from the active list
                active.RemoveAt(currentIndex);
            }
        }
    }
    private List<IntPoint> GetAvailableNeighbors(IntPoint cell)
    {
        var neighbors = new List<IntPoint>();

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

            // Check if cell is valid (not off boundaries and unvisited)
            if (IsValidVertex(nx, ny) && !IsVisited(nx, ny))
            {
                neighbors.Add(new IntPoint(nx, ny));
            }
        }
        return neighbors;
    }
    private bool IsVisited(int x, int y)
    {
        if (Maze is null) return false;
        
        var vertex = Maze[y][x];
        // Check if all walls are closed, if so the cell is not visited yet
        return (vertex.LeftEdge || vertex.RightEdge || vertex.UpEdge || vertex.DownEdge);
    }
}

Desafio

Tente implementar a versão “True” Prim, atribuindo um peso aleatório para cada célula.

Análise de complexidade

• Complexidade de Tempo: A complexidade de tempo do algoritmo de Prim depende da estrutura de dados utilizada para gerenciar as células candidatas.
  • Com uma fila de prioridade implementada com um heap binário, a complexidade é O(n log n), onde n é o número de células.
  • Com uma busca linear simples, a complexidade pode chegar a O(n^2).
• Complexidade de Espaço: O algoritmo de Prim requer memória proporcional ao número de células no labirinto, resultando em uma complexidade de espaço O(n).

Prós

• Fácil de Implementar: Apesar de suas nuances, o algoritmo de Prim é relativamente fácil de implementar, especialmente em sua versão simplificada.
• Garantia de Conectividade: O algoritmo garante que todas as células do labirinto estarão interligadas, dessa forma assegurando que o jogador sempre possa encontrar um caminho de um ponto a outro.
• Flexibilidade na Textura do Labirinto: o algoritmo de Prim possibilita a criação de labirintos com uma variedade de texturas visuais, desde padrões radiais até formações mais orgânicas, assim permitindo diferentes estratégias de seleção de células.

Contras

• Possível Tendência a Texturas Radiais: Em algumas implementações, o algoritmo de Prim pode gerar labirintos com uma textura radial, resultando então em um visual menos natural ou aleatório.
• Potencial para Muitos Becos Sem Saída: Em certas configurações, o algoritmo de Prim pode produzir labirintos com um número elevado de becos sem saída, e dessa forma aumentar a dificuldade de navegação para o jogador.
• Consumo de Memória Linear: O algoritmo de Prim requer memória proporcional ao número de células no labirinto, e assim pode torná-lo inadequado para labirintos extremamente grandes ou sistemas com recursos limitados.

Quando usar este algoritmo?

• Controle a Textura do Labirinto: Utilize o algoritmo de Prim quando desejar influenciar a aparência visual do labirinto, dessa forma explorando diferentes estratégias de seleção de células para criar padrões específicos.
• Priorize a Conectividade Completa: Além disso, empregue este algoritmo quando for essencial garantir que todas as áreas do labirinto sejam acessíveis, assegurando que não haja regiões isoladas.
• Considere o Tamanho do Labirinto e os Recursos: Avalie cuidadosamente o tamanho do labirinto e a disponibilidade de memória, já que o consumo de memória linear pode ser um fator limitante em certos casos.
• Otimize o Desempenho com Estruturas de Dados Eficientes: Por fim, para obter o melhor desempenho, utilize uma fila de prioridade implementada com um heap binário para gerenciar as células candidatas.

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