Desvendando Labirintos #1: Tudo sobre algoritmos de geração

Decidi criar essa série de posts sobre como gerar labirintos para jogos como uma forma de estudo para um projetinho que estou desenvolvendo. A ideia é explorar diferentes algoritmos, desde os mais simples até os mais complexos, e entender como cada um pode contribuir para criar labirintos intrigantes e desafiadores. Afinal, cada um tem suas peculiaridades. Enquanto uns tem corredores mais longos e retos, outros são mais sinuosos e com mais becos, por exemplo.

Se você fez ou faz faculdade na área de computação, talvez você se lembre de alguns conceitos daquelas matérias um tanto quanto traumáticas, como estruturas de dados avançadas, estruturas dicretas ou análise de algoritmos. Bem como algumas palavrinhas mágicas: BFS, DFS, Kruskal, Djkstra e A*. Mas prometo que vai ser divertido kkk.

Alguns dos jogos que mais me inspiraram com seus labirintos desafiadores são Labyrinthine, Legend of Grimrock, Ragnarok Online, The Legend of Zelda, e até aqueles que exploram a vibe misteriosa dos Backrooms. O legal é que cada jogo tem sua abordagem única: enquanto alguns geram os labirintos de forma procedural — sempre garantindo uma surpresa nova — outros investem em designs feitos manualmente, com detalhes super caprichados, por exemplo.

Em resumo, vou compartilhar o que aprender ao longo dessa jornada em novas postagens. Assim, cada novo post, eu vou atualizar esse aqui para que fique como uma forma de índice para facilitar a organização.

Planejamento

Durante essa série, utilizaremos a linguagem C# para explorar diversos algoritmos de geração de labirintos. Cada postagem será dedicada a um algoritmo específico, permitindo um aprofundamento em cada técnica. Após abordarmos todos os algoritmos de geração, teremos duas postagens especiais focadas em um algoritmos para encontrar o melhor caminho através dos labirintos gerados.

Em seguida, vamos desenvolver uma API utilizando .NET, a qual retornará os resultados dos algoritmos de forma eficiente. Essa etapa é mais voltada para a didática e a organização do código, permitindo a reutilização dos algoritmos em diferentes aplicações, evitando sua reescrita e garantindo o encapsulamento. Mas, na prática, se o objetivo for apenas um jogo ou uma página web, pode ser mais vantajoso deixar os algoritmos embutidos no próprio código da aplicação.

Por fim, planejamos desenvolver um webapp com a framework Next.js, permitindo que os usuários gerem labirintos aleatórios, solucionem os desafios e exportem os resultados em formato PDF. Essa aplicação proporcionará uma experiência interativa e prática, integrando a geração e resolução de labirintos de forma intuitiva e acessível.

Índice

• Desvendando Labirintos #1: Tudo sobre algoritmos de geração
• Desvendando Labirintos #2: Algoritmo de Árvores Binárias
• Desvendando Labirintos #3: Algoritmo Depth-First Search (DFS)
• Desvendando Labirintos #4: Algoritmo Recursive Division
• Desvendando Labirintos #5: Algoritmo Hunt and Kill
• Desvendando Labirintos #6 Algoritmo de Prim
• Desvendando Labirintos #7: Algoritmo de Eller
• Desvendando Labirintos #8: Algoritmo Randomized Kruskal <EM BREVE>
• Desvendando Labirintos #9: Algoritmo Sidewinder <EM BREVE>
• Desvendando Labirintos #10: Algoritmo de Aldous-Broder <EM BREVE>
• Desvendando Labirintos #11: Algoritmos de melhor caminho para grafos (Parte 1 – Introdução, BFS e DFS) <EM BREVE>
• Desvendando Labirintos #12: Algoritmos de melhor caminho para grafos (Parte 2 – Djikstra e A Estrela) <EM BREVE>
• Desvendando Labirintos #13: Montando uma API de labirintos utilizando .Net <EM BREVE>
• Desvendando Labirintos #14: Criando uma WebApp Next.js com puzzles <EM BREVE>

Antes de começar…

Temos alguns elementos em comum que vamos utilizar em todos os algoritmos:

• Vamos utilizar uma estrutura de dados que é composta por um vértice com 4 arestas, onde cada uma representa os caminhos para cima (up), para baixo (down), para a esquerda (left) e para a direita (right). Cada aresta possui um valor booleano, onde true siguinifica que possui passagem e false significa que possui parede.
  • Um vértice, uma célula ou um tile são 3 formas de se referir a uma “sala” em um labirinto.
  • Uma aresta representa uma parede (ou alguma forma de bloquear o caminho) ou uma passagem para outro vértice vizinho
• A seguir temos a classe que vamos utilizar para representar um vértice:

namespace MazeBuilderAPI.Models.Internal;

public class MazeVertex
{
    public bool UpEdge { get; set; } = false;
    public bool DownEdge { get; set; } = false;
    public bool LeftEdge { get; set; } = false;
    public bool RightEdge { get; set; } = false;

    public MazeVertex(bool upEdge, bool downEdge, bool leftEdge, bool rightEdge)
    {
        UpEdge = upEdge;
        DownEdge = downEdge;
        LeftEdge = leftEdge;
        RightEdge = rightEdge;
    }
}

• A classe a seguir vamos utilizar para representar coordenadas (X, Y) para ajudar na movimentação de um vértice para outro.

namespace MazeBuilderAPI.Models.Internal;

public struct IntPoint
{
    public int X { get; }
    public int Y { get; }

    public IntPoint(int x, int y)
    {
        X = x;
        Y = y;
    }

    // Override do ToString() para facilitar a visualização
    public override string ToString() => $"({X}, {Y})";
}

• Os algoritmos vão utilizar funções e parâmetros em comum, como inicializador, removedor de paredes, e outros. Então para não repetir código, vamos fazer eles todos herdarem de uma classe que possui tudo o que for compartilhado.

using MazeBuilderAPI.Models.Internal;

namespace MazeBuilderAPI.Algorithms.Maze;

public class MazeBuilderBaseAlgorithm
{
    protected List<List<MazeVertex>>? Maze { get; set; }
    
    // Use this array to move between vertex (up, down, left and right)
    protected List<IntPoint> Directions =
    [
        new IntPoint(0, -1),
        new IntPoint(0, 1),
        new IntPoint(-1, 0),
        new IntPoint(1, 0)
    ];
    
    protected int Rows { get; init; }
    protected int Columns { get; init; }

    // Get vertex index using (x, y) coordinates
    protected int GetVertexIndex(int x, int y) => y * Rows + x;
        
    // Check if vertex exists
    protected bool IsValidVertex(int x, int y) => x >= 0 && x < Rows && y >= 0 && y < Columns;
    
    // Connect two vertex setting the edge between them to true
    protected void HandleWallBetween(int x1, int y1, int x2, int y2, bool bRemoveWall)
    {
        if (Maze is null) return;
            
        if (x1 == x2)
        {
            if (y1 < y2)
            {
                Maze[y1][x1].DownEdge = bRemoveWall;
                Maze[y2][x2].UpEdge = bRemoveWall;
            }
            else
            {
                Maze[y1][x1].UpEdge = bRemoveWall;
                Maze[y2][x2].DownEdge = bRemoveWall;
            }
        }
        else if (y1 == y2)
        {
            if (x1 < x2)
            {
                Maze[y1][x1].RightEdge = bRemoveWall;
                Maze[y2][x2].LeftEdge = bRemoveWall;
            }
            else
            {
                Maze[y1][x1].LeftEdge = bRemoveWall;
                Maze[y2][x2].RightEdge = bRemoveWall;
            }
        }
    }
    
    protected bool Initialize(bool bAddWalls)
    {
        if (Rows == 0 || Columns == 0) return false;
        
        Maze = [];
        
        for (var i = 0; i < Columns; i++)
        {
            Maze.Add([]);
            for (var j = 0; j < Rows; j++)
            {
                Maze[i].Add(bAddWalls
                    ? new MazeVertex(false, false, false, false)
                    : new MazeVertex(true, true, true, true));
            }
        }
        if (!bAddWalls) // Add the maze limits if it's initialized with no wall
        {
            for (var i = 0; i < Rows; i++)
            {
                Maze[0][i].UpEdge = false;
                Maze[Columns - 1][i].DownEdge = false;
            }
            for (var i = 0; i < Columns; i++)
            {
                Maze[i][0].LeftEdge = false;
                Maze[i][Rows - 1].RightEdge = false;
            }
        }
        return true;
    }
    
    
    /*
     * Convert the Maze class to the response class of the API. If necessary, implement it.
     */
    public List<List<MazeVertex>>? ConvertMazeToResponseType()
    {
        return Maze;
    }
}

Testes

Ao final da série, irei fazer uma postagem sobre a construção de uma WebApp e disponibilizar o seu repositório do GitHub. Mas enquanto isso, para realizar os testes sugiro criar uma WebApp com Next.js e TailwindCSS com o seguinte arquivo:

export async function getServerSideProps() {
    process.env.NODE_TLS_REJECT_UNAUTHORIZED = "0"

    const res = await fetch(
        `${process.env.MAZE_API_URI}?height=25&width=25&mazeAlgorithm=HuntAndKill&seed=-1`,
        {
            method: "GET",
            headers: {
                "Content-Type": "application/json",
            }
        }
    );
    const maze = await res.json();

    return {
        props: {
            maze,
        }
    }
}


function HomeScreen({ maze }) {
    return (
        <div className="flex flex-col items-center my-5">
            {maze.map((row, rowIndex) => (
                <div key={rowIndex} className="flex">
                    {row.map((cell, cellIndex) => {
                        return(
                            <div
                                key={cellIndex}
                                className={`w-8 h-8 border-2 
                                ${cell.upEdge ? 'border-t-white' : 'border-t-black'} 
                                ${cell.downEdge ? 'border-b-white' : 'border-b-black'} 
                                ${cell.leftEdge ? 'border-l-white' : 'border-l-black'} 
                                ${cell.rightEdge ? 'border-r-white' : 'border-r-black'}`}
                            ></div>
                        )
                    })}
                </div>
            ))}
        </div>
    )
}

export default HomeScreen;

Agora, para testar basta utilizar os algoritmos dessa série em um endpoint de uma API, onde a assinatura do endpoint corresponda a assinatura utilizada na requição fetch cima. Além disso, o retorno da requisição precisa ser um json correspondente à uma lista de listas da classe MazeVertex vista anteriormente.

Para finalizar, tendo isso basta rodar a API e o WebApp localmente e acessar http://localhost:3000 para visualizar o labirinto gerado.

Por fim…

Ao final da série, você aprenderá técnicas de como gerar labirintos para jogos em C#. E terá um WebApp para gerar quantos labirintos quiser! E o mais legal é que você pode usar seeds para gerar o mesmo labirinto repetidas vezes.

Ah, e se quiser uns desafios legais, aqui vão alguns:

• Você pode reescrever esses algoritmos em outras linguagens como Python, Ruby, ou qualquer uma que seja a mais interessante para a sua aplicação.
• Sabe aquele WebApp? Que tal dar um upgrade nele e utilizar assets gratuitos da internet para fazer labirintos bonitos? Você ainda pode salvar como pdf ou imprimir para dar para alguma criança brincar. Aqui estão alguns sites com assets gratuitos: Kenney, Itch.io
• Se quiser um desafio ainda mais interessante, você pode fazer um jogo simples em qualquer engine (mas recomendo Godot ou Unity) que em cada fase seja gerado um labirinto, e o jogador deve encontrar a saída.

Depois, se você quiser, compartilhe o seu resultado! Pode me mandar por e-mail, direct em redes sociais ou compartilhar nos comentários.

Quero me aprofundar ainda mais!

• E se eu quiser que meus vértices sejam triângulares ou hexagonais ao invés de quadrados?
• Alguns labirintos também podem ser tridimensionais, né? Por exemplo um prédio com vários andares. Imagina você andando em um labirinto e se depara com uma escada para subir ou descer para outro labirinto várias vezes.
• Ou então você pode ir mais ao pé da letra quando se trata de tridimensional. Existem labirintos esféricos, cilindricos…
• Mais um exemplo: labirintos que têm caminhos de um vértice para outro passando por outros andares. Lembra do caso do prédio? Agora imagina fazer um labirinto que o jogador pode precisar passar por vários andares para poder chegar ao final.
• Parecido com o anterior, existem labirintos “trançados”, conhecidos como Weavy Mazes… Meio que você passa por de baixo de um caminho para poder continuar (como uma ponte) … Sei nem como explicar kkk
• Estamos falando de jogos, né? Normalmente temos terrenos mais difíceis que outros, não? Andar na água é mais devagar do que na terra… Encontrar um monstro em uma sala, vai te atrapalhar a passar também. Por isso quando falamos de algoritmos de melhor caminho, podemos atribuir pesos aos vértices. Ou seja, às vezes o menor caminho não é o melhor. Imagina você é um jovem aventureiro level 1 e pode escolher entre passar por um caminho curto com vários Tonberries, Cactuar e um Rathalos ou um bem longo com vários Porings, Fabres e Lunáticos.

Então ainda tem muito estudo pela frente se o seu objetivo for se aprofundar ainda mais sobre labirintos. Certamente, um bom ponto de partida é pesquisar sobre Jamis Buck, autor do livro Maze for Programmers. Esse livro aborda alguns tópicos que citei anteriormente e aprofunda ainda mais nos algoritmos que discutimos. E se quiser, tem o link para o livro na parte de referências.

Referências

Agora vou listar alguns dos materiais que mais utilizei para estudar sobre como gerar labirintos para jogos. Assim, espero que te ajude a entender ainda mais sobre esse assunto!

1. Maze for Programmers: Code Your Own Twisty Little Passages

Jamis Buck é o resulto número 1 quando se pesquisa sobre labirintos em qualquer lugar da internet. Nesse livro ele compila todo seu conhecimento sobre esse assunto, com exemplos práticos utilizando Ruby.

2. 8 Maze Generating Algorithms in 3 minutes