Como percorrer um labirinto programaticamente quando atingiu um beco sem saída

Question

Movendo-se através do labirinto para a frente é muito fácil, mas eu não consigo descobrir como fazer o backup através do labirinto para tentar uma nova rota, uma vez que você atingiu um beco sem saída, sem ir muito para trás?

Answer 1

Utilização retrocesso mantendo uma pilha de direção anterior decisões.

Answer 2

A forma mais simples (a implementar) algoritmo seria apenas para manter uma pilha de locais que você foi, e o caminho que você tomou de cada um, a menos que o retrocesso não dá essa informação.

Para voltar, basta retirar antigos locais da pilha e seleção para mais sai desse local até encontrar um local antigo, com uma testada de saída.

Constantemente, a testar as saídas, na mesma ordem a cada vez, se você sabe que retrocesso para um local vem de baixo (ie.a última vez que você esteve no local antigo que você descer), em seguida, basta escolher o próximo direção após para baixo.

Eu não sou inteiramente certo o que você quer dizer com vai muito para trás porém, eu diria que você iria querer voltar para o antigo lugar que você não testado rotas, não é isso o que você quer?

Observe que, a menos que você tente acompanhar o caminho do ponto de partida para a sua localização actual, e evitando os quadrados quando você tenta encontrar novas rotas, você pode acabar indo em círculo, que viria a tornar a pilha muito grande.

Um simples método recursivo que marca o caminho que leva e nunca entra em áreas que são marcadas pode fazer isso facilmente.

Além disso, se o seu coisa que se move através do labirinto é um pouco mais inteligente do que apenas ser capaz de mover-se, e bateu (parar em paredes, em que pode ver a partir do seu ponto atual em todas as direções, eu tenho outros algoritmos que podem ajudar.

Answer 3

Eric Lippert fizemos uma série de artigos sobre a criação de um C# implementação de Um*, o que pode ser mais eficiente.