Ajustar AStar para encontrar la ubicación más cercana al destino inalcanzable

11

Implementé AStar en Java y funciona bien para un área con obstáculos donde se puede llegar al destino elegido.

Sin embargo, cuando el destino es inalcanzable, la "ruta" calculada no está de ninguna manera a la ubicación más cercana (a la ubicación inalcanzable) sino que es una ruta aleatoria.

¿Hay alguna manera factible de ajustar AStar para que encuentre el camino a la ubicación más cercana a un destino inalcanzable?

path-finding Shivan Dragon
fuente

Respuestas:

20

Realice un seguimiento del nodo con el más bajo EstimatedDistanceToEnd(es decir, el más bajo h(x)), y si no se puede acceder a ningún nodo final para retroceder, retroceda desde ese nodo.

BlueRaja - Danny Pflughoeft
fuente
Simple. ¡Me encanta!
John McDonald
Solo me di una palmada en la cabeza y dije "doh" cuando leí tu respuesta. ¡Gracias!
Shivan Dragon
1

Esto no es realmente una pregunta A *. A * se trata de encontrar una ruta desde el punto A al punto B. A pesar de que se puede extender, los resultados podrían ser fácilmente desordenados e impredecibles. En cambio, lo que necesita es un algoritmo que elija el destino accesible más cercano.

Aquí hay una manera de hacer esto: si A * devuelve una ruta válida (los nodos de inicio / fin en la ruta coinciden con los nodos de entrada), devuelva la ruta. De otra manera...

  • Comience a buscar desde el nodo inicial
  • Atraviese todos los nodos vinculados (recuerde marcar los visitados para evitar una recursión infinita)
  • Compare distancias al destino para encontrar el nodo más cercano
serpiente5
fuente
Algo como Relleno de inundación parece apropiado en.wikipedia.org/wiki/Flood_fill tenga en cuenta que aún necesita A * desde el nodo de inicio al nodo con la distancia más baja. También tenga en cuenta que esto siempre implica inspeccionar todos los nodos conectados y, por lo tanto, puede ser extremadamente lento.
Roy T.
Sí, podría ser lento. Pero la lentitud probablemente vendría de tener los nodos dispersos por toda la memoria; eso se puede arreglar fácilmente. Además, es posible acelerarlo sacrificando algo de precisión: simplemente omita los enlaces que estén demasiado lejos o apunten en la dirección incorrecta.
serpiente5
1
@Roy: A *, BFS y todos los algoritmos de búsqueda de ruta similares serán exactamente tan lentos como el relleno de inundación, porque todos deben inspeccionar cada nodo conectado para asegurarse de que no haya una ruta hacia el final. Sin embargo, hay formas de aliviar este problema; ver aquí .
BlueRaja - Danny Pflughoeft