Desvendando Labirintos #5: Algoritmo Hunt and Kill

Esse é o quinto 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 Hunt and Kill.

Passo-a-passo

1. Crie uma grade de células, com todas arestas marcadas como paredes.
2. Depois, escolha uma célula inicial aleatória e marque-a como parte do labirinto.
3. Enquanto houver células não visitadas:
   • Se a célula atual tem vizinhos não visitados:
     • Escolha aleatoriamente um vizinho não visitado.
     • Remova a parede entre a célula atual e o vizinho.
     • Mova-se para o vizinho.
   • Caso contrário, busque uma célula morta que tenha vizinhos visitados:
     • Se encontrar uma, mova-se para lá e continue.
     • Se não encontrar, o algoritmo termina.

Algoritmo

Acesse o repositório no GitHub aqui.

Importante! O algoritmo Hunt and Kill, 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 HuntAndKillAlgorithm : MazeBuilderBaseAlgorithm
{
    public HuntAndKillAlgorithm(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;
        }
        
        // Track visited vertices, initializing with all unvisited
        var visited = Enumerable.Repeat(false, Rows * Columns).ToList();
        
        // Initializing the random stream
        var randomStream = seed == -1 ? new Random() : new Random(seed);
        
        // Visiting the first vertex
        var currentX = randomStream.Next(0, Rows-1);
        var currentY = randomStream.Next(0, Columns-1);
        visited[GetVertexIndex(currentX, currentY)] = true;
        
        bool bHuntPhase = false;

        while (true)
        {
            // Set vertex neighbors
            var neighbors = new List<IntPoint>();

            // Looking for non visited neighbors
            foreach (var direction in Directions.OrderBy(d => randomStream.Next()))
            {
                var newX = currentX + direction.X;
                var newY = currentY + direction.Y;

                if (IsValidVertex(newX, newY) && !visited[GetVertexIndex(newX, newY)])
                {
                    neighbors.Add(new IntPoint(newX, newY));
                }
            }

            // Found vertex's non visited neighbor
            if (neighbors.Count > 0)
            {   
                // Choose random neighbor
                var chosenNeighbor = neighbors[randomStream.Next(0, neighbors.Count-1)];
                
                // Add a vertex between current vertex and the current neighbor
                HandleWallBetween(currentX, currentY, chosenNeighbor.X, chosenNeighbor.Y, true);
                
                // Move the current vertex to the selected neighbor and check as visited
                currentX = chosenNeighbor.X;
                currentY = chosenNeighbor.Y;
                visited[GetVertexIndex(currentX, currentY)] = true;

                bHuntPhase = false;  // Still on "Kill" phase
            }
            
            // Start hunt phase if all neighbors are already visited
            else if (!bHuntPhase)
            {
                bHuntPhase = true;
                var bFoundNewStart = false;
                
                // Look for a non visited vertex that has at least one visited neighbor
                for (var y = 0; y < Columns; ++y)
                {
                    for (var x = 0; x < Rows; ++x)
                    {
                        // Found a non visited vertex
                        if (!visited[GetVertexIndex(x, y)])
                        {
                            // Check if it has a visited neighbor
                            foreach (var direction in Directions)
                            {
                                var newX = x + direction.X;
                                var newY = y + direction.Y;

                                // Connect the yet not visited vertex to the visited neighbor
                                if (IsValidVertex(newX, newY) && visited[GetVertexIndex(newX, newY)])
                                {
                                    HandleWallBetween(x, y, newX, newY, true);
                                    currentX = x;
                                    currentY = y;
                                    visited[GetVertexIndex(currentX, currentY)] = true;
                                    bFoundNewStart = true;
                                    break;
                                }
                            }
                            if (bFoundNewStart)
                            {
                                break;
                            }
                        }
                    }
                    if (bFoundNewStart)
                    {
                        break;
                    }
                }
                if (!bFoundNewStart)
                {
                    break;
                }
            }
            // Finish current hunt
            else
            {
                bHuntPhase = false;
            }
        }
    }
}

