A lógica dos labirintos

Além de prender minotauros e abrigar faunos, os labirintos podem servir como ótimos passatempos. Portanto resolvi mostrar como criar, de forma “aleatória”, inúmeros labirintos.

Para isso devemos definir uma matriz e suas ligações. Para facilitar a exemplificação, irei trabalhar com uma matriz de 5 colunas e 4 linhas. Após isso, nosso algoritmo deve começar a partir de um dos elementos. Vamos escolher o primeiro e defini-lo como visitado e escolher aleatoriamente um vizinho ligado a ele. E a partir do vizinho repetir o processo, marcar como visitado e escolher outro disponível não visitado. Quando chegar a algum elemento que não possua mais ligações ou vizinhos não visitados, devemos retroceder no caminho até encontrar algum vizinho disponível.

Após percorrer todos os elementos, consideramos que as bordas e os caminhos que não percorremos (linhas pretas) serão as paredes do labirinto.

Bom, a lógica é essa. Agora vamos colocar a mão na massa é codificar. Nesse tutorial irei mostrar utilizando JavaScript, mas você pode adaptar facilmente para qualquer outra linguagem.

E o resultado você pode ver abaixo e o projeto no Github. Clique no labirinto para gerar outro.

Obs.: Com este algoritmo, você pode ir de um ponto qualquer a outro ponto do labirinto, ou seja, não existem salas fechadas.

Referencias:

Perfect Maze Puzzle in AS3 Flash, Random Maze Generator
Perfect Maze Generation – Tile Based Version AS3

  • Muito bom o Post Feldhaus 😉 Parabéns

  • Carlos Cadori

    Caramba, muito bom, simples e funcional!
    Estava quebrando a cabeça aqui tentando implementar com o A*