Razón Artificial

La ciencia y el arte de crear videojuegos

Usando Pilas Binarias en Pathfinding A*

Escrito por adrigm el 3 de abril de 2010 en Inteligencia Artificial, Noticias, Programación | 3 Comentarios.

Este artículo es un anexo al artículo principal, A* Pathfinding. Camino óptimo” . Deberías leer ese artículo, o comprender el A* a fondo, antes de leer este artículo.

Una de las partes más lentas del algoritmo A*, es encontrar el cuadro o nodo de la lista abierta con la menor puntación F. Dependiendo del tamaño de tu mapa, podrías tener docenas, cientos o incluso miles de nodos donde buscar en cualquier momento mientras usas el A*. No necesito decir, que buscar repetidamente en una lista que sea grande puede enlentecer mucho las cosas. Sin embargo, la cantidad de tiempo que lleva hacer esto puede ser influenciada por la forma en la que elijas salvar los elementos de tu lista abierta.

Listas abiertas Ordenas y Desordenadas: Una Simple Aproximación

Una forma realmente fácil de almacenar la lista abierta es guardar cada elemento cuando se necesite, y recorrer la lista completa cada vez que necesites sacar algo de la lista buscando el elemento de coste menor. Esto proporciona rápidas inserciones en la lista, pero será posiblemente más lento de quitar ya que necesitas comprobar todos los elementos de la lista para asegurarte de que tienes el elemento de coste F más bajo.

Normalmente puedes mejorar la ejecución de tu programa manteniendo lista ordenada. Lleva un poco más de trabajo; porque cada vez que añades un elemento a la lista, necesitas insertarlo en el lugar adecuado. Sin embargo, eliminar elementos es rápido. Solo sacas el primer elemento que es el que tiene el coste más bajo posible.

Hay muchas formas de mantener tus datos ordenados (selection sorts, bubble sorts, quick sorts, etc.) y puedes encontrar artículos en internet acerca del tema, simplemente incluyendo los términos en tu buscador favorito. De todas formas puede que al menos captes unas ideas aquí. Un enfoque realmente simple sería empezar al principio de tu lista cada vez que necesites añadir un nuevo elemento, y luego comparar sucesivamente el coste F del nodo actual que estás añadiendo a la lista con cada elemento que ya esté en ella. Una vez que hayas encontrado un nodo en la lista con un coste F igual o mayor, podrías insertar el nuevo elemento antes de ese que has encontrado. Dependiendo del lenguaje que estés usando, las listadas enlazadas usando clases o las estructuras (tipos en darkbasic y blitz), son probablemente las mejores opciones.

Este enfoque podría mejorarse  manteniendo la pista del coste F medio de los elementos que ya están en la lista, y usando eso para decidir si empezar al principio de la lista (como se describe más abajo) o empezar al final de la lista y seguir hasta el principio de la lista. En general, las inserciones de nuevos elementos con menor coste que la F media, deberían empezar al principio de la lista y avanzar, mientras que elementos nuevos con una F sobre la media deberían ir al final e ir retrocediendo. Este enfoque acorta el tiempo de búsqueda a la mitad.

Más complicado pero más rápido sería llevando esa idea al siguiente nivel, usando una quick sort (clasificación rápida), que básicamente empieza comparando el coste F del nuevo elemento con el elemento de la mitad de la lista. Si el nuevo elemento tiene un coste menor, deberías compararlo con el elemento que esté a 1/4 de la longitud de la lista, si es menor a 1/8, y así sucesivamente hasta que encuentres el lugar adecuado

Pilas Binarias (Binary Heaps )

Los pilas binarios son muy similares al método quick sort que acabamos de describir, y frecuentemente los usan personas que desean mantener sus funciones A*, tan rápidas como sea posible. En mi experiencia, usar un pila binario ha acelerado la búsqueda de 2 a 3 veces de media, y más aún en mapas mayores con muchos nodos (me refiero a un mapa de 100 x 100 nodos o más). No obstante, he de decir que los pilas binarios son un poco complicados y no deberían ser un dolor de cabeza a menos que estés usando un mapa con muchos nodos, donde ganar velocidad es crucial.

El resto de este artículo se dedica a explicar pilas binarios y su uso en A*. Hay también una sección de Más Información al final de esta página la cual te dará perspectivas adicionales, si la mía te ha dejado totalmente desconcertado.

¿Aún estás interesado? De acuerdo, allá vamos…

En una lista ordenada, cada elemento de la lista está en el orden correcto, de menor a mayor o de mayor a menor. Esto es útil, pero ahora es más de lo que necesitamos realmente. En estos momentos no nos importa si el número 127 es menor que el 128 de la lista. Lo verdaderamente importante es que tengamos el elemento con el coste F menor, al principio de la lista. El resto de la lista puede ser un revoltijo sin sentido. Mantener el resto de la lista debidamente ordenado es solo trabajo innecesario hasta que, por supuesto, necesitemos el siguiente elemento con la F más baja.

Básicamente, lo que andamos buscando es algo llamado “pila” o, más específicamente, una pila binaria. Una pila binaria es un conjunto de elementos donde el elemento menor o el mayor (dependiendo de lo que quieras) está al principio de la pila. Cuando estemos buscando el elemento con el coste F más bajo, lo pondremos en lo más alto de nuestra pila. Este elemento tiene dos hijos, cada uno de los cuales tiene un coste F igual  o un poco mayor que él, y cada uno de esos hijos tienen a su vez dos hijos que tienen un coste igual o un poco mayor que ellos… y así hasta el final. Aquí hay algo que podría ser una pila:

Observa que el el elemento menor de la lista (10) está en todo lo alto y el segundo menor (20) es uno de sus hijos. En esta particular pila binaria, el tercer elemento con el coste menor de la lista es el 24, el cual está a dos pasos del principio y es menor que 30, el cual está solo a un paso del 10 y situado a su izquierda. No importa el valor de los otros elementos de la pila, cada elemento individual, solo necesita ser igual o mayor que su padre, e igual o menor que sus dos hijos. Estas condiciones representan una pila binaria válida.

Llegados a este punto, probablemente estés pensando en el modesto interés de todo esto. ¿Cómo vas a usar esos conceptos de una manera práctica? Una de las cosas interesantes sobre pilas es que puedes guardarlas en matriz unidimensional.

En esta matriz, el elemento al principio de la pila estaría en la primera posición de la matriz (posición 1, no posición 0 cosa posible en una matriz). Sus dos hijos deberían estar en las posiciones 2 y 3. Los 4 hijos de esos 2 elementos estarían en las posiciones 4-7.

En resumen, los dos hijos de cualquier elemento de la pila, pueden localizarse en la matriz, multiplicando la posición del elemento actual en la matriz por dos (para encontrar al primer hijo) y por dos mas uno (para encontrar al segundo). Así, por ejemplo, los 2 hijos del tercer elemento de nuestra pila (con un valor de 20), se encuentran en las posiciones 2×3 = 6, y 2×3 +1=7 de la matriz. En este caso, los números de esas posiciones son 30 y 24 respectivamente, cosa que cobra sentido cuando miras la pila.

Con 7 elementos, se llena completamente cada fila de una pila de 3 niveles. Sin embargo, esto no es obligatorio. Para que nuestra pila sea válida, lo único que necesitamos es llenar cada fila que haya sobre el último nivel. Podemos tener cualquier número de elementos en el nivel inferior y los nuevos elementos se irán añadiendo en ese nivel de izquierda a derecha. El método descrito en este artículo hace esto, así que no necesitas preocuparte por esto.

Añadiendo Elementos Al Montón

Necesitaremos considerar algunas cosas antes de que podamos usar una pila en un pathfinding, pero por ahora solo vamos a aprender lo básico de su uso. Te sugeriría que hojeases esta parte para comprender los principios. Más tarde, te daré una fórmula que te librará de todo esto, pero aún es importante que comprendas como funcionan las cosas.

En general, para añadir elementos a la pila, los colocamos al final de la matriz. Después los comparamos a sus padres, quienes están en la posición (elementos en la pila)/2 redondeando la parte fraccional hacia abajo. Si el coste F del nuevo elemento es menor, no saltamos esos 2 elementos. Luego comparamos el nuevo elemento con su padre que está en la posición (posición actual en la pila)/2, redondeando hacia abajo. Si su valor F es menor, los saltamos de nuevo. Repetimos este proceso hasta que el elemento no se menor que su padre, o hasta que el elemento haya rebasado el principio de la pila, lo que representa la posición 1 de la matriz.

Supongamos que añadimos un elemento con una F de 17 a nuestra pila. En este momento tenemos 7 elementos en ella, así que el nuevo elemento debería situarse en la posición número 8. Así queda la pila; el nuevo elemento está subrayado:

10 30 20 34 38 30 24 17

Luego comparamos este elemento con su padre, el cual esta en la posición 8/2 = posición 4. El valor F del elemento que ahora mismo está en la posición 4 es 34. Ya que 17 es menor que 34 intercambiamos sus respectivas posiciones.

10 30 20 17 38 30 24 34

Después lo comparamos con su nuevo padre. Como está en la posición 4 lo comparamos con el elemento en la posición 2 (4/2=2). Ese elemento tiene una puntuación F de 30. Ya que 17 es menor que 30, y ahora nuestra pila sería así:

10 17 20 30 38 30 24 34

Luego lo comparamos con su nuevo padre. Ahora que está en la posición 2, lo comparamos con la posición 1 (2/2), que es la posición del primer elemento de la pila. En este caso, 17, no es menor que 10, así que nos paramos y dejamos la pila como está.

Quitando Elementos de la Pila

Eliminar elementos de la pila, implica un proceso similar, pero en orden inverso. Primero, quitamos el elemento del hueco 1, que ahora se quedaría vacío. Luego cogemos el último elemento de la pila y lo llevamos al hueco 1. Tomando como ejemplo la pila anterior, ahora tenemos que el que antes fue el último elemento de la pila ahora está subrayado:

34 17 20 30 38 30 24

Lo siguiente es comparar el elemento con cada uno de sus hijos, los cuales están en las posiciones (posición actual x 2) y (posición actual x 2+1). Si tiene una puntuación menor que sus 2 hijos, se queda donde está. Si no, intercambiamos su posición con el menor de sus hijos. Así que, en este caso, los dos hijos del elemento en la posición 1, están en la posición 1×2=2 y 1×2+1=3. Ya que 34 no es menor que sus hijos lo intercambiamos por el menor de ellos, en este caso el 17. La cosa queda así:

17 34 20 30 38 30 24

Ahora comparamos el elemento con sus 2 hijos, que están en la posición 2×2=4, y 2×2+1=5. Como 34 no es menor que sus hijos lo intercambiamos por el menor (el 30 en la posición 4). Ahora nos sale esto:

17 30 20 34 38 30 24

Por último comparamos el elemento con su nuevo hijo. Como ya sabes, están en las posiciones 4×2=8 y 4×2+1=9. Sin embargo, no hay ningún hijo en esas posiciones, esto se debe a que la lista no es tan larga. Hemos alcanzado el último nivel de la pila, así que paramos.

¿Porqué una Pila Binaria es tan Rápida?

Ahora que sabes los principios de la inserción y borrado en una pila, deberías empezar a ver por qué es mucho más rápido, que por ejemplo, un insertion sort. Imagina que tienes una lista abierta con 1000 nodos, cosa que no es imposible en un mapa respetable con muchos nodos (recuerda que un mapa de solo 100 x 100 nodos, tiene 10000). Si hicieses un simple insertion sort, empezarías al principio de la lista, y procederías hasta encontrar la posición adecuada para insertar el nuevo elemento, tendrías que hacer una media de 500 comparaciones antes de insertarlo en el lugar adecuado.

Usando una pila binaria, solo necesitas hacer una media de 1-3 comparaciones para insertarlo en el lugar correcto, empezando desde el final. También necesitarías hacer una media de 9 comparaciones para eliminar de la lista abierta y reordenar la pila apropiadamente. En un A*, normalmente eliminas un nodo en cada paso (el elemento con el coste F más bajo), y usualmente añades en cualquier lugar de 0 a 5 nodos (usando el enfoque 2D descrito en el artículo principal). Esto puede alcanzar más o menos el 1% del tiempo que lleva hacer una insertion sort con el mismo número de nodos. La diferencia se hará geométricamente más importante en mapas mayores (con más nodos). En comparación, mapas más pequeños, ganan paulatinamente menos ventaja, cosa que se debe a que las pilas binarias pierden su importancia cuanto más pequeño sea el mapa y su número de nodos sea menor.

De todas formas, solo porque vayas a usar una pila binaria, no significa que tu algoritmo vaya a ser 100 más rápido (o lo que sea). En un algoritmo A*, hay muchas cosas más importantes que ordenar solamente la lista abierta. Sin embargo, mi experiencia me dice que usar pilas binarias hace que tu algoritmo pathfinding sea en muchos casos, 2 o 3 veces más rápido, tal vez incluso más en caminos largos.

Creando una Lista Abierta

Ahora que sabemos lo que es una pila, ¿Cómo vamos a usarla? Lo primero que necesitamos hacer es dimensionar nuestra matriz mono-dimensional apropiadamente. Para hacer esto, lo primero que necesitamos es hacernos una idea de como será posiblemente de grande. Por norma, la lista no puede ser mayor que el número total de nodos de nuestro mapa (asumiendo en el peor de los casos, un escenario donde el camino se busque teniendo en cuenta todo el mapa). En un cuadrado mapa bidimensional como el que describí en el artículo principal, no tendremos más de AnchoMapa x AltoMapa nodos. Es una indicación de que tan grande será nuestra matriz unidimensional. Por el bien de este ejemplo, nosotros llamaremos a esta matriz listaAbierta(). El elemento superior se guardará en listaAbierta(1), el segundo en la pila estará en listaAbierta(2), y así.

Usando Punteros

Ahora que tenemos una pila/matriz unidimensional con el tamaño adecuado, estamos casi listos para empezar a usarlo para un pathfinding. Antes de que vayamos más lejos, vamos a echar de nuevo un vistazo a nuestra pila original antes de añadir o quitar nada.

Ahora mismo, es solo una lista de valores de F organizados debidamente. Pero olvidamos un elemento importante. Claro que tenemos un grupo de valores F organizados por orden en una pila binaria, pero no tenemos pistas de a que cuadros pertenecen. Básicamente, lo único que sabemos ahora mismo, es que el 10 es el menor valor de la pila. Pero, ¿a qué cuadrado de nuestro mapa hace referencia?

Para solucionar este problema, necesitamos cambiar los valores de los elementos de la matriz. En vez de guardar el valor F en la matriz, necesitamos guardar un único número identificador que nos indique a qué cuadro se refiere. Mi idea es crear un único ID (número identificador) asociado con cada nuevo elemento añadido a la pila, llamado cuadrosComprobados. Cada vez que añadimos un elemento a la lista abierta, incrementamos cuadrosComprobados en uno y lo usamos como único ID para los nuevos elementos añadidos a la lista abierta. El primer elemento añadido es el elemento 1, el segundo el 2,…

Por último, necesitamos guardar el coste actual de ese cuadro en una tabla unidimensional a parte, a la que llamo costeF(). Al igual que la matriz listaAbierta, el tamaño será el mismo,  AnchoMapa x AltoMapa. También guardaremos las coordenadas x e y del nodo en el mapa, en matrices unidimensionales similares, que llamaré abiertoX() y abiertoY(). Se parecería a la siguiente ilustración:

Aunque esto parezca un poco más complicado, es la misma pila que la anterior. La diferencia está en que ahora tenemos mucha más información.

El elemento 5 (con el costeF menor – 10) aún sigue al principio de la pila y en la primera columna de nuestra matriz unidimensional. Pero ahora estamos guardando un ID único de 5 en vez de su coste F en la pila. En otras palabras,  listaAbierta(1) = 5. Este número único se usa luego, para mirar el costeF del elemento y su localización X e Y en el mapa. El costeF de este elemento es costeF(5)=10, su localización en el mapa es,  abiertoX(5)=12 y abiertoY(5)=22.

El elemento superior de la pila tiene 2 hijos, los elementos con el número 2 y el 6, tienen un costeF de 30 y 20 respectivamente y están en las posiciones 2 y 3 de la listaAbierta(), y así hasta el final. En resumen, tenemos exactamente la misma pila que teníamos al principio, solo que con mucha más información, ahora sabemos donde está el elemento en el mapa y su costeF.

Añadiendo Nuevos Elementos a la Pila (Parte 2)

