Encontrar caminos con múltiples caminos aleatorios en un juego de Tower Defense

Pensé en encontrar caminos aleatorios para mi juego Tower Defense. A * no funcionaría para mis pupos, porque específicamente necesito encontrar rutas aleatorias .

Imagine un mapa con rutas, un punto de partida y un destino. Tengo múltiples rutas, que conducen desde el punto de partida hasta el destino, de una forma u otra. Podría verse así:

Descripción del color: rojo - punto de partida; negro - destino; gris - ruta; blanco - espacio libre
(los números se usan en el texto como referencia para algunos mosaicos)

Primero pensé en calcular el siguiente waypoint al azar, cuando una entidad pasa un mosaico. Pero eso no funcionaría. Cuando una entidad pasa el mosaico 1, puede subir o bajar. Cuando se trata de 2, puede ir hacia abajo / arriba (en relación con su posición) o hacia la derecha.
Si se va hacia abajo / arriba iría a baldosa 1, lo que significa que va hacia atrás. Malo...

Realmente me gustaría hacerlo dinámico , pero no puedo entender qué puedo hacer ahora. ¿Alguien con ideas o experiencia en esto?

En lugar de tener todos los cuadrados adyacentes como posibles puntos de referencia próximos, solo incluya cuadrados que no conduzcan al principio y elija al azar de ellos. Si hiciera esto, sería imposible retroceder porque retroceder no es una opción.

Este es un problema de gráfico dirigido con cada punto de referencia como vértice y cada ruta como borde. Solo necesita limitar el número de ciclos, quizás eliminándolos por completo.

Dices al azar, pero ¿cuánta aleatoriedad quieres? ¿Está bien si los enemigos eligen un camino que es 10 veces más largo que el más corto? ¿Está bien si los enemigos entran en un callejón sin salida y tienen que retroceder? Es decir, al azar sobre qué conjunto de caminos, y con qué distribución de probabilidad?

Suponiendo que desea que los enemigos prefieran caminos cortos, puede usar A *, pero al azar puede variar los pesos de borde que se le suministran. Luego, los enemigos siempre elegirán una ruta aleatoria que visite cada nodo como máximo una vez, con un sesgo hacia rutas más cortas. En particular, si sin aleatorización hubiera varios caminos de la misma longitud, cada uno de estos caminos se elegiría con la misma probabilidad.

Alternativamente, en A *, puede iterar sobre los vecinos en orden aleatorio. En su ejemplo, cuando la búsqueda de ruta alcanza el nodo 1, al azar colocaría primero la parte superior del vecino inferior, haciendo que la ruta superior o inferior se considere primero. Esta solución haría que los enemigos elijan entre todos los caminos más cortos al azar. En su ejemplo simple, ambas rutas más cortas serían igualmente probables, pero en una situación como:

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

la ruta superior se elegiría con probabilidad 1/2, mientras que las inferiores se elegirían con probabilidad 1/4 cada una.

Solo una prueba de concepto:

1. Elige una dirección aleatoria.
2. Si esto nos hace ir a algún lugar donde ya hemos estado, elija otra dirección.
3. Si nos hemos quedado sin direcciones, regrese al último cuadrado con una dirección inexplorada.