Oi pessoal,
Estou desenvolvendo um gerador aleatório para a criação de um labirinto para um trabalho, todavia estou com algumas dificuldades. Nas indicações do trabalho o labirinto precisa ter um tamanho aleatório e somente um caminho possível (uma solução só). Para isso começamos com todos os “muros” fechados de todas as células, então escolhemos uma célula aleatória e vamos visitando as vizinhas e marcando como visitadas e derrubando os muros para traçar o caminho. O problema que não consegui resolver é a condição de que só pode haver uma solução possível. Para isso sei que não podemos revisitar as células já visitadas, a menos que nos encontremos num impasse. Entretanto não sei como resolver isso essa parte. Agradeço se alguém conseguir me ajudar nesse problema!
Crie um tabuleiro com X linhas e colunas.
Inicialmente cada célula do tabuleiro terá quatro paredes fechadas.
Escolha uma célula aleatória para iniciar a criação do labirinto.
Implemente um algoritmo de busca em profundidade para visitar as células vizinhas.
Ao pular de uma célula pra outra, remova a parede que existia entre elas.
Repita os passos até ter visitado todas as células do tabuleiro.
Graças à característica do algoritmo em busca por profundidade, ao final você terá um labirinto com uma única solução possível.
1 curtida