¿Cómo funciona A * pathfinding?

67

Me gustaría entender en un nivel fundamental la forma en que funciona la búsqueda de rutas A *. Sería útil cualquier implementación de código o código psuedo, así como las visualizaciones.

Daniel X Moore
fuente
Aquí hay un pequeño artículo con un GIF animado que muestra el algoritmo de Dijkstra en movimiento.
Ólafur Waage
Las páginas A * de Amit fueron una buena introducción para mí. Puede encontrar muchas visualizaciones buenas buscando el algoritmo AStar en youtube.
jdeseno
Me han confundido varias explicaciones de A * antes de encontrar este gran tutorial: policyalmanac.org/games/aStarTutorial.htm. Me referí principalmente a eso cuando escribí una implementación de A * en ActionScript: newarteest.com/flash /astar.html
jhocking
44
-1 Wikipedia tiene un artículo sobre * con la explicación, código fuente, visualización y ... . Algunas de las respuestas aquí tienen enlaces externos desde esa página wiki.
user712092
44
Además, debido a que este es un tema bastante complejo de gran interés para los desarrolladores de juegos, creo que queremos la información aquí. Recuerdo que Joel dijo una vez que quiere que StackOverflow sea el mejor éxito cuando la gente hace preguntas de programación en Google.
jhocking

Respuestas:

63

Descargo de responsabilidad

Hay toneladas de ejemplos de código y explicaciones de A * que se pueden encontrar en línea. Esta pregunta también ha recibido muchas respuestas excelentes con muchos enlaces útiles. En mi respuesta, intentaré proporcionar un ejemplo ilustrado del algoritmo, que podría ser más fácil de entender que el código o las descripciones.


Algoritmo de Dijkstra

Para entender A *, sugiero que primero eche un vistazo al algoritmo de Dijkstra . Déjame guiarte a través de los pasos que realizará el algoritmo de Dijkstra para una búsqueda.

Nuestro nodo de inicio es Ay queremos encontrar el camino más corto hacia F. Cada borde del gráfico tiene un costo de movimiento asociado (indicado como dígitos negros al lado de los bordes). Nuestro objetivo es evaluar el costo mínimo de viaje para cada vértice (o nodo) del gráfico hasta que alcancemos nuestro nodo objetivo.

Dijkstra ilustrado, parte 1

Este es nuestro punto de partida. Tenemos una lista de nodos para examinar, esta lista actualmente es:

{ A(0) }

Atiene un costo de 0, todos los demás nodos se establecen en infinito (en una implementación típica, esto sería algo similar int.MAX_VALUEo similar).

Dijkstra ilustrado, parte 2

Tomamos el nodo con el costo más bajo de nuestra lista de nodos (dado que nuestra lista solo contiene A, este es nuestro candidato) y visitamos a todos sus vecinos. Establecemos el costo de cada vecino para:

Cost_of_Edge + Cost_of_previous_Node

y realice un seguimiento del nodo anterior (se muestra como una pequeña letra rosa debajo del nodo). Aahora se puede marcar como resuelto (rojo), para que no lo volvamos a visitar. Nuestra lista de candidatos ahora se ve así:

{ B(2), D(3), C(4) }

Dijkstra ilustrado, parte 3

Nuevamente, tomamos el nodo con el costo más bajo de nuestra lista ( B) y evaluamos a sus vecinos. El camino hacia Des más costoso que el costo actual de D, por lo tanto, este camino puede descartarse. Ese agregará a nuestra lista de candidatos, que ahora se ve así:

{ D(3), C(4), E(4) }

Dijkstra ilustrado, parte 4

El siguiente nodo para examinar es ahora D. La conexión a Cse puede descartar, ya que la ruta no es más corta que el costo existente. Sin embargo, encontramos una ruta más corta E, por Elo que se actualizará el costo y su nodo anterior. Nuestra lista ahora se ve así:

{ E(3), C(4) }

Dijkstra ilustrado, parte 5

