Busqueda Heuristica

BÚSQUEDA HEURÍSTICA Introducción La búsqueda es una de las técnicas más utilizadas para resolver los problemas de pathfinding o planificación que se presentan en la inteligencia artificial en los juegos de vídeo. En particular, la búsqueda es utilizada para resolver el problema de la navegación. La constante evolución de los juegos de vídeo ha llevado a que la inteligencia artificial constituya uno de los aspectos más importantes; es fundamental que los agentes (entidades autónomas) controlados por la computadora se comporten en forma inteligente. Un problema característico es la navegación, que consiste en determinar el camino más conveniente entre una posición inicial y una posición de destino. Si bien el planteo del problema es sencillo, el mismo está lejos de ser trivial debido a la creciente complejidad de los entornos simulados y los requerimientos de tiempo real de los juegos modernos. Clasificación de los algoritmos de búsqueda.

Definición La búsqueda es una técnica para resolver problemas cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de un único agente. Por lo tanto se puede decir que los algoritmos de búsqueda heurística son método computacional para resolver problemas de pathfinding “búsqueda de la mejor ruta del punto A al punto B”.

De los distintos tipos de algoritmos de búsqueda, los algoritmos búsqueda heurística completa se encuentran ampliamente difundidos, el algoritmo A* es el algoritmo de búsqueda heurística más popular.

Algoritmo de búsqueda A* DEFINICIÓN El algoritmo de búsqueda A* o también denominado “A Estrella” se encuentra dentro de los tipos de algoritmos de búsqueda en grafos, representado por Peter E. Hart, Nils J. Nilsson y Bertram Rápale, en 1968. El algoritmo A* es el único que garantiza, sea cual sea la función heurística, que se tiene en cuenta el camino recorrido y por ende es mejor que la versión más extendida de "primero el mejor", aquélla que sólo considera la distancia a la meta. En definitiva, sí tiene razón en el caso concreto que usted plantea, pero no la tiene en general. REPRESENTACIÓN A continuación se muestra la clásica representación del algoritmo A *. Donde:

f'(n) = g(n) + h'(n)

g (n) es la distancia total que ha tomado para llegar desde la posición inicial a la ubicación actual. h '(n) es la estimación de la distancia desde la posición actual con el destino, es una función heurística se utiliza para crear esta estimación sobre cuan lejos se esta para alcanzar la meta. f '(n) es la suma de g (n) y h' (n). Este es el camino actual estimado más corto. f (n) es el verdadero camino más corto que no se descubrieron hasta que el algoritmo A * ha terminado. Ejemplo: Una familia cuando se dirige de vacaciones, y uno pregunta al padre que esta al volante, "¿Cuánto más falta para llegar?", a lo cual el Papa dirá supongo "Otras 300 millas”, si la familia ya había conducido 100 millas en ese punto, que representan g (n), el total de distancia recorrida hasta el momento. La estimación de 300 millas se h '(n), el adivinar en cuánto más sería. Por lo tanto, el f '(n) sería de 100 + 300 = 400 millas.

Ejemplo: pequeño juego.

CARACTERISTICAS  Realiza la búsqueda informada teniendo en cuenta dos factores fundamentales, el valor heurístico de los nodos y el coste real del recorrido.  Se utiliza en la búsqueda de un camino más corto.  El Algoritmo no desarrolla un camino por interacción, sino que desarrolla varios caminos y elige los más prometedores.  Tiene algunas buenas referencias y consejos acerca elementos de juego de la programación y la industria del juego, ejemplo tetris, camino más corto entre dos puntos.  Es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.  Si para todo nodo n del grafo se cumple que g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, el algoritmo A* pasa a ser una búsqueda de coste uniforme no informada.  Para garantizar la optimalidad del algoritmo, la función h(n) debe ser admisible, quiere decir que no sobrestime el coste real de alcanzar el nodo objetivo, si fuese así el algoritmo pasa a denominarse simplemente A, debido a que no se asegura que el resultado obtenido sea el camino de coste mínimo.  Debido a que se tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema.

APLICACIONES Se mencionará algunas aplicaciones: •

Minería de datos, búsqueda de comportamiento en los datos.

•

Procesamiento de imágenes.

•

Medicina humana, software médicos, control de tumores, problemas cancerigenos, VESALIO.

•

En la aeronavegación y transporte, el pilotaje automático, búsquedas de rutas mas próximas.

•

Video juegos de estrategia, camino más corto, ejemplo Pacman: Los fantasmas que persiguen a Pacman buscan el camino mas corto, en lugar de aparecer en forma aleatoria en el Mapa del Juego.

•

Juegos, ejemplo Age of Empires, un juego de conquista de civilizaciones, los enemigos salvan obstáculos para llegar a la ciudad del adversario.

SEGUIMIENTO Y EXPLICACION DEL PSEUDOCODIGO Para explicar el funcionamiento del código primero vamos a ver algunas definiciones funcionamientos previos respecto a las áreas de búsquedas. Introducción: El Área de Búsqueda Vamos a asumir que tenemos a alguien que quiere ir desde el punto A hasta el punto B. Asumamos también que un muro separa estos dos puntos, esto se puede ver en el gráfico siguiente, donde el recuadro verde es el punto de inicio A, el rojo es el punto de destino B y la zona azul el muro que hay entre ambos.

Lo primero que deberías advertir es que hemos dividido nuestra área de búsqueda en una rejilla cuadrada. Simplificar el área, tal y como hemos hecho, es el primer paso en un pathfinding. Este particular método reduce nuestra área de búsqueda a una simple matriz bidimensional. Cada elemento de la matriz representa uno de los cuadrados de la rejilla, y su estado se almacena como transitable o intransitable. El camino se elige calculando qué cuadros deberíamos pisar para ir desde A hasta B. Una vez que el camino haya sido encontrado, el personaje de nuestro juego (o lo que sea) se moverá desde el centro de un cuadrado hacia el centro del siguiente hasta que el objetivo haya sido alcanzado. A esos puntos centrales se les llama "nodos". Cuando leas en cualquier otro sitio sobre pathfinding, a menudo verás a gente hablando sobre nodos. ¿Acaso no es más fácil referirse a ellos como cuadrados? Esto se debe a que es posible dividir nuestra área en otras cosas aparte de cuadrados. Podrían ser rectangulares, hexagonales, o de cualquier otra forma; y podrían situarse en cualquier lugar dentro de esas formas - en el centro, por los bordes, o en cualquier lugar. Se usa este sistema porque es el más simple. Iniciando la Búsqueda Una vez que hemos simplificado nuestro área de búsqueda en un número de nodos accesible, tal y como hemos hecho con la rejilla de la figura anterior, el siguiente paso es dirigir una búsqueda para encontrar el camino más corto. En el pathfinding A*, lo hacemos empezando desde el punto A, comprobando los cuadros adyacentes y generalmente buscando hacia fuera hasta que encontremos nuestro destino. Empezamos la búsqueda haciendo lo siguiente: 1. Empieza en el punto inicial A y añádelo a una "lista abierta" de cuadrados a tener en cuenta. La lista abierta es como una lista de la compra. Ahora mismo solo tenemos un elemento en la lista, pero más tarde tendremos más. La lista contiene los cuadrados que podrían formar parte del camino que queremos tomar, pero que quizás no lo hagan. Básicamente, esta es una lista de los cuadrados que necesitan ser comprobados. 2. Mira en todos los cuadrados alcanzables o transitables adyacentes al punto de inicio, ignorando cuadrados con muros, agua u otros terrenos prohibidos. Añádelos a la lista abierta también. Por cada uno de esos cuadrados, guarda el punto A como su "cuadrado padre". El cuadrado padre es muy importante para trazar nuestro camino. Se explicará más adelante. 3. Saca el cuadro inicial A desde tu lista abierta y añádelo a una "lista cerrada" de cuadrados que no necesitan, por ahora, ser mirados de nuevo. En este punto, deberías tener algo como la siguiente ilustración. En este diagrama, el cuadrado verde oscuro del centro es tu cuadrado de inicio. Esta bordeado el azul claro para indicar que el cuadrado ha sido añadido a la lista cerrada. Todos los cuadros adyacentes están ahora en la lista abierta para ser comprobados, están bordeados con verde claro. Cada uno tiene un puntero gris que señala a su padre, el cual es el cuadro inicial.

