Este apartado del Anexo lo dividiremos en dos partes: la primera sobre la implementación del algoritmo A* y la segunda parte la implementación de los métodos auxiliares que nos faltó por desarrollar en el capítulo 6.
6.1. Implementación del algoritmo A*.
El algoritmo A* es un algoritmo de búsqueda o “pathfinding« que se utiliza para calcular los caminos mínimos en una red. Es un algoritmo heurístico ya que utiliza una función heurística para calcular el camino más óptimo entre dos nodos.
Este algoritmo es fácil de implementar pero requiere de un elevado coste computacional. En nuestro caso al tratarse de escenarios (matrices) relativamente pequeños, ese coste es inapreciable con el hardware actual, sin embargo la complejidad será exponencial con respecto al espacio requerido para realizar la búsqueda por lo que en juegos con escenarios muy grandes y complejos, es recomendable buscar otras alternativas como la navegación por NavMesh que incluye Unity3d. A continuación detallamos la implementación en C# para Unity3d.
Figura 6.1. Implementación de la clase NodoAStar
Lo primero es crear la clase “NodoAStar” (Figura 6.1) que contendrá la función de evaluación de un nodo en concreto. En nuestra matriz todos los nodos tendrán el mismo coste (0) y los nodos donde existan otros objetos (tierra, piedras, diamantes) no serán transitables (isTransitable = false). Tendrá métodos para calcular las funciones F, G y H.
Figura 6.2. Implementación de la clase Deap.
La clase “Deap” o “monticulo” de la Figura 6.2 representa una lista de nodos. La utilizaremos para guardar la lista de nodos descartados, la de nodos disponibles y la lista final con el camino más óptimo.
Figura 6.3. Implementación de la clase Astar.
Por último implementamos la clase “Astar” que contendrá el algoritmo A*. Como se puede ver en la Figura 6.3, esta clase recibirá la matriz de nodos, el nodo inicial, el nodo final y un booleano para indicarle si utilizaremos las diagonales. En nuestro juego no nos podemos mover diagonalmente por lo que este parámetro será falso.
Figura 6.4. Primera parte de la función que calcula el camino más óptimo.
Para calcular el camino más óptimo (Figura 6.4), lo primero es tener una lista con los nodos disponibles (“listOpen”) y otra lista con los nodos descartados (“listClose”). Mientras queden nodos disponibles y no se haya encontrado el camino, extraeremos nodos de la primera lista.
Figura 6.5. Segunda parte de la función que calcula el camino más óptimo.
En la segunda parte del algoritmo (Figura 6.5), del nodo actual que hemos extraído de “listOpen”, extraemos sus nodos adyacentes y los insertamos en otra lista a parte.
Figura 6.6. Tercera parte de la función que calcula el camino más óptimo.
Lo siguiente (Figura 6.6) será comprobar si cada nodo adyacente está en la lista abierta y en caso contrario, insertarlo en ella enlazándolo con su nodo padre. En caso de que esté en la lista cerrada, comprobaremos si su valor G es menor que el nodo actual y en ese caso lo volvemos a añadir a la lista abierta.
Figura 6.7. Cuarta parte de la función que calcula el camino más óptimo.
Una vez encontrado el camino (Figura 6.7), hacemos “backtracking” desde los nodos padre para devolver el camino más óptimo.
Figura 6.8. Creación de la matriz e instanciación de la clase Astar.
Por último en la figura 6.8 se muestra la forma en la que se crea la matriz de nodos que será utilizada por la clase “Astar” para calcular el camino más óptimo.
6.2. Métodos auxiliares utilizados en la inteligencia artificial de los enemigos.
Figura 6.9. Función selectStateFromNoSmart
La función de la Figura 6.9 es utilizada para devolver el estado más próximo del estado que se le pasa por parámetro. Comprobamos primero el estado actual para que siga en la misma dirección. Esta función es utilizada cuando el enemigo no es inteligente.
Figura 6.10. Función moveFromState
La función “moveFromState” (Figura 6.10) es similar a la función del personaje para moverse en el estado actual. Al igual que con el personaje, volteamos horizontalmente la imagen del enemigo según la dirección.
Figura 6.11. Función getStateFromPosition
En la función de la Figura 6.11 le pasamos el nodo y en función del estado actual calculamos el estado al que debe moverse.