Entonces, como lo hicimos antes, examinamos el nodo con el costo más bajo de nuestra lista, que es ahora E. Esolo tiene un vecino sin resolver, que también es el nodo de destino. El costo para alcanzar el nodo objetivo se establece en 10y su nodo anterior en E. Nuestra lista de candidatos ahora se ve así:

{ C(4), F(10) }

Dijkstra ilustrado, parte 6

A continuación lo examinamos C. Podemos actualizar el costo y el nodo anterior para F. Como nuestra lista ahora tiene un Fnodo con el costo más bajo, hemos terminado. Nuestro camino puede construirse retrocediendo los nodos más cortos anteriores.


A * algoritmo

Entonces, ¿se preguntará por qué le expliqué Dijkstra en lugar del algoritmo A * ? Bueno, la única diferencia está en cómo sopesas (u ordenas) a tus candidatos. Con Dijkstra es:

Cost_of_Edge + Cost_of_previous_Node

Con A * es:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Donde Estimated_Cost_to_reach_Target_fromcomúnmente se llama una función heurística . Esta es una función que intentará estimar el costo para alcanzar el nodo objetivo. Una buena función heurística logrará que se tengan que visitar menos nodos para encontrar el objetivo. Si bien el algoritmo de Dijkstra se expandiría a todos los lados, A * buscará (gracias a la heurística) en la dirección del objetivo.

La página de Amit sobre heurística tiene una buena visión general sobre la heurística común.

bummzack
fuente
2
Vale la pena señalar que la heurística no siempre empujará la búsqueda para encontrar la mejor ruta. Por ejemplo, si su heurística es la distancia al objetivo, pero la ruta viable está alrededor del borde del mapa, la búsqueda buscará en este caso todo el mapa antes de obtener la ruta correcta. Seguramente entonces, debes estar pensando, ¿hay algo que no entiendo? ¡Esto no funciona! - lo que hay que entender es que el propósito de una heurística es reducir la búsqueda en la MAYORÍA de los casos, y su trabajo es encontrar una que sea la "mejor" de todas las soluciones disponibles para sus necesidades específicas.
SirYakalot
2
@AsherEinhorn Todavía va a ser mejor (o en el peor de los casos igual) que una búsqueda desinformada como la de Djikstra.
bummzack
si si, tienes toda la razón. Tal vez no estaba claro, esa instancia de la que hablé en el comentario anterior es un senador teórico del "peor de los casos" para A * con esa heurística, PERO es lo que Dijkstra haría CADA vez. La mayoría de las veces A * será mejor incluso con una heurística muy simple. Mi punto era que la heurística puede ser confusa al principio porque la "distancia al objetivo" no siempre tiene sentido para cada escenario; el punto es que lo hace para la mayoría.
SirYakalot
Además, vea esto: qiao.github.io/PathFinding.js/visual
David Chouinard
Esta respuesta podría usar una mención de lo que hace admisible una heurística, en el sentido de garantizar que A * encontrará el camino más corto. (Brevemente: para ser admisible, la heurística nunca debe sobreestimar la distancia real al objetivo. Las heurísticas no admisibles a veces pueden ser útiles, pero pueden hacer que A * regrese caminos subóptimos.)
Ilmari Karonen
26

Una búsqueda de ruta * es una búsqueda de primer tipo que utiliza una heurística adicional.

Lo primero que debe hacer es dividir su área de búsqueda. Para esta explicación, el mapa es una cuadrícula de mosaicos cuadrados, porque la mayoría de los juegos en 2D usan una cuadrícula de mosaicos y porque eso es fácil de visualizar. Sin embargo, tenga en cuenta que el área de búsqueda se puede dividir de la forma que desee: una cuadrícula hexadecimal o incluso formas arbitrarias como Riesgo. Las distintas posiciones del mapa se denominan "nodos" y este algoritmo funcionará cada vez que tenga que atravesar un grupo de nodos y tenga conexiones definidas entre los nodos.