Después, elegimos uno de los cuadrados adyacentes de la lista abierta y más o menos repetimos el proceso anterior como se describe un poco más abajo. Pero, ¿cual cuadro debemos elegir? Aquel que tenga el coste F más bajo. Puntuando el camino La clave para determinar que cuadrados usaremos para resolver el camino está en la siguiente ecuación: F=G+H Donde •

G = el coste de movimiento para ir desde el punto inicial ‘A’ a un cierto cuadro de la rejilla, siguiendo el camino generado para llegar allí.

•

h = el coste de movimiento estimado para ir desde ese cuadro de la rejilla hasta el destino final, el punto B. Esto es a menudo nombrado como la heurística, la cual puede ser un poco confusa. La razón por la cual es llamada así, se debe a que es una suposición. Realmente no sabemos la distancia actual hasta que encontramos el camino, ya que toda clase de cosas pueden estar en nuestro camino (muros, agua, etc.), existen muchas formas de calcular H.

Nuestro camino se genera por ir repetidamente a través de nuestra lista abierta y eligiendo el cuadrado con la puntuación F más baja. Este proceso se describirá con más detalle un poco más adelante. Primero veamos más de cerca cómo calculamos la ecuación. Tal y como está descrito más arriba, G es el coste de movimiento para ir desde el punto de inicio a un cierto cuadro usando el camino generado para llegar allí. En este ejemplo asignaremos un coste de 10 a cada cuadro vertical u horizontal hacia el que nos movamos, y un coste de 14 para un movimiento diagonal. Usamos estos números porque la distancia actual para mover diagonalmente es el cuadrado de la raíz de 2 (no temas), o mas o menos 1,414 veces el coste del movimiento horizontal o vertical. Usamos 10 y 14 con el fin de simplificar. El rango es bastante bueno, y así nos libramos de tener que calcular raíces cuadradas y sus decimales. Esto no es solo porque seamos idiotas y no nos gusten las matemáticas; usar números enteros también es mucho más rápido para el ordenador. Pronto descubrirás que el pathfinding puede ser muy lento si no usas atajos como este. Ahora que hemos calculado el coste G mediante un camino específico hasta cierto cuadrado, la forma de resolver el coste G del cuadrado es coger el coste G de su padre, y luego añadirle 10 o 14 dependiendo de si está en diagonal u ortogonal(no diagonal) con respecto a ese cuadro padre. Este método se hará más claro cuando llevemos este ejemplo un poco más allá y nos alejemos un cuadro del inicial.

H puede ser estimado de diferentes maneras. El método que hemos usado aquí se llama el método Manhattan, donde calculas el número total de cuadros movidos horizontalmente y verticalmente para alcanzar el cuadrado destino desde el cuadro actual, sin hacer uso de movimientos diagonales. Luego multiplicamos el total por 10. Se llama método Manhattan porque es como calcular el número de manzanas que hay desde un lugar a otro, donde no puedes acortar atravesando en diagonal una manzana. Debemos señalar que cuando calculamos H, ignoramos cualquier obstáculo que intervenga. Es una estimación de la distancia que queda, no de la distancia actual, es por eso que se llama heurística. F se calcula sumando G y H. El resultado del primer paso en nuestra búsqueda puede ver se en la ilustración inferior. Las puntuaciones F, G y H están escritas en cada cuadrado. En el cuadro inmediatamente a la derecha de cuadro inicial, la F está impresa arriba a la izquierda, la G abajo a la izquierda y la H abajo la derecha.

Así pues, vamos a mirar algunos ejemplos de estos cuadros. En el cuadrado con letras, G =10. Esto es debido a que está solo a un cuadro del cuadrado inicial en dirección horizontal. Los cuadrados inmediatamente encima, abajo y a la izquierda del cuadrado inicial; tienen todos el mismo valor G de 10. Los cuadros diagonales tienen un valor G de 14. Las puntuaciones H se calculan estimando la distancia Manhattan hasta el cuadrado rojo objetivo, moviéndose solo horizontal y verticalmente e ignorando el muro que está en el camino. Usando este método, el cuadro de la derecha del inicial, está a 3 cuadros del cuadrado rojo con una puntuación H de 30. El cuadrado está a solo 4 cuadros de distancia (recuerda que solo nos movemos en horizontal y vertical) con una puntuación H de 40. Probablemente comprendas como se calculan las puntuaciones H para los demás cuadros. De nuevo, la puntuación F de cada cuadro se calcula simplemente sumando G y H.