Ahora vamos a aplicar esta técnica para ordenar nuestra lista de una forma que sea útil en un algoritmo de un pathfinding A*. Usaremos exactamente las mismas técnicas explicadas anteriormente.

El primer elemento que añadamos a la lista abierta, es normalmente el nodo principal y se le asigna un ID único, en este caso 1. Luego lo ponemos en la posición 1 de la lista abierta. En otras palabras, listaAbierta(1)=1. También mantenemos un seguimiento al número de elementos de nuestra lista, que es 1 por ahora. Guardamos este número en una variable llamada numeroDeElementosEnListaAbierta.

Así que, añadimos nuevos nodos a la lista abierta, calculando sus puntuaciones G, H y F, como está descrito en el artículo principal. Después los añadimos a la pila binaria como está señalado más arriba.

Primero asignamos el nuevo elemento a un ID único para la variable cuadrosComprobados. Le sumamos 1 cada vez que añadamos un nuevo nodo, y asignamos este número al nuevo nodo. Luego sumamos 1 a numeroDeElementosEnListaAbierta, y después lo añadimos al final de la lista abierta. Todo lo anterior se traduce en lo siguiente:

cuadrosComprobados = cuadrosComprobados +1
numeroDeElementosEnListaAbierta= numeroDeElementosEnListaAbierta+1
listaAbierta(numeroDeElementosEnListaAbierta) = cuadrosComprobados

Después hacemos sucesivas comparaciones con su padre hasta que alcance su lugar apropiado en la pila. Aquí hay algún código que lo hace:

m = numeroDeElementosEnListaAbierta
While m <> 1 ;Mientras que el elemento no ha alcanzado el principio(m=1)

	;Comprueba si el hijo es <= padre. Si es así los intercambia.
	If costF(listaAbierta(m)) <= costF(listaAbierta(m/2)) Then
		temp = listaAbierta(m/2)
		listaAbierta(m/2) = listaAbierta(m)
		listaAbierta(m) = temp
		m = m/2
	Else
		Exit ;sale del bucle while/wend
	End If
Wend

Borrando Elementos de la Pila (Parte 2)

Por supuesto, no solo construimos una pila, también necesitamos borrar elementos de ella cuando ya no los vayamos a utilizar de nuevo. Específicamente en el pathfinding A*, necesitamos borrar el elemento con el coste F menor del principio de la lista después de haberlo comprobado y pasado a la lista cerrada.

Antes describimos como se empieza moviendo el ultimo elemento de la pila hasta la primera posición, y luego reducimos el número de elementos de la lista en uno. En pseudocódigo sería así:

listaAbierta(1) = listaAbierta(numeroDeElementosEnListaAbierta)
numeroDeElementosEnListaAbierta = numeroDeElementosEnListaAbierta - 1

Lo siguiente que necesitamos hacer es sucesivas comparaciones entre este valor y sus dos hijos. Si tiene una puntuación F mayor que alguno de ellos, intercambiaremos su posición con el menor. Luego comparamos el elemento con sus 2 nuevos hijos (ahora que está más abajo en la pila). Si tiene su F es mayor que cualquiera de sus hijos, lo intercambiamos por el menor. Repetimos este proceso hasta que el elemento encuentre su lugar correcto, que podría ser el final de la pila, pero no necesariamente. Aquí tienes el pseudocódigo de lo dicho:

;Repite lo siguiente hasta que el elemento encaje en su lugar adecuado en la pila.
Repeat
	u = v
	If 2*u+1 <= numeroDeElementosEnListaAbierta ;si ambos hijos existen 		;Selecciona el menor hijo de los 2. 		If costF(listaAbierta(u)) >= costF(listaAbierta(2*u)) then v = 2*u ;VER NOTA MÁS ABAJO
		If costF(listaAbierta(v)) >= costF(listaAbierta(2*u+1)) then v = 2*u+1 ;VER NOTA MÁS ABAJO

	Else If 2*u <= numeroDeElementosEnListaAbierta ;si solo el hijo 1 existe 		;Comprueba si el coste F es mayorque el del hijo 		If costF(listaAbierta(u)) >= costF(listaAbierta(2*u)) then v = 2*u
	End If

	If u <> v then ; Si el F del padre > al de uno o al de los dos hijos, los intercambia
		temp = listaAbierta(u)
		listaAbierta(u) = listaAbierta(v)
		listaAbierta(v) = temp
	Else
		Exit ;si el elemento <= que ambos hijos, sale del bucle repeat/forever
	End if
