\newpage

En esta práctica se pedía desarrollar un controlador basado en alguna variante de A* dentro del entorno GVG\textunderscore AI que guíe a un avatar a resolver un juego en distintos niveles. El avatar debía además tener un comportamiento reactivo adecuado, ya que en el juego existen elementos como enemigos cuyo movimiento no es predecible.

La memoria se dividirá en 3 partes, una descripción general de la solución, otra del comportamiento reactivo y otra del comportamiento deliberativo.

A grandes rasgos el comportamiento del avatar se basa en lo siguiente.

• Realiza un estudio de las gemas que existen en el mapa (aprovechandose de que el mapa es conocido), el objetivo de esto es elegir el orden en el que se irá a cada una de las gemas teniendo en cuenta su posición y lo seguras que son.
• El avatar tiene un comportamiento deliberativo donde, según lo visto antes, va cogiendo gemas intentando siempre pasar por posiciones seguras (no presentan un riesgo evidente).
• En caso de que suceda algo inesperado, por ejemplo, una piedra cayendo sobre el avatar o un enemigo acercandose, dispone de una serie de reglas reactivas, todas basadas en garantizar su seguridad.
• La implementación del avatar se basa en una máquina de estados, donde es fácil llevar un control de la situación actual del avatar.

Aquí vemos un esquema de los diferentes estados en los que puede encontrarse el agente y de las transiciones que existen entre ellos.

(Looking for gem) as lfg
(Near wanted gem) as nwg
(Setting path for gem) as spfg
(Need new objetive) as nno
(Escaping) as e
(Got all gems) as gag
(Going to exit) as gte
(Just got gem) as jgg
(Reactive mode) as rm

nwg --> nno : Gema conseguida

lfg --> e : Peligro
lfg --> nwg : path.size == 1
lfg --> nno : path.empty

jgg --> nno : Era la gema buscada
jgg --> lfg : No era la gema buscada

spfg --> nno : No existe camino para la gema
spfg --> lfg : Existe camino a la gema
spfg --> rm : Está atascado
nno --> gag : 9 Gemas
nno --> spfg : <9 gemas

rm --> lfg : Desatascado

e --> nno

gag --> gte

gte --> e : Peligro

El código correspondiente al metodo act tiene la siguiente estructura.
\begin{algorithm}[H] \KwData{StateObservation stateObs} \KwResult{Types.ACTIONS acción}

\While{true}{

\Switch{estado}{
\uCase{LOOKING\_FOR\_GEM}{\ …\ } \uCase{JUST\_GOT\_GEM}{\ …\ } \uCase{NEAR\_WANTED\_GEM}{\ …\ } \uCase{NEED\_NEW\_OBJETIVE}{\ …\ } \uCase{SETTING\_PATH}{\ …\ } \uCase{GOT\_ALL\_GEMS}{\ …\ } \uCase{GOING\_TO\_EXIT}{\ …\ } \uCase{ESCAPING}{\ …\ } } } \caption{act} \end{algorithm}

\newpage

En este apartado estudiaremos como funciona el aspecto deliberativo del avatar, lo diviremos en varios sub-apartados.

El comportamiento respecto al estudio de las gemas en función de su colocación con el mapa es reactivo y heurístico, para seleccionar en que orden queremos intentar recoger las gemas. Este orden no será definitivo, puesto que la parte reactiva tendrá la capacidad de, en función de la situación, dejar de intentar obtener una gema para obetener otra. El proceso de selección de las gema es así:

\begin{algorithm}[H] \KwData{StateObservation StateObs} \KwResult{ArrayList<Observation> orderedGems} gemas = gemas\_disponibles()
pos = posicion\_jugador()

\While{queden\_gemas}{ ordenar\_gemas\_por\_heurística()

gema\_seleccionada = mejor\_gema
pos = posicion\_mejor\_gema

gemas.eliminar(mejor\_gema)
orderedGems.añadir\_al\_final(mejor\_gema)

} }

\caption{función: \textit{ordered\textunderscore gems}} \end{algorithm}

La heurística tiene en cuenta dos factores:

• Se beneficia a las gemas que no tengan una roca encima, pues no varían la conectividad de los nodos del mapa permitiendo así explotar primero las gemas disponibles en el estado actual, para explotar luego las que pasen a ser accesibles tras de variaciones del mapa.
• Se perjudica a las gemas con bichos cerca de forma radial. Esto implica que se perjudican de manera incremental segun tengan un bicho en un radio de 3, 2 o 1 bloque, utilizando la distancia manhattan para generar estas bolas.
• Cercania a la posición pos. Está se incializa a la posición donde aparece el jugador, y se va actualizando con respecto a cada gema. Esta cercacina se calcula como la distancia del path hallado por el pathfinder. Suponiendo un mapa vacío con solo gemas, nuestro orden se comportaría como una solución greedy del TSP.

De este modo nuestro jugador empieza con un orden coherente para intentar recoger las gemas. El vector de gemas se recorre en sentido FIFO.

La forma en la que el avatar computa las rutas para llegar a las gemas es utilizando un algoritmo A^*, como el entorno GVG\textunderscore AI ya dispone de un algoritmo A^* programado en él y no pensamos que el objetivo de la práctica sea poner a prueba nuestra capacidad para programar el algoritmo de búsqueda (teniendo en cuenta que fue uno de los trabajos realizados en la asignatura previa, Inteligencia Arficial), hemos decidido copiar la implementación realizada en nuestro paquete y realizar modificaciónes sobre ella. Modificaciones realizadas:

• En el método de generación de vecinos en pathfinder.java, se han añadido las siguientes consideraciones (siempre que el modo secure_mode este activado): una casilla bajo una roca no es transitable, hemos de tener en cuenta que aunque no sea transitable si es alcanzable, una gema bajo una piedra se puede coger desde alrededor, esto también se ha implementado. El resultado que tiene esto en el avatar es que los caminos que coge no intentan pasar por debajo de piedras salvo que la parte reactiva le diga lo contrario. De esta forma se evitan movimientos de piedras innecesarios y que podrían resultar en que el avatar quedara encerrado.
• También se ha añadido a la clave pathfinding un vector de nodos, este es usado para añadir posiciones que no queramos que sean transitables.
• Otro vector de nodos similar se ha añadido a AStar, llamado high_ heuristic_ value, en el que podemos insertar posiciones que queramos que sean evitadas, salvo que sea estrictamente necesario pasar por ellas. En este vector insertamos todas las inmediaciones de donde se encuentras los monstruos, de forma que uno nunca será liberado salvo que sea imposible ganar el mapa sin hacerlo.
• El comportamiento normal de este conjunto de clases se basa en precalcular todos los caminos en la inicialización y luego utilizarlos en cada iteración. Como este juego está sujeto a cambios constantes (piedras y monstruos), hemos decidido no utilizar esta implementación y llamar directamente al A^* en cada iteración.
• En la heurística de AStar.java se ha realizado un cambio, ya que esta no tenia en cuenta el coste de movimiento que implica realizar un giro.

\newpage

El comportamiento reactivo del avatar está basado en 3 grandes comprobaciones que se realizan en cada iteración.

Esta comprobación se realiza en el método monsterNearby dentro de Agent.java, su objetivo es comprobar si la posición a la que se pretende avanzar presenta algún riesgo debido a presencia de monstruos. Supongamos que el avatar es A y quiere avanzar a la casilla V, el método comprueba todas las casillas numeradas.

La primera comprobación es que en las casillas 2, 5, I, 6, 8 y 9 no existe un monstruo, en caso de haberlo la posición I no es segura, ya que en un solo movimiento podría matarnos el enemigo.

Las siguientes comprobaciones se hacen teniendo en cuenta que los monstruos no necesitan realizar giros y que su movimiento se hace antes que el del avatar. Miramos que las posiciones 1 y 3 no sean un monstruo, en caso de serlo, estas posiciones suponen un problema solo en las siguientes ocasiones:

• La posicion 1 será peligrosa si y solo si las casillas 2 o 5 se encuentran vacías, en caso de estar ocupadas la posición no es peligrosa.
• La posicion 3 será peligrosa si y solo si las casillas 2 o 6 se encuentran vacías, en caso de estar ocupadas la posición no es peligrosa.

Ahora se comprueban las casillas 0, 4 y 7, que serán peligrosas si y solo si las casillas 2, 5, y 6 respectivamente están vacías.

Este método simula que se realiza la acción que se quiere devolver, utilizando la herramienta que dispone GVG\textunderscore AI para ello, este método no es efectivo contra los monstruos ya que su movimiento es aleatorio y en la simulación pueden realizar un movimiento distinto al realizado después.

Este método se preocupa de comprobar si en la casilla a la que se quiere ir existe el riesgo de que vaya a caer una piedra.

En caso de que cualquiera de los métodos anteriores devuelva que la acción es peligrosa, el avatar entra en modo escape, donde llamará a escape_from _current_position, un método encargado de devolver la acción que salvará al avatar. Para ello se cogen todas las acciones posibles que se pueden realizar y se hacen las 3 mismas comprobaciones sobre ellas hasta dar con una posición segura. En caso de no encontrarse, se devolverá la acción contraria a la realizada la última vez (con la idea de volver a la posición anterior).

La finalidad de este estado es utilizarlo cuando el pathfinder, no sea capaz de devolver un camino. En este estado el avatar coge la posición que más le acerque a su destino de entre sus vecinos. Intentando no volver atrás salvo que sea necesario. En la práctica este estado solo se utiliza cuando el avatar se ha quedado encerrado y la única forma de salir es mover ciertas piedras, aunque no asegura que de existir una forma de salir la vaya a encontrar.