Continuando la búsqueda Para continuar la búsqueda, simplemente elegimos la puntuación F más baja de todos aquellos que estén en la lista abierta. Después hacemos lo siguiente con el cuadro seleccionado: 4) Sácalo de la lista abierta y añádelo a la lista cerrada. 5) Comprueba todos los cuadrados adyacentes, ignorando aquellos que estén en la lista cerrada o que sean intransitables terrenos con muros, agua, o cualquier terreno prohibido), añade los cuadros a la lista abierta si no están ya en esa lista. Haz al cuadro seleccionado el "padre" de los nuevos cuadros. 6) Si el cuadro adyacente ya está en la lista abierta, comprueba si el camino a ese cuadro es mejor que este. En otras palabras, comprueba que la G de ese cuadro sea más baja que la del que estamos usando para ir allí. Si no es así, no hagas nada. Por otro lado, si el coste G del nuevo camino es más bajo, cambia el padre del cuadro adyacente al cuadro seleccionado (en el diagrama superior, cambia la dirección del puntero para que señale al cuadro seleccionado). Finalmente, recalcula la F y la G de ese cuadrado. Si esto te parece confuso, podrás verlo ilustrado más abajo. Ahora vamos a ver como funciona. De nuestros 9 cuadros iniciales, dejamos 8 en la lista abierta después de que el cuadrado inicial fuera incluido en la lista cerrada. De estos, el que tiene el coste F más bajo es el de inmediatamente a la derecha del cuadro inicial, con una F de 40. Así que seleccionamos este cuadrado como nuestro siguiente cuadrado. Está resaltado en azul en la imagen mostrada.

Primero, lo sacamos de nuestra lista abierta y lo añadimos a nuestra lista cerrada (por que ahora está resaltado en azul). Luego comprobamos los cuadros adyacentes. Todos los que hay a la derecha son cuadros de muro, así que no los tenemos en cuenta. El de la izquierda es el cuadrado inicial; ese está en la lista cerrada, así que lo ignoramos también.

Los otros 4 cuadrados ya están en la lista abierta, así que necesitamos comprobar si alguno de los caminos hasta esos cuadros es mejor que el del cuadrado actual hasta ellos. Para eso usaremos la puntuación G como punto de referencia. Miremos debajo de nuestro cuadrado seleccionado; su G actual es 14. Si fuésemos a través del cuadro actual hasta allí, la G sería igual a 20 (10, la G del cuadro actual, más 10 de un movimiento vertical hacia el cuadro superior). Una G de 20 es mayor que una de 14, así que no es un buen camino. Todo eso debería cobrar sentido si miras el diagrama. Es más directo llegar a ese cuadro desde el cuadro inicial moviéndote un cuadro en diagonal, que moverte horizontalmente un cuadro y luego verticalmente otro. Cuando repetimos este proceso para los otros 4 cuadros adyacentes que ya están en la lista abierta, descubrimos que ninguno de los caminos ha mejorado por ir a través del cuadro actual (el de la derecha bordeada de azul), así que pasamos de él. Ahora que hemos mirado en todos los cuadros adyacentes y ya nos hemos hecho con este nuevo cuadro, estamos listos para movernos al siguiente cuadrado. Recorremos el grupo de cuadros de nuestra lista abierta, ahora ha bajado a 7 cuadrados, cogemos el que tenga el coste F más bajo. Interesante, en este caso hay dos cuadros que tienen una puntuación de 54. Así que, ¿cual elegimos? La verdad es que no importa. Para propósitos de velocidad, puede ser más rápido elegir el último que añadimos a la lista abierta. Esto influencia a la búsqueda en favor de cuadros que fueron encontrados más tarde justo cuando estés más cerca de alcanzar tu objetivo. De todas formas no es verdaderamente importante. Así pues, y ya que lo elegimos anteriormente, escogemos el cuadro justo debajo del cuadrado que desechamos antes. La siguiente figura se ve mas claro: E

