Parte 1. Algoritmo de búsqueda general
Introduccion
Encontrar un camino es uno de esos temas que generalmente son los más difíciles para los desarrolladores de juegos. Especialmente la gente pobre comprende el algoritmo
A * , y muchos piensan que se trata de algún tipo de magia incomprensible.
El propósito de este artículo es explicar la búsqueda de la ruta en general y
A * en particular de una manera muy comprensible y accesible, poniendo fin a la idea errónea generalizada de que este tema es complejo. Con la explicación correcta, todo es bastante simple.
Tenga en cuenta que en el artículo consideraremos la búsqueda de una forma
de juegos ; A diferencia de otros artículos académicos, omitiremos algoritmos de búsqueda como Profundidad-Primero o Anchura-Primero. En su lugar, intentaremos pasar de cero a
A * lo más rápido posible.
En la primera parte explicaremos los conceptos más simples para encontrar un camino. Al comprender estos conceptos básicos, se dará cuenta de que
A * es sorprendentemente obvio.
Circuito simple
Aunque puede aplicar estos conceptos a entornos 3D complejos arbitrarios, comencemos con un esquema extremadamente simple: una cuadrícula cuadrada de 5 x 5. Para mayor comodidad, marqué cada celda con una letra mayúscula.
Malla simpleLo primero que haremos es imaginar este entorno como un gráfico. No explicaré en detalle qué es un gráfico; En pocas palabras, este es un conjunto de círculos conectados por flechas. Los círculos se llaman
"nudos", y las flechas se
llaman "bordes" .
Cada nodo representa un
"estado" en el que puede estar el personaje. En nuestro caso, el estado del personaje es su posición, por lo que creamos un nodo para cada celda de la cuadrícula:
Nodos que representan celdas de cuadrícula.Ahora agregue las costillas. Indican los estados que se pueden
"alcanzar" desde cada estado dado; En nuestro caso, podemos pasar de cualquier celda a la siguiente, con la excepción de las bloqueadas:
Los arcos denotan movimientos permitidos entre celdas de la cuadrícula.Si podemos pasar de
A a
B , entonces decimos que
B es un
"vecino" para el nodo
A.Vale la pena señalar que las costillas tienen una
dirección ; necesitamos aristas de
A a
B , y de
B a
A. Esto puede parecer superfluo, pero no cuando surgen "condiciones" más complejas. Por ejemplo, un personaje puede caer del techo al piso, pero no puede saltar del piso al techo. Puede pasar del estado de "vivo" al estado de "muerto", pero no al revés. Y así sucesivamente.
Ejemplo
Supongamos que queremos pasar de
A a
T. Comenzamos con
A. Puede hacer exactamente dos acciones: ir a
B o ir a
F.Digamos que nos mudamos a
B. Ahora podemos hacer dos cosas: volver a
A o ir a
C. Recordamos que ya estábamos en
A y consideramos las opciones allí, por lo que no tiene sentido volver a hacerlo (de lo contrario, podemos pasar todo el día moviendo
A →
B →
A →
B ...). Por lo tanto iremos a
C.Al estar en
C , no tenemos a dónde movernos. Volver a
B no tiene sentido, es decir, es un callejón sin salida. Elegir la transición a
B cuando estábamos en
A fue una mala idea; tal vez deberías probar
F en su lugar?
Seguimos repitiendo este proceso hasta que terminamos en
T. En este momento, simplemente recreamos el camino desde
A , volviendo en nuestros pasos. Estamos en
T ; ¿Cómo llegamos allí? De
o ? Es decir, el final del camino tiene la forma
O →
T. ¿Cómo llegamos a
O ? Y así sucesivamente.
Tenga en cuenta que no nos estamos
moviendo realmente; todo esto fue solo un proceso de pensamiento. Continuamos parados en
A , y no nos moveremos fuera de él hasta que encontremos todo el camino. Cuando digo "movido a
B ", quiero decir "imagina que nos mudamos a
B ".
Algoritmo general
Esta sección es la parte más importante de todo el artículo . Absolutamente
debe comprenderlo para poder realizar la búsqueda del camino; el resto (incluido
A * ) son solo detalles. En esta sección, comprenderá hasta que
comprenda el significado .
Además, esta sección es increíblemente simple.
Intentemos formalizar nuestro ejemplo, convirtiéndolo en un pseudocódigo.
Necesitamos rastrear los nodos que sabemos cómo llegar desde el nodo inicial. Al principio, este es solo el nodo inicial, pero en el proceso de "explorar" la cuadrícula, aprenderemos cómo llegar a otros nodos. Llamemos a esta lista de nodos
reachable :
reachable = [start_node]
También necesitamos rastrear los nodos ya revisados para no volver a considerarlos.
explored :
explored = []
A continuación, describiré el núcleo del algoritmo : en cada paso de la búsqueda, seleccionamos uno de los nodos que sabemos alcanzar y observamos qué nuevos nodos podemos obtener de él. Si determinamos cómo llegar al nodo final (objetivo), ¡entonces el problema está resuelto! De lo contrario, continuamos la búsqueda.
Tan simple, ¿qué incluso decepciona? Y esto es verdad. Pero este es todo el algoritmo. Vamos a escribirlo paso a paso con pseudocódigo.
Continuamos buscando hasta que lleguemos al nodo final (en este caso, encontramos la ruta desde el nodo inicial al final), o hasta que nos quedemos sin nodos en los que puede buscar (en este caso, no hay forma entre los nodos iniciales y finales) .
while reachable is not empty:
Elegimos uno de los nodos a los que sabemos cómo llegar y que aún no se ha investigado:
node = choose_node(reachable)
Si acabamos de aprender cómo llegar al nodo final, ¡entonces la tarea está completa! Solo necesitamos construir la ruta siguiendo los enlaces
previous al nodo de inicio:
if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path
No tiene sentido examinar el nodo más de una vez, así que haremos un seguimiento de esto:
reachable.remove(node) explored.add(node)
Identificamos nodos a los que no podemos llegar desde aquí. Comenzamos con una lista de nodos adyacentes al actual y eliminamos los que ya hemos examinado:
new_reachable = get_adjacent_nodes(node) - explored
Tomamos cada uno de ellos:
for adjacent in new_reachable:
Si ya sabemos cómo llegar al nodo, ignórelo. De lo contrario, agréguelo a la lista
reachable , rastreando cómo entró en él:
if adjacent not in reachable: adjacent.previous = node
Encontrar el nodo final es una forma de salir del bucle. La segunda es cuando lo
reachable se vacía: nos hemos quedado sin nodos que se pueden explorar, y no hemos llegado al nodo final, es decir, no hay forma desde el nodo inicial al final:
return None
Y ... eso es todo. Este es el algoritmo completo, y el código de construcción de ruta se asigna en un método separado:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Aquí está la función que construye la ruta, siguiendo los enlaces
previous al nodo de inicio:
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Eso es todo
Este es el pseudocódigo de
cada algoritmo de búsqueda de ruta, incluido
A * .
Vuelva a leer esta sección hasta que comprenda cómo funciona todo y, lo que es más importante,
por qué funciona todo. Sería ideal dibujar un ejemplo a mano en papel, pero también puede ver una demostración interactiva:
Demo interactiva
Aquí hay una demostración y un ejemplo de la implementación del algoritmo anterior (puede ejecutarlo en la
página del artículo original ).
choose_node solo selecciona un nodo aleatorio. Puede iniciar el algoritmo paso a paso y ver la lista de
explored reachable y
explored , así como a dónde apuntan los enlaces
previous .
Observe que la búsqueda termina tan pronto como se detecta una ruta; Puede suceder que algunos nodos ni siquiera sean considerados.
Conclusión
El algoritmo presentado aquí es un algoritmo general para
cualquier algoritmo de búsqueda de ruta.
Pero, ¿qué distingue cada algoritmo de otro, por qué
A * es
A * ?
Aquí hay un consejo: si ejecuta la búsqueda en la demostración varias veces, verá que el algoritmo no siempre encuentra la misma ruta. Encuentra
un camino, y este camino no es necesariamente el
más corto . Por qué
Parte 2. Estrategias de búsqueda
Si no comprende completamente el algoritmo descrito en la sección anterior, vuelva a él y léalo nuevamente, porque es necesario para comprender más información. Cuando lo descubras,
A * te parecerá completamente natural y lógico.
Ingrediente secreto
Al final de la parte anterior, dejé dos preguntas abiertas: si cada algoritmo de búsqueda usa el mismo código, ¿por qué
A * se comporta como
A * ? ¿Y por qué la demostración a veces encuentra diferentes caminos?
Las respuestas a ambas preguntas están relacionadas entre sí. Aunque el algoritmo está bien definido, dejé un aspecto sin resolver, y resulta que es la clave para explicar el comportamiento de los algoritmos de búsqueda:
node = choose_node(reachable)
Es esta cadena de aspecto inocente que distingue todos los algoritmos de búsqueda entre sí.
choose_node depende del método de implementación de
choose_node .
Entonces, ¿por qué la demostración encuentra diferentes caminos? Porque su método
choose_node selecciona un nodo al azar.
La longitud importa
Antes de sumergirnos en las diferencias en el comportamiento de la función
choose_node , necesitamos corregir un pequeño descuido en el algoritmo descrito anteriormente.
Cuando consideramos los nodos adyacentes a los actuales, ignoramos los que ya saben cómo lograr:
if adjacent not in reachable: adjacent.previous = node
Esto es un error: ¿qué pasa si descubrimos la
mejor manera de llegar a él? En este caso, es necesario cambiar el enlace del nodo
previous para reflejar esta ruta más corta.
Para hacer esto, necesitamos saber la longitud de la ruta desde el nodo inicial hasta cualquier nodo accesible. Llamaremos a esto el costo del camino. Por ahora, suponemos que pasar de un nodo a uno de los nodos vecinos tiene un costo constante de
1 .
Antes de comenzar la búsqueda, asignamos el valor de
cost de cada nodo al
infinity ; Gracias a esto,
cualquier camino será más corto que este. También estableceremos el
cost nodo
start_node en
0 .
Entonces así es como se verá el código:
if adjacent not in reachable: reachable.add(adjacent)
Mismo costo de búsqueda
Veamos ahora el método
choose_node . Si nos esforzamos por encontrar la ruta más corta posible, elegir un nodo al azar no es una buena idea.
Es mejor elegir un nodo que podamos alcanzar desde el nodo inicial a lo largo del camino más corto; Gracias a esto, generalmente preferimos caminos más cortos a los más largos. Esto no significa que las rutas más largas no se considerarán en absoluto, sí significa que las rutas más cortas se considerarán primero. Dado que el algoritmo termina inmediatamente después de encontrar una ruta adecuada, esto debería permitirnos encontrar rutas cortas.
Aquí hay un posible ejemplo de la función
choose_node :
function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node
Intuitivamente, la búsqueda de este algoritmo se expande "radialmente" desde el nodo inicial hasta que llega al nodo final. Aquí hay
una demostración interactiva de este comportamiento:
Conclusión
Un simple cambio en el método de elección del nodo considerado por el siguiente nos permitió obtener un algoritmo bastante bueno: encuentra la ruta más corta desde el nodo inicial hasta el final.
Pero este algoritmo, hasta cierto punto, sigue siendo "estúpido". Continúa buscando en todas partes hasta que se topa con un nodo terminal. Por ejemplo, ¿cuál es el punto en el ejemplo que se muestra arriba para buscar en la dirección
A , si es obvio que nos estamos alejando del nodo final?
¿Es posible hacer
choose_node más inteligente? ¿Podemos hacer que
dirija la búsqueda hacia el nodo final , sin siquiera saber de antemano la ruta correcta?
Resulta que podemos: en la siguiente parte, finalmente llegamos a
choose_node , lo que nos permite convertir el algoritmo de búsqueda de ruta general en
A * .
Parte 3. Retire el velo de secreto de A *
El algoritmo obtenido en la parte anterior es bastante bueno: encuentra la ruta más corta desde el nodo inicial hasta el final. Sin embargo, desperdicia su energía: considera las formas que una persona obviamente llama erróneas: generalmente
se alejan de la meta. ¿Cómo se puede evitar esto?
Algoritmo mágico
Imagine que ejecutamos un algoritmo de búsqueda en una computadora especial con un chip que puede hacer
magia . Gracias a este increíble chip, podemos expresar
choose_node muy simple, que garantiza la creación del camino más corto sin perder tiempo explorando caminos parciales que no llevan a ninguna parte:
function choose_node (reachable): return magic(reachable, " , ")
Suena tentador, pero las fichas mágicas aún necesitan algún tipo de código de bajo nivel. Aquí hay una buena aproximación:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, " ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Esta es una excelente manera de seleccionar el siguiente nodo: selecciona un nodo que nos da la ruta más corta desde el nodo inicial hasta el final, que es lo que necesitamos.
También minimizamos la cantidad de magia utilizada: sabemos exactamente cuál es el costo de moverse desde el nodo inicial a cada nodo (esto es
node.cost ), y usamos magia solo para predecir el costo de mover del nodo al nodo final.
No es mágico, pero es bastante impresionante A *
Desafortunadamente, las fichas mágicas son nuevas y necesitamos soporte de equipos obsoletos. La mayor parte del código nos conviene, con la excepción de esta línea:
Es decir, no podemos usar magia para averiguar el costo de un camino inexplorado. Pues bien, hagamos una predicción. Seremos optimistas y supondremos que no hay nada entre los nodos actuales y finales, y simplemente podemos movernos directamente:
cost_node_to_goal = distance(node, goal_node)
Tenga en cuenta que la
ruta más corta y la
distancia mínima son diferentes: la distancia mínima implica que no hay absolutamente ningún obstáculo entre los nodos actuales y finales.
Esta estimación es bastante simple de obtener. En nuestros ejemplos de cuadrícula, esta es la
distancia de bloques de ciudades entre dos nodos (es decir,
abs(Ax - Bx) + abs(Ay - By) ). Si pudiéramos movernos en diagonal, entonces el valor sería igual a
sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) , y así sucesivamente. Lo más importante, nunca obtenemos una estimación de valor
demasiado alta.
Así que aquí hay una versión no
choose_node de
choose_node :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Una función que estima la distancia desde el nodo actual hasta el final se llama
heurística , y este algoritmo de búsqueda, damas y caballeros, se llama ...
A * .
Demo interactiva
Mientras se recupera de la conmoción causada por la comprensión de que el misterioso
A * es realmente
tan simple , puede ver la demostración (o ejecutarla en el
artículo original ). Notará que, a diferencia del ejemplo anterior, la búsqueda pasa muy poco tiempo moviéndose en la dirección incorrecta.
Conclusión
Finalmente, llegamos al algoritmo
A * , que no es más que el algoritmo de búsqueda general descrito en la primera parte del artículo con algunas mejoras descritas en la segunda parte y usando la función
choose_node , que selecciona el nodo que, en nuestra estimación, nos acerca más a nodo final Eso es todo
Aquí hay un pseudocódigo completo del método principal para su referencia:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Método
build_path :
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Y aquí está el método
choose_node , que lo convierte en
A * :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Eso es todo
Pero, ¿por qué necesitamos la
parte 4 ?
Ahora que comprende cómo funciona
A * , quiero hablar sobre algunas áreas sorprendentes de su aplicación, que están lejos de limitarse a encontrar rutas en una cuadrícula de celdas.
Parte 4. A * en la práctica
Las primeras tres partes del artículo comienzan con los fundamentos mismos de los algoritmos de búsqueda de ruta y terminan con una descripción clara del algoritmo
A * . Todo esto es genial en teoría, pero entender cómo esto es aplicable en la práctica es un tema completamente diferente.
Por ejemplo, ¿qué sucede si nuestro mundo no es una red?
¿Qué pasa si un personaje no puede rotar instantáneamente 90 grados?
¿Cómo construir un gráfico si el mundo es infinito?
¿Qué pasa si no nos importa la longitud del camino, pero dependemos de la energía solar y necesitamos estar lo más bajo posible de la luz solar?
¿Cómo encontrar la ruta más corta a cualquiera de los dos nodos finales?
Función de costo
En los primeros ejemplos, buscamos la ruta más corta entre los nodos de inicio y fin. Sin embargo, en lugar de almacenar longitudes de ruta parciales en la
length variable, lo llamamos
cost . Por qué
Podemos hacer que
A * busque no solo el
más corto , sino también el
mejor camino, y la definición de "mejor" se puede elegir en función de nuestros objetivos. Cuando necesitamos el camino más corto, el costo es la longitud del camino, pero si queremos minimizar, por ejemplo, el consumo de combustible, entonces debemos usarlo como costo. Si queremos maximizar el "tiempo que pasa bajo el sol", entonces el costo es el tiempo que pasa sin el sol. Y así sucesivamente.
En el caso general, esto significa que los costos correspondientes están asociados con cada borde del gráfico. En los ejemplos mostrados anteriormente, el valor se estableció implícitamente y siempre se consideró igual a
1 , porque contamos los pasos en el camino. Pero podemos cambiar el costo de la costilla de acuerdo con lo que queremos minimizar.
Función de criterio
Digamos que nuestro objeto es un automóvil, y él necesita llegar a la estación de servicio. Cualquier reabastecimiento de combustible nos vendrá bien. Toma la ruta más corta hasta la estación de servicio más cercana.
El enfoque ingenuo será calcular el camino más corto para cada reabastecimiento de combustible y seleccionar el más corto. Esto funcionará, pero será un proceso bastante costoso.
¿Qué pasaría si pudiéramos reemplazar un
goal_node con un método que, en un nodo dado, puede decir si es finito o no? Gracias a esto, podemos buscar varios objetivos al mismo tiempo. También necesitamos modificar la heurística para que devuelva el costo mínimo estimado de todos los nodos finales posibles.
Dependiendo de los detalles de la situación, es posible que no podamos lograr el objetivo a la
perfección , o costará demasiado (si enviamos al personaje a través de medio mapa enorme, ¿es importante la diferencia de una pulgada?), Por lo tanto, el método
is_goal_node puede volver
true cuando Estamos "lo suficientemente cerca".
No se requiere certeza total.
Representar al mundo como una grilla discreta puede no ser suficiente para muchos juegos. Tomemos, por ejemplo, un juego de disparos o de carreras en primera persona. El mundo es discreto, pero no se puede representar como una cuadrícula.
Pero hay un problema más serio: ¿qué pasa si el mundo es interminable? En este caso, incluso si podemos presentarlo en forma de cuadrícula, simplemente no podremos construir un gráfico correspondiente a la cuadrícula, porque debe ser infinito.
Sin embargo, no todo está perdido. Por supuesto, para el algoritmo de búsqueda de gráficos, definitivamente necesitamos un gráfico. ¡Pero nadie dijo que el gráfico debería ser
completo !
Si observa detenidamente el algoritmo, notará que no estamos haciendo nada con el gráfico en su conjunto; Examinamos el gráfico localmente, obteniendo nodos a los que podemos llegar desde el nodo en cuestión. Como se puede ver en la demostración
A * , algunos nodos del gráfico no se investigan en absoluto.
Entonces, ¿por qué no construimos el gráfico en el proceso de investigación?
Hacemos que la posición actual del personaje sea el nodo inicial. Al llamar a
get_adjacent_nodes puede determinar las posibles formas en que el personaje puede moverse desde un nodo dado y crear nodos vecinos sobre la marcha.
Más allá de las tres dimensiones
Incluso si su mundo es
realmente una malla 2D, hay otros aspectos a considerar. Por ejemplo, ¿qué pasa si un personaje no puede rotar instantáneamente 90 o 180 grados, como suele ser el caso?
El estado representado por cada nodo de búsqueda no tiene que ser solo una
posición ; por el contrario, puede incluir un conjunto de valores arbitrariamente complejo. Por ejemplo, si los giros de 90 grados toman tanto tiempo como la transición de una celda a otra, entonces el estado del personaje se puede establecer como
[position, heading] . Cada nodo puede representar no solo la posición del personaje, sino también la dirección de su mirada; y los nuevos bordes del gráfico (explícito o indirecto) reflejan esto.
Si vuelve a la cuadrícula original de 5x5, la posición de búsqueda inicial ahora puede ser
[A, East] . Los nodos vecinos ahora son
[B, East] y
[A, South] : si queremos llegar a
F , primero debemos ajustar la dirección para que la ruta tome la forma
[A, East] ,
[A, South] ,
[F, South] .
Tirador en primera persona? Al menos cuatro dimensiones:
[X, Y, Z, Heading] . Quizás incluso
[X, Y, Z, Heading, Health, Ammo] .
Tenga en cuenta que cuanto más complejo es el estado, más compleja debe ser la función heurística.
A * en sí mismo es simple; El arte a menudo surge de una buena heurística.
Conclusión
El propósito de este artículo es disipar el mito de una vez por todas que
A * es un algoritmo místico que no se puede descifrar. Por el contrario, demostré que no hay nada misterioso en él y, de hecho, puede deducirse simplemente comenzando desde cero.
Lectura adicional
Amit Patel tiene una excelente
"Introducción al algoritmo A *" [
traducción en Habré] (¡y sus otros artículos sobre diversos temas también son excelentes!).