Localização de caminhos com vários caminhos aleatórios em um jogo de Tower Defense

Pensei em encontrar caminhos aleatórios para o meu jogo de Tower Defense. A * não funcionaria para meus propósitos, porque eu especificamente preciso de uma busca aleatória de caminhos.

Imagine um mapa com rotas, um ponto de partida e um destino. Eu tenho várias rotas, que levam do ponto de partida ao destino, de uma maneira ou de outra. Pode ficar assim:

Descrição da cor: vermelho - ponto de partida; preto - destino; cinza - rota; espaço em branco livre
(os números são usados ​​no texto como referência a alguns blocos)

Primeiro pensei em apenas calcular o próximo waypoint aleatoriamente, quando uma entidade passa um ladrilho. Mas isso não funcionaria. Quando uma entidade passa o bloco 1, ela pode subir ou descer. Quando se trata de 2, pode descer / subir (em relação à posição) ou para a direita.
Se ele vai para cima / baixo ele iria para a telha 1, o que significa que ele vai para trás. Ruim...

Eu realmente gostaria de torná-lo dinâmico , mas não consigo descobrir o que posso fazer agora. Alguém com idéias ou experiência nisso?

Em vez de ter todos os quadrados adjacentes possíveis nos próximos waypoints, inclua apenas quadrados que não retornem ao início e escolha aleatoriamente aqueles. Se você fez isso, seria impossível voltar atrás, porque voltar não é uma opção.

Este é um problema de gráfico direcionado com cada waypoint como um vértice e cada caminho como uma aresta. Você só precisa limitar o número de ciclos, talvez removendo-os completamente.

Você diz aleatoriamente, mas quanta aleatoriedade você quer? Tudo bem se os inimigos escolherem um caminho 10 vezes maior que o menor? Tudo bem se os inimigos entrarem em um beco sem saída e tiverem que voltar atrás? Ou seja, aleatório sobre o conjunto de caminhos e com qual distribuição de probabilidade?

Supondo que você queira que os inimigos prefiram caminhos curtos, você pode usar A *, mas varia aleatoriamente os pesos das arestas alimentadas a ele. Então, os inimigos sempre escolhem um caminho aleatório que visita cada nó no máximo uma vez, com um viés em direção a caminhos mais curtos. Em particular, se sem randomização houvesse vários caminhos do mesmo comprimento, cada um desses caminhos seria escolhido com igual probabilidade.

Como alternativa, em A *, você pode iterar os vizinhos em ordem aleatória. Em seu exemplo, quando a localização do caminho atinge o nó 1, ele enfileira aleatoriamente primeiro o vizinho superior, causando o primeiro ou o menor caminho considerado. Essa solução faria com que os inimigos escolhessem aleatoriamente todos os caminhos mais curtos. No seu exemplo simples, os dois caminhos mais curtos seriam igualmente prováveis, mas em uma situação como:

start -+--------+
       |        |
       +--------+
       |        |
       +--------+- end

o caminho superior seria escolhido com probabilidade 1/2, enquanto o caminho inferior seria escolhido com probabilidade 1/4 cada.

Apenas uma prova de conceito:

1. Escolha uma direção aleatória.
2. Se isso nos levar a algum lugar que já estivemos, escolha outra direção.
3. Se ficarmos sem instruções, volte para o último quadrado com uma direção inexplorada.