sta

vez, cuando comprobamos los cuadrados adyacentes encontramos que el de la izquierda y el superior a este son cuadros de muro así que los ignoramos. Tampoco tenemos en cuenta el cuadro que está debajo del muro. ¿Por qué? Porque no puedes llegar a ese cuadrado sin que tu

personaje se raspe el hombro con la esquina al intentar pasar en diagonal; lo mejor es dar un pequeño rodeo, primero bajando y luego yendo hacia la derecha. (Nota: Esta regla de bordear esquinas es opcional. Su uso depende de como estén situados tus nodos.) Eso nos deja otros 5 cuadros. Los otros 2 cuadros bajo el actual no están en la lista abierta así que los añadimos y el cuadro actual se convierte en su padre. De esos otros 3 cuadros, 2 ya están en la lista cerrada (el cuadro inicial, y el cuadro que hay encima del actual, ambos resaltados en azul en el diagrama) así que los ignoramos. El último cuadro, el de la izquierda del cuadro actual, se comprueba para ver si el coste G hasta él desde el cuadro actual, es menor que llegando directamente desde el cuadro inicial. Lo hacemos y no hay suerte, así que ya estamos listos para comprobar el siguiente cuadro de nuestra lista abierta. Repetimos este proceso hasta que añadimos el cuadro objetivo a la lista abierta, en ese momento parecería algo como la imagen de abajo:

Observa que el cuadro padre para el cuadrado dos cuadros por debajo del cuadro inicial ha cambiado desde la ilustración anterior. Antes tenía un coste G de 28 y apuntaba al cuadrado encima suya y a la derecha. Ahora tiene una puntuación de 20 y apunta al cuadrado encima suya. Esto ocurrió en algún momento por la forma en la que se ejecuta nuestra búsqueda, donde la puntuación G fue comprobada y devuelta más baja usando un nuevo camino - el padre cambió y G y F fueron recalculadas. A pesar de que este cambio no parece demasiado importante en este ejemplo, hay muchas posibles situaciones donde este constante control significará la diferencia en la determinación del mejor camino hasta tu objetivo. Pero, ¿cómo determinamos el camino actual en si mismo? Fácil, sólo empiezas desde el cuadro objetivo rojo, y vas hacia atrás de un cuadrado a su padre, siguiendo las flechas. Eso te llevará de

vuelta al cuadrado inicial y tus movimientos serán el camino a seguir. Debería parecerse a la siguiente ilustración. Moverse desde el cuadro inicial A hasta el cuadro destino B es solo cuestión de ir moviéndose desde el centro de un cuadro (el nodo) al siguiente hasta alcanzar el objetivo.

Resumen del Método A*

Ahora que has leído la explicación, vamos a resumir el método paso a aso: 1) Añade el cuadro inicial a la lista abierta. 2) Repite lo siguiente: a) Busca el cuadro con el coste F más bajo en la lista abierta. Nos referimos a este como el cuadro actual. b) Cámbialo a la lista cerrada c) Para cada uno de los 8 cuadros adyacentes al cuadro actual... •

Si no es transitable o si está en la lista cerrada, ignóralo. En cualquier otro caso haz lo siguiente.

•

Si no está en la lista abierta, añádelo a la lista abierta. Haz que el cuadro actual sea el padre de este cuadro. Almacena los costes F, G y H del cuadro.

•

Si ya está en la lista abierta, comprueba si el camino para ese es mejor usando el coste G como baremo. Un coste G menor significa que este es un mejor camino. Si es así, cambia el padre del cuadrado al cuadro actual y recalcula G y F del cuadro. Si estás manteniendo la lista abierta por orden de puntuación F, podrías necesitar reordenar la lista para llevar cuenta del cambio.

d) Para cuando: •

añadas el cuadro objetivo a la lista abierta en cuyo caso el camino ha sido encontrado, o

•