De todos modos, comenzando en un mosaico de inicio dado:

  • Las 8 fichas alrededor de la ficha inicial se "puntúan" en función de a) el costo de pasar de la ficha actual a la siguiente ficha (generalmente 1 para movimientos horizontales o verticales, sqrt (2) para el movimiento diagonal).

  • A cada ficha se le asigna una puntuación "heurística" adicional, una aproximación del valor relativo de moverse a cada ficha. Se utilizan diferentes heurísticas, la más simple es la distancia en línea recta entre los centros del mosaico dado y el mosaico final.

  • El mosaico actual se "cierra" y el agente se mueve al mosaico vecino que está abierto, tiene la puntuación de movimiento más baja y la puntuación heurística más baja.

  • Este proceso se repite hasta que se alcanza el nodo objetivo o no hay más nodos abiertos (lo que significa que el agente está bloqueado).

Para diagramas que ilustran estos pasos, consulte este buen tutorial para principiantes .

Se pueden hacer algunas mejoras, principalmente para mejorar la heurística:

  • Teniendo en cuenta las diferencias de terreno, aspereza, pendiente, etc.

  • A veces también es útil hacer un "barrido" a través de la cuadrícula para bloquear áreas del mapa que no son rutas eficientes: una forma de U frente al agente, por ejemplo. Sin una prueba de barrido, el agente primero entraría en la U, se daría la vuelta, luego se iría y saldría por el borde de la U. Un agente inteligente "real" notaría la trampa en forma de U y simplemente la evitaría. Barrer puede ayudar a simular esto.

Sean James
fuente
1
Una explicación con gráfico, nodos, bordes, sería más clara que solo sobre mosaicos. No ayuda comprender que, sea cual sea la estructura espacial de su juego, puede aplicar el mismo algoritmo siempre que haya información de posiciones interconectadas en este espacio.
Klaim
Yo diría que en realidad sería menos claro, porque es más difícil de visualizar. Pero sí, esta explicación debería mencionar que no se requiere una cuadrícula de mosaico; de hecho,
editaré
14

Está lejos de ser el mejor, pero esta es una implementación que hice de A * en C ++ hace unos años.

Probablemente sea mejor que le señale recursos que intente explicar todo el algoritmo. Además, mientras lee el artículo wiki, juegue con la demostración y vea si puede visualizar cómo está funcionando. Deja un comentario si tienes una pregunta específica.

  1. A * en Wikipedia
  2. A * demostración de Java
David McGraw
fuente
44
Su ejemplo de Python está en C ++.
Bollos de aluminio
@finish - ¡Es bueno ver a alguien captar eso! Las actividades cotidianas giran en torno a Python en estos días. ¡Gracias!
David McGraw
3
Su ejemplo de C ++ también podría ser C.
deceleratedcaviar
44
El ejemplo también podría estar en ensamblador para toda la estructura que tiene. Ni siquiera es A *, ¿cómo es esta la respuesta aceptada?
44
Lo siento, no depende de los muchachos, fue uno de mis primeros intentos de codificación cuando comencé. Siéntase libre de contribuir con algo a los comentarios / editar la publicación para compartir su propia solución.
David McGraw
6

Puede encontrar útil el artículo de ActiveTut sobre Path Finding . Repasa tanto el algoritmo de A * como el de Dijkstra y las diferencias entre ellos. Está dirigido a los desarrolladores de Flash, pero debería proporcionar una buena idea de la teoría, incluso si no usa Flash.

VirtuosiMedia
fuente
4

Una cosa que es importante visualizar cuando se trata con A * y el Algoritmo de Dijkstra es que A * está dirigido; trata de encontrar el camino más corto hacia un punto en particular "adivinando" en qué dirección mirar. El algoritmo de Dijkstra encuentra el camino más corto hacia / cada / punto.