Análise

O algoritmo funciona em duas fases principais:

• Kill Phase: Anda aleatoriamente a partir de um ponto inicial, marcando células como visitadas e criando passagens, até que fique preso (sem vizinhos não visitados).
• Hunt Phase: “Caça” por uma nova célula não visitada que tenha um vizinho já visitado. Quando encontra, abre um caminho para o vizinho e retorna à fase de caminhada aleatória.

Em relação à memória, o labirinto é representado como uma lista de listas (List<List<MazeVertex>>), onde cada célula é um objeto MazeVertex que contém informações sobre suas quatro arestas. Além disso, o algoritmo precisa de uma estrutura adicional para rastrear as células visitadas (uma lista de valores booleanos).

• Complexidade de Tempo: O(n^2) (no pior caso) – No pior caso, a fase de caça pode exigir que o algoritmo percorra toda a grade para encontrar uma célula adequada, resultando em uma complexidade de tempo quadrática em relação ao número de células (n).
• Complexidade de Espaço: O(n) – A complexidade de espaço é linear em relação ao número de células (n). Isso ocorre devido a:
  • Representação do Labirinto: O labirinto é armazenado como uma lista de listas (ou array bidimensional), onde cada célula (vértice) contém informações sobre suas arestas.
  • Rastreamento de Células Visitadas: O algoritmo precisa de uma estrutura para rastrear as células que já foram visitadas durante a caminhada aleatória e a fase de caça (por exemplo, uma lista de valores booleanos).

Prós

• Cria Labirintos com Longos Corredores Interconectados: O Hunt and Kill gera labirintos com longos corredores sinuosos e interconectados, e, como resultado, proporciona uma intensa sensação de exploração e descoberta ao jogador.
• Garante a Conectividade do Labirinto: Graças à combinação da caminhada aleatória com a fase de caça, o algoritmo garante que todas as áreas do labirinto sejam acessíveis, o que, por conseguinte, evita a criação de regiões isoladas e sem saída.
• Gera Menos Bicos Sem Saída: Em virtude de sua lógica de construção, o Hunt and Kill tende a gerar menos becos sem saída em comparação com outros algoritmos, o que, por conseguinte, resulta em uma experiência de navegação mais fluida e menos frustrante para o jogador.

Contras

• Ineficiência na Fase de Caça: Embora essencial, a fase de caça pode ser ineficiente em labirintos grandes, pois exige percorrer a grade para encontrar células.
• Pouca Variedade: Por causa da ênfase em corredores longos, o Hunt and Kill pode gerar labirintos com pouca variedade, e então reduzir o interesse a longo prazo.
• Consumo Linear de Memória: Torna-se inadequado para labirintos grandes ou sistemas com recursos limitados, já que o algoritmo Hunt and Kill requer memória proporcional ao número de células.
• Impacto da Estratégia de Busca: Finalmente, a estratégia de busca na fase de caça afeta a estrutura do labirinto, portanto exige experimentação.

Quando usar este algoritmo?

• Incentive a Exploração com Corredores Longos: Utilize o Hunt and Kill para gerar labirintos que incentivem a exploração, pois seus corredores sinuosos proporcionam imersão.
• Minimize a Frustração com Poucos Bicos Sem Saída: Empregue este algoritmo quando a facilidade de navegação for importante, já que ele tende a produzir labirintos com menos becos sem saída.
• Priorize a Simplicidade em Labirintos Moderados: Escolha o Hunt and Kill quando a simplicidade for crucial, pois ele oferece uma implementação direta, especialmente em labirintos de tamanho moderado, onde o consumo de memória linear não se torna um fator limitante.
• Crie Variedade com Estratégias de Busca: Explore diferentes estratégias de busca para criar labirintos com texturas distintas, já que a fase de caça oferece flexibilidade na definição do padrão de exploração, o que, por sua vez, permite adaptar o algoritmo a diferentes estilos e desafios.

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