Forever ;Repetir siempre

Por favor, observa en el código, la u y la v en negrita (en rojo) . En la segunda línea, quieres usar v, no u, cosa que podría no ser inmediatamente obvia. Esto te asegura que acabes intercambiando con el menor de los 2 hijos. Fallar haciendo esto, te dará una pila errónea, y joderá tu pathfinding completamente.

Reordenando un Elemento Existente en una Lista Abierta

Tal y como se describió en el artículo principal, llegará un momento en el que te des cuenta que la puntuación F de una lista puede cambiar. Cuando eso ocurre, no necesitas sacar el elemento de la lista y empezar todo de nuevo. Simplemente empiezas en su posición actual, y lo comparas con su padre usando su nueva (y menor) puntuación F. En general, usamos el mismo código descrito en la sección “Añadiendo un Elemento a la Pila” con la siguiente consideración adicional:

Desafortunadamente, debido a que tus datos son una enorme y aparentemente desordenada pila, necesitas recorrerla por completo para encontrar un elemento en su interior. Básicamente estarás buscando el cuadro con las coordenadas x e y correctas, como se indica en abiertoX(listaAbierta()) y abiertoY(listaAbierta()). Sin embargo, después de encontrarlo, puedes proceder normalmente haciendo las comparaciones necesarias y empezando los intercambios desde su posición dentro de la pila.

Notas Finales

Tengo la esperanza de que si has llegado hasta aquí y aún estás leyendo , significa que no estás totalmente confundido. Si no te sientes intimidado, y quieres codificar tu propia pila binaria para tu propio algoritmo de pathfinding, entonces esto es lo que te sugiero:

Primero, olvida las pilas binarias por un momento. Concéntrate en conseguir que tu algoritmo A* funcione correctamente y que esté libre de errores usando un método simple para ordenar. Al principio solo necesitas que funcione, no que vaya rápido.

Segundo, antes de que añadas una pila binaria al código, intenta codificar una pila binaria aparte que haga lo que tu quieras, añadiendo y substrayendo elementos de la pila de una forma correcta. Asegúrate de escribir el programa de forma que puedas reconocer qué función realiza cada paso del proceso, quizá imprimiendo los resultados en la pantalla conforme lo vayas ejecutando. Deberías incluir alguna tecla de escape en el programa que te permita salir si fuera necesario, es muy fácil quedar atrapado en un bucle sin fin si no has escrito la pila binaria correctamente.

Una vez que confíes en que ambos programas funcionan perfectamente, guarda una copia de los 2, y luego empieza a trabajar en unirlos. Amenos que seas mucho más listo que yo, probablemente tendrás problemas al principio. Signos de tus errores serán extraños mensaje de error y misteriosos caminos ilógicos. No desesperes, al final lo conseguirás.

3 Comentarios en "Usando Pilas Binarias en Pathfinding A*"

  1. Jose dice:

    xD, muy interesante el tema de las pilas binarias. Yo lo conocía como “max heap”.

    Yo he usado un A* para realizar el juego del Wumpus por lo que la velocidad no es algo que se notara (apenas unos pocos nodos).

    Haces fácil lo difícil xD.

    Saludos.

  2. admin dice:

    Jose, todo depende del Numero de nodos, si por ejemplo es un juego que tiene un mapa de 1000×1000 Nodos unos 1000000, cualquier cosa que haga mejora supone ganar rapidez.

    Para grillas de Nodos no tan grande obviamente no es tan determinante.

  3. seniorH dice:

    A menudo escucho decir, en gamedev.net por ejemplo, que la optimización prematura es la raíz de todos los problemas. La pila binaria es una optimización para las listas abierta y cerrada del algoritmo A*, si entiendo correctamente su valor para el fin que nos interesa. Por eso he decidido no intentarlo aún pero este artículo realmente es un tesoro y en español, muchas gracias.

    Quicksort fue mi primer intento, un enlace interesante http://www.sorting-algorithms.com/

Deja un comentario