Karantza
fuente
1
Esta no es realmente una descripción precisa de la diferencia entre A * y Dijkstra. Es cierto que Dijkstra resuelve una sola fuente en todos los puntos, pero cuando se usa en juegos generalmente se interrumpe tan pronto como encuentras un camino hacia la meta. La verdadera diferencia entre los dos es que A * está informado por heurística y puede encontrar ese objetivo con menos ramas.
Para agregar a la explicación de Joe: A * también encontrará el camino a todos los puntos, si lo permite, pero en los juegos generalmente queremos parar antes. A * funciona como el algoritmo de Dijsktra, excepto que la heurística ayuda a reordenar los nodos para explorar primero los caminos más prometedores. De esa manera, generalmente puede detenerse incluso antes que con el algoritmo de Dijkstra. Por ejemplo, si desea encontrar una ruta desde el centro del mapa hacia el lado este, el algoritmo de Dijkstra explorará por igual en todas las direcciones y se detendrá cuando encuentre el lado este. A * pasará más tiempo yendo al este que al oeste, y llegará antes.
amitp
3

Entonces, como primera afirmación, A * es en el fondo un algoritmo de exploración gráfica. Por lo general, en los juegos usamos fichas u otra geometría mundial como gráfico, pero puedes usar A * para otras cosas. Los dos algoritmos ur para el recorrido del gráfico son profundidad-primera-búsqueda y amplitud-primera-búsqueda. En DFS, siempre explora por completo su rama actual antes de mirar a los hermanos del nodo actual, y en BFS siempre mira primero a los hermanos y luego a los hijos. A * intenta encontrar un punto medio entre estos donde exploras una rama (más como DFS) cuando te estás acercando al objetivo deseado, pero a veces te detienes e intentas un hermano si podría tener mejores resultados en su rama. La matemática real es que mantiene una lista de posibles nodos para explorar a continuación donde cada uno tiene una "bondad" puntuación que indica qué tan cerca (en algún sentido abstracto) está de la meta, siendo mejores las puntuaciones más bajas (0 significaría que encontró la meta). Para seleccionar cuál usar a continuación, encuentre el mínimo de la puntuación más el número de nodos lejos de la raíz (que generalmente es la configuración actual o la posición actual en la búsqueda de rutas). Cada vez que explora un nodo, agrega todos sus elementos secundarios a esta lista y luego elige el nuevo mejor.

coderanger
fuente
3

En un nivel abstracto, A * funciona así:

  • Tratas al mundo como un número discreto de nodos conectados, por ejemplo. una cuadrícula o un gráfico.
  • Para encontrar un camino a través de ese mundo, necesita encontrar una lista de 'nodos' adyacentes dentro de ese espacio, que conducen desde el principio hasta el objetivo.
  • El enfoque ingenuo sería este: calcule cada permutación posible de nodos que comienzan con el nodo de inicio y terminan en el nodo final, y elija el más barato. Obviamente, esto tomaría una eternidad en todos los espacios menos en los más pequeños.
  • Por lo tanto, los enfoques alternativos intentan usar algún conocimiento sobre el mundo para adivinar qué permutaciones vale la pena considerar primero y para saber si una solución dada puede ser superada. Esta estimación se llama heurística.
  • A * requiere una heurística que sea admisible . Esto significa que nunca se sobreestima.
    • Una buena heurística para los problemas de búsqueda de caminos es la distancia euclidiana porque sabemos que la ruta más corta entre 2 puntos es una línea recta. Esto nunca sobreestima la distancia en simulaciones del mundo real.
  • A * comienza con el nodo de inicio, e intenta permutaciones sucesivas de ese nodo más cada vecino y los vecinos de su vecino, etc., utilizando la heurística para decidir qué permutación probar a continuación.
  • En cada paso, A * mira el camino más prometedor hasta el momento y elige el siguiente nodo vecino que parece ser el "mejor", en función de la distancia recorrida hasta el momento y la estimación de la heurística de qué tan lejos quedaría de ese nodo.
  • Debido a que la heurística nunca se sobreestima, y ​​se sabe que la distancia recorrida hasta ahora es precisa, siempre elegirá el siguiente paso más optimista.
    • Si el siguiente paso alcanza la meta, sabes que ha encontrado la ruta más corta desde la última posición, porque esta fue la suposición más optimista de las válidas restantes.
    • Si no alcanzó la meta, se deja como un posible punto para explorar desde más adelante. El algoritmo ahora elige la siguiente posibilidad más prometedora, por lo que la lógica anterior aún se aplica.
Kylotan
fuente