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.
algorithm
path-finding
Daniel X Moore
fuente
fuente
Respuestas:
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
A
y queremos encontrar el camino más corto haciaF
. 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.Este es nuestro punto de partida. Tenemos una lista de nodos para examinar, esta lista actualmente es:
A
tiene un costo de0
, todos los demás nodos se establecen en infinito (en una implementación típica, esto sería algo similarint.MAX_VALUE
o similar).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:y realice un seguimiento del nodo anterior (se muestra como una pequeña letra rosa debajo del nodo).
A
ahora se puede marcar como resuelto (rojo), para que no lo volvamos a visitar. Nuestra lista de candidatos ahora se ve así:Nuevamente, tomamos el nodo con el costo más bajo de nuestra lista (
B
) y evaluamos a sus vecinos. El camino haciaD
es más costoso que el costo actual deD
, por lo tanto, este camino puede descartarse.E
se agregará a nuestra lista de candidatos, que ahora se ve así:El siguiente nodo para examinar es ahora
D
. La conexión aC
se puede descartar, ya que la ruta no es más corta que el costo existente. Sin embargo, encontramos una ruta más cortaE
, porE
lo que se actualizará el costo y su nodo anterior. Nuestra lista ahora se ve así:Entonces, como lo hicimos antes, examinamos el nodo con el costo más bajo de nuestra lista, que es ahora
E
.E
solo tiene un vecino sin resolver, que también es el nodo de destino. El costo para alcanzar el nodo objetivo se establece en10
y su nodo anterior enE
. Nuestra lista de candidatos ahora se ve así:A continuación lo examinamos
C
. Podemos actualizar el costo y el nodo anterior paraF
. Como nuestra lista ahora tiene unF
nodo 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:
Con A * es:
Donde
Estimated_Cost_to_reach_Target_from
comú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.
fuente
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.
fuente
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.
fuente
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.
fuente
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.
fuente
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.
fuente
En un nivel abstracto, A * funciona así:
fuente