¿Sería aceptable para colocar límites alrededor de mi área de búsqueda de caminos?

Question

Actualmente estoy usando el algoritmo A * búsqueda de caminos para calcular una ruta en una red infinita (utilizando un UnboundedGrid en GridWorld, el estudio de caso AP CS, si eso ayuda a nadie). Todo funciona de maravilla, a excepción de los casos en que no exista una ruta válida porque el nodo final está completamente rodeada por paredes. Como era de esperar, el algoritmo continúa buscando infinitamente, sin encontrar nunca el nodo final.

Una posible solución a este sería colocar invisible (como en, el usuario no los ve, pero el algoritmo hace) paredes alrededor de toda el área de búsqueda de caminos, por lo que el nodo de inicio, nodo final, y todos los nodos de la pared se encuentran dentro de estas paredes, con 2-3 espacios relleno o así. Algo así como:

_________________________________
|                               |
|              S  |             |
|            _____|   _____     |
|                     | E |     |
|                     |___|     |
|_______________________________|

... siendo que con el tiempo todos los nodos se añadirán a la closedlist la idea, el openlist se convertirá en vacío, y en ese momento voy a saber que no existe una ruta válida.

¿Le parece esto como una solución razonable al problema? ¿Existe alguna forma en la que esto podría salir mal? Yo entiendo que otra solución es al mismo tiempo PathFind hacia atrás desde el final, pero esto parece que podría ser potencialmente costosa, particularmente en los casos en que el nodo final no está tan fuertemente cerrados.

Answer 1

No se sabe exactamente dónde está el nodo final? Si lo hace, sólo comprobar si está rodeado antes de hacer su algoritmo.

Answer 2

Véase también mi comentario sobre su pregunta. Después de escribir se me ocurrió lo que podría ser una buena solución. Este es un caso en el que no conoce su nodo final y no puede hacer nada con la posición de su nodo final como se sugirió anteriormente.

Se podría también algo en la línea de: "Me han encontrado una caja cerrada en mi campo y hay un camino después de x de tiempo por lo que con y% propability lo que puedo decir no hay camino, y actualizar el y% a aumentar con el tiempo, pero nunca llegar al 100%.

podría ser una buena solución que está en el medio del que delimita el área de búsqueda y no hacer nada.

Answer 3

He tenido un problema similar y esto es lo que hice:

1. Ejecutar algoritmo para n iteraciones, a partir de una búsqueda para B.
2. Ejecutar algoritmo para n iteraciones, a partir de la búsqueda B para A.

Si bien ejecución determina que uno o el otro se encuentra en una zona completamente aislada (sin nodos más abiertas), la búsqueda falla. De lo contrario, la búsqueda se realiza de forma normal.

El truco aquí es, por supuesto, para llegar a un valor bueno para n . Hice varias pasadas con el aumento de n y en caché los resultados (mi gráfico de cambio aún no ha mucho).

Answer 4

Usted está utilizando un * por lo que debe ser capaz de ponderar los nodos de terreno con un costo. Poner un costo increíblemente alta en los nodos de pared. Debe ser mayor que el costo total de cualquier camino posible. Si el coste final de la ruta es mayor que el costo de frontera, entonces tenía que pasar una pared de encontrar un camino, por lo que es válido. El A * rutas algoritmo alrededor de los nodos de alto costo, por lo que no ruta a través de una pared a menos que tenga a.