falles en encontrar el cuadro objetivo y la lista abierta esté vacía. En este caso no hay camino.

3) Guarda el camino. Muévete hacia atrás desde el cuadro objetivo, ve desde cada cuadro a su padre hasta que alcances el cuadro inicial. El camino seguido es el que buscas. CONCLUSIONES  La implementación esta involucra almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema.  Los puntos tratados en el trabajo sintetizan las conclusiones.

APLICACIÓN PRÁCTICA EN JAVA. Desde el punto A (azul), ir al punto B (rojo). 1. El escenario (derecho) y el mapeo correspondiente en la cuadricula (izquierda).

2. Representación del escenario en la cuadricula con sus respectivas restricciones.

3. Secuencia de pasos generados con el algoritmo y recorridos por el móvil.

4. El móvil una vez recorrido el camino, llega al punto B (rojo).

CÓDIGO LISP

;; ================================================================== ;; Variables globales (Ancho y altura) ;; ================================================================== (defvar *WIDTH* 5) (defvar *HEIGHT* 5) ;; ================================================================== ;; Estructura Nodo ;; -----------------------------------------------------------------;; DESCRIPCION ;; -----------------------------------------------------------------;; PARAMETROS ;; w : ;; ================================================================== (defstruct node (coord '(-1 -1)) (parent '(-1 -1)) (successors '()) ;; (successors (make-array '(8) :initial-element '(-1 -1))) ;; (num-successors 0) (been-seen '*) (f 0) (g 0) (h 0) ) ;; ================================================================== ;; init-array (w) ;; -----------------------------------------------------------------;; DESCRIPCION ;; -----------------------------------------------------------------;; PARAMETROS ;; w : ;; ================================================================== ;; se necesita inicializar cada elemento en la matriz, de lo ;; contrario, todos los elementos sólo apuntaran a la misma ubicación. ;; el código original es similar a este: ;; (w (make-array '(5 5) :initial-element (make-node)) ;; El problema con el que se apunta a sólo una instancia creada no ha ;; sido declarada dentro de una matriz. (defun init-array(w) (dotimes (i (array-dimension w 0)) (dotimes (j (array-dimension w 1)) (setf (aref w i j) (make-node :coord (LIST i j))) ) ) )

;; ================================================================== ;; a-star () // algoritmo “A estrella” ;; -----------------------------------------------------------------;; DESCRIPCION ;; ================================================================== (defun a-star () (let ( (s '(0 0)) ;; iniciar (g '(2 4)) ;; objetivo (start (make-node :been-seen 's)) (w (make-array '(5 5))) ;; Paso 1 (OPEN '()) (CLOSED '()) ;; Paso 2 ) (init-array w) ;; inicializando el mundo con nodos (setf (node-been-seen (aref w 0 0)) 's) (setf (node-parent (aref w 0 0)) '(0 0)) (setf (node-been-seen (aref w 2 4)) 'g) (SETF OPEN (CONS (aref w 0 0) OPEN)) ;; este también forma parte del Paso 1 (print-world w) ;; Necesario empezar a recorrer desde aquí (do ;; Entran las variables locales a este bucle DO ( (ret_val 0) (n '()) ;; nodo temporal (i -1) ;; fila actual de ‘n’ (j -1) ;; columna actual de ‘n’ ) ( (/= ret_val 0) );; ejecutar el bucle hasta que el valor de retorno sea 0 ;; ret_val = 1 : Exito! ;; ret_val = -1 : Error, no se ha encontrado una ruta ;; Paso 3 (COND ( (ENDP OPEN) (FORMAT T "Error: OPEN is empty.~%") (setf ret_val -1) ) ) ;; También debemos ver cuando ‘n’ se actualiza si el nodo en el mundo "w" También se

;; está actualizada, o si necesita ser actualizado después de cada bucle. ;; Paso 4 (SETF n (FIRST OPEN)) (SETF OPEN (REST OPEN)) (SETF CLOSED (CONS n CLOSED)) (SETF i (FIRST (node-coord n))) (SETF j (SECOND (node-coord n))) (FORMAT T "n: ~a ~%" n) ;; comprobar si el objetivo encontrar esta en el - Paso 5 (COND ( (EQUAL n NIL) (FORMAT T "N is NIL~%") ) ( (EQUAL (node-coord n) g) (FORMAT T "Found the goal.~%") (SETF ret_val 1) ) ;; si es así, entonces a rastrear marcando el camino (T ;; Paso 6 – generar sucesores (COND ((is-successor w (- i 1) (- j 1)) (add-successor n (- i 1) (- j 1)) ;; crear y añadir sucesores a la función (set-node n w (- i 1) (- j 1) g) (SETF OPEN (CONS (AREF w (- i 1) (- j 1)) OPEN)) ;; (SETF (node-parent (AREF w (- i 1) (- j 1))) (LIST i j)) ;; (SETF (node-been-seen (AREF w (-i 1) (- j 1))) '?) ) ) (COND ((is-successor w (- i 1) j) (add-successor n (- i 1) j) ;; crear y añadir sucesores a la función (set-node n w (- i 1) j g) (SETF OPEN (CONS (AREF w (- i 1) j) OPEN)) ) ) (COND ((is-successor w (- i 1) (+ j 1) ) (add-successor n (- i 1) (+ j 1)) ;; crear y añadir sucesores a la función (set-node n w (- i 1) (+ j 1) g) (SETF OPEN (CONS (AREF w (- i 1) (+ j 1)) OPEN)) ) ) (COND ((is-successor w i (- j 1))

(add-successor n i (- j 1)) ;; crear y añadir sucesores a la función (set-node n w i (- j 1) g) (SETF OPEN (CONS (AREF w i (- j 1)) OPEN)) ) ) (COND ((is-successor w i (+ j 1)) (add-successor n i (+ j 1)) ;; crear y añadir sucesores a la función (set-node n w i (+ j 1) g) (SETF OPEN (CONS (AREF w i (+ j 1)) OPEN)) ) ) (COND ((is-successor w (+ i 1) (- j 1)) (add-successor n (+ i 1) (- j 1)) ;; crear y añadir sucesores a la función (set-node n w (+ i 1) (- j 1) g) (SETF OPEN (CONS (AREF w (+ i 1) (- j 1)) OPEN)) ) ) (COND ((is-successor w (+ i 1) j) (add-successor n (+ i 1) j) ;; crear y añadir sucesores a la función (set-node n w (+ i 1) j g) (SETF OPEN (CONS (AREF w (+ i 1) j) OPEN)) ) ) (COND ((is-successor w (+ i 1) (+ j 1)) (add-successor n (+ i 1) (+ j 1)) ;; crear y añadir sucesores a la función (set-node n w (+ i 1) (+ j 1) g) (SETF OPEN (CONS (AREF w (+ i 1) (+ j 1)) OPEN)) ) ) ;; (FORMAT T "Open-list: ~a ~%" OPEN) ;; Paso 7 ;; Paso 8 – Reordenar la lista OPEN (SORT OPEN #'f-compare) ) ) ;; puede ser que necesite para copiar 'n' de nuevo en mundo w (print-world w)

) ;; Fin del bucle DO – Paso 9 ;; ahora, rastrear ... ;; fijó el objetivo de G (SETF (node-been-seen (AREF w (FIRST g) (SECOND g))) 'g) ;; bucle hasta volver a la meta de inicio ;; establecer cada nuevo tema como una T “verdadero” (DO ( (trail-coord g) ) ( (EQUAL trail-coord s) ) (SETF (node-been-seen (AREF w (FIRST trail-coord) (SECOND trail-coord))) 't) (SETF trail-coord (node-parent (AREF w (FIRST trail-coord) (SECOND trailcoord)))) ) (print-world w) ) ) ;; ================================================================== ;; is-successor (w i j) // es sucesor ( w i j) ;; -----------------------------------------------------------------;; DESCRIPCION ;; -----------------------------------------------------------------;; PARAMETROS ;; ================================================================== (defun is-successor(w i j) (COND ( (OR (< i 0) (>= i *WIDTH*)) NIL ) ( (OR (< j 0) (>= j *HEIGHT*)) NIL ) ( (EQUAL (node-been-seen (aref w i j)) 'g) T) ( (NOT (EQUAL (node-been-seen (aref w i j)) '* )) NIL) (T T) ) ) ;; ================================================================== ;; is-successor2 (n i j) ;; -----------------------------------------------------------------;; this is just a test case to make sure that it works (defun is-successor2(n i j) (COND ( (OR (< i 0) (>= i *WIDTH*)) NIL ) ( (OR (< j 0) (>= j *HEIGHT*)) NIL ) ( (NOT (EQUAL (node-been-seen n) '* )) NIL) (T T)

) ) ;; ================================================================== ;; add-successor (n i j) // agregar successor (n i j) ;; -----------------------------------------------------------------;; DESCRIPCION ;; -----------------------------------------------------------------;; PARAMETROS ;; i : sucesor de la fila a coordinar ;; j : sucesor de la columna a coordinar ;; ================================================================== (defun add-successor(n i j) (SETF (node-successors n) (CONS (LIST i j) (node-successors n))) ) ;; ================================================================== ;; set-node (n w i j goal) ;; -----------------------------------------------------------------;; DESCRIPCION ;; Establecer nuevos valores en el sucesor de nodo, como por ejemplo valores f, g, h ;; -----------------------------------------------------------------;; PARAMETROS ;; n : nodo padre actual ;; w : matriz 2-d que representa la red mundial del espacio ;; i : sucesor de la fila a coordinar ;; j : sucesor de la columna a coordinar ;; goal : coordenadas de la meta estatal ;; ================================================================== (defun set-node (n w i j goal) (SETF (node-parent (aref w i j)) (node-coord n)) ;; set the parent (SETF (node-g (aref w i j)) ( + (node-g n) 1)) ;; get the real distance to node (SETF (node-h (aref w i j)) (+ (ABS (- i (FIRST goal)) ) (ABS (- j (SECOND goal)) ) ) ) ;; (format t "g: ~a h: ~a ~%" (node-g (aref w i j)) (node-h (aref w i j)) ) (SETF (node-f (aref w i j)) (+ (node-g (aref w i j)) (node-h (aref w i j)) ) ) (SETF (node-been-seen (aref w i j)) 'x) ;; (SETF OPEN (CONS (aref w i j) OPEN)) ;; add node to the OPEN list ;; (format t " Open in set-node: ~a ~%" OPEN) ) ;; ================================================================== ;; print-world (w) // imprimir ‘w’ ;; -----------------------------------------------------------------;; DESCRIPCION ;; -----------------------------------------------------------------;; PARAMETROS ;; w : 2-d, matriz que representa la red total del espacio ;; ================================================================== (defun print-world(w)

(dotimes (i (array-dimension w 0)) (dotimes (j (array-dimension w 1)) (format t "~a " (node-been-seen (aref w i j))) ) (format t "~%") ) ) ;; ================================================================== ;; f-compare (item1 item2) // comparando item1 con item 2 ;; -----------------------------------------------------------------;; DESCRIPCION ;; Comparar el valor de f para ver que es mayor y el retorno, ya sea verdadera o falsa. ;; Esta comparación se utiliza para ordenar las funciones en LISP. ;; Luego si se desea ordenar la lista de menor a mayor. ;; -----------------------------------------------------------------;; PARAMETROS ;; item1 : el primer tema para comparar ;; item2 : el segundo tema para comparar ;; ================================================================== (defun f-compare (item1 item2) (< (node-f item1) (node-f item2) ) )

WEBGRAFIA  Código Lisp  http://www.edenwaith.com/products/pige/src/a-star.l  Código Java  http://www.edadfutura.com/algoritmo-a-en-java  Aplicación del algoritmo A* en juegos (tanquecito)  http://perso.wanadoo.es/jarecio/Aestrella/Applet.html  Código en LISP  http://www.edenwaith.com/products/pige/tutorials/a-star.php  Métodos en Lisp, del algoritmo  http://ccc.inaoep.mx/~emorales/Cursos/Busqueda04/node40.html  Algoritmo A* para principiantes, en Lisp Y C++  http://www.policyalmanac.org/games/articulo1.htmhttp://www.policyalmanac.org/games /aStarTutorial.htm