Labirintos com Delphi

Uma das coisas boas da programação é a diversão que ela proporciona. Só o ato de desenvolver sistemas já é, muitas vezes, divertido, e desenvolver aplicações que geram momentos marcantes é muito bom.

Em determinado momento tive a curiosidade de pesquisar sobre algorítmos de criação de labirintos (em inglês, mazes). Fiquei surpeso com a quantidade de algorítmos diferentes existentes para isso. Percebi que existem, aliás, diferentes tipos de labitintos, dos quais nunca havia ouvido falar a respeito.

Fui levado a diferentes literaturas, das quais, indico Mazes for Programmers, de Jamis Buck. Para aqueles que de alguma forma não conseguem adquirir o livro, sugiro a leitura do conteúdo no site do próprio autor, que já elucidará o suficiente o neófito de criação de labirintos – http://weblog.jamisbuck.org/under-the-hood.

Abaixo vamos desenvolver labirintos utilizando-se três diferentes tipos de algorítmos – e acredite, existem muito mais tipos.

Antes de começarmos

Existem diferentes tipos de labirintos. O labirinto tradicional consiste de um quadrado ou retângulo, cujo interior é divido de forma a criar as passagens do labirintos. Todavia, existem diversos outros tipos, como labirintos circulares, triangulares, hexagonais, multidimensionais, etc. Estaremos aqui nos referindo apenas aos labirintos tradicionais.

Assim, trataremos cada labirinto como uma matriz de dimensões N x N, com todas as paredes em todas as células, conforme a figura abaixo:

Binary Tree

O algorítmo de árvore binária para desenvolvimento de labirintos é talvez o mais simples de todos. Ele baseia-se no conceito:

  • Escolha duas direções que não sejam opostas. Ex: Norte e Leste. Poderia ser Norte e Oesta, como Sul e Leste. O importante é não se oporem.
  • Todas as céulas encostadas nas paredes dessas direções devem possuir uma passagem entre sí. Imagine que a escolha tenha sido Norte e Leste. Nesse caso, todas as células encostadas nas paredes Norte e Leste deverão estar ligadas:

  • Uma vez isso feito, para cada célula do labirinto, que não sejam essas células já abertas, faça uma escolha entre essas duas direções, e crie uma passagem nela.

Pronto, está criado seu labirínto. Você terá algo como:

Devido essa simplicidade e uniformidade, sem a existência de nenhuma dependência para a operação de cada célula, esse algorítmo é facilmente portado em uma lógica para processamento paralelo, além de utilizar o mínimo de memória, visto que não armazena nenhuma informação.

Sidewinder

O seu entendimento é um tanto confuso, mas depois que “pegamos o jeito”, vemos a sua engenhosidade.

A primeira coisa é entendermos que para o funcionamento desse algorítmo, vamos precisar criar diferentes “ambientes”. Chamo aqui de ambiente um dado corredor, dentro do labirinto.

Considere o labirinto 3 x 3 abaixo:

Um ambiente, é um corredor, conforme pode ser observado abaixo, grifado em vermelho:

Não importa se esse corredor possui apenas 1 casa, ou várias casas. Essa diferenciação é o que dará a “sensação” de um labirinto.

Partindo da posição inicial (0, 0 – primeira célula na esquerda, no topo), vamos linha a linha, de cima para baixo, com a seguinte lógica:

  • Se for a primeira linha, abra passagem por ela toda. Isso mesmo, a primeira linha inteira é um único ambiente. Isso é necessário para que seja possível interligar todos os ambientes.
  • Para as próximas linhas, sorteie um número, que seja entre 1 ao total de células disponíveis da linha, e abra o caminho entre essas células. Como é? Isso mesmo. Entre 1 ao total de células disponíveis da linha.

Vamos partir do segunda passo, quando já temos a primeira linha aberta:

Temos que a segunda linha possui 3 células disponíveis. Assim, vou fazer um sorteio entre 1 à 3, pois 3 é o total de células disponíveis. Vamos dizer que o número sorteado foi 2. Assim, tenho que as duas primeiras células terão passagem:

  • A próxima etapa a ser feita, é criar uma passagem para a linha de cima. Para isso, vamos sortear novamente, mas agora apenas entre as células do ambiente criado, ou seja, entre a primeira e segunda célula. Vamos dizer que, novamente, o número sorteado foi 2 – não se preocupe agora com quais números são sorteados. Isso realmente não importa. Depois você verá que qualquer número daria certo, embora produza um desenho de labirinto diferente.

Assim, como a segunda célula foi sorteada, fazemos uma passagem na segunda célula para a linha de cima:

Pronto. Agora vamos para o próximo passo.

  • Faça novamente a primeira e segunda etapa, para as células restantes da mesma linha.

Hein?

Ok, vou explicar. No nosso exemplo, temos apenas 3 colunas, por isso não é tão perceptível isso, mas o labirinto poderia ser de uma dimensão, 10 x 10 por exemplo. Nós tratamos apenas a primeira e segunda célula. Ainda faltam todas as outras células para a mesma linha. Como no nosso exemplo temos apenas 1 coluna restante, o sorteio vai entre 1 e 1. Assim, temos que a terceira coluna apenas – a única que restou – é a sorteada, e ela também recebe a abertura da passagem para a linha de cima, porque é a única célula a ser sorteada. Assim:

Perceba que o nosso labirinto já está ganhando forma.

  • Repita o mesmo passo inicial da linha 2 para os restantes das linhas. Vamos imaginar que, conforme o sorteio, na terceira linha a primeira célula seja a única escolhida, e depois, as dúas últimas células foram escolhidas. O desenho ficaria mais ou menos assim:

Pronto!

Está finalizado o labirinto, através do algorítmo sidewinder.

Recursive Backtracking

Na minha opnião, o melhor dos três labirintos. Seu desenho é muito mais agradável, e parece-se muito com aqueles labirintos dos almanaques da turma da Mônica – você sabe do que estou falando!.

Ele é um pouco mais complexo, mas nada que seja fora do comum.

  •  Escolha qualquer célula do labirinto randomizamente. Essa passa a ser a célula  ativa. Marque ela como uma célula visitada.
  • Partindo da posição da célula ativa, escolha um lado. Se esse lado ainda não foi visitado, cave uma passagem para ele. Essa célula imediata ao lado escolhido passa a ser a célula ativa.
  • Comece novamente o processo para a célula ativa.
  • Na escolha dos lados, se a célula do lado escolhido já foi visitada, escolha outro lado. Se todos os lados foram visitados, volte para a célula anterior. Ela se torna a célula ativa.
  • Continue o processo até que não existem mais lados disponíveis quando a célula ativa for a primeira célula escolhida, randomicamente.

Um ponto a prestar atenção aqui é que, como ele utiliza-se da recursividade, é possível que ele cause um estouro na stack caso suas dimensões sejam muito grande, então fique muito com isso. Uma possibilidade é alterar a directiva $MAXSTACKSIZE, para interferir na forma como o Delphi solicita a memória. Para saber mais a respeito, click aqui.

Legal, mas cadê a porta?

Já tinha percebido que não havíamos criado nenhuma porta de entrada ou de saída em nossos labirintos? Pois bem, isso é de fácil solução, mas deixo aqui como um exercício para você pensar um pouco.

Conclusão

Espero que você tenha gostado de aprender sobre desenvolvimento de labirintos – mazes – no Delphi, tanto quanto gostei de compartilhar isso com você.

Abaixo está um link para o projeto que desenvolvi para a geração de labirintos.

Link

Obtenha o exemplo do projeto aqui!

2 respostas para “Labirintos com Delphi”

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *