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.
Para profundizar en la inteligencia artificial (IA) de los enemigos en un juego, es fundamental entender los conceptos clave y adoptar estrategias efectivas:
1. Entendimiento del Comportamiento Deseado:
- Define claramente el comportamiento que deseas para tus enemigos. ¿Deben atacar al jugador, esquivar obstáculos, trabajar en grupo, etc.?
2. Sistemas de Comportamiento:
- Implementa sistemas de comportamiento basados en estados o máquinas de estados finitos. Define estados como «Buscar al Jugador», «Atacar», «Esquivar», etc.
3. Sensores y Percepción:
- Da a tus enemigos la capacidad de percibir su entorno y al jugador. Utiliza sensores para detectar la presencia del jugador, obstáculos, u otros enemigos.
4. Algoritmos de Pathfinding:
- Implementa algoritmos de pathfinding (por ejemplo, A* o navegación de Unity) para que los enemigos puedan planificar rutas eficientes hacia el jugador o a ubicaciones estratégicas.
5. Sistemas de Toma de Decisiones:
- Crea sistemas de toma de decisiones que permitan a los enemigos elegir acciones en función de su estado actual y de la información percibida.
- Utiliza técnicas como árboles de comportamiento o algoritmos de toma de decisiones.
6. Inteligencia Colectiva (Opcional):
- Si tienes múltiples enemigos, considera la inteligencia colectiva. Permite que los enemigos colaboren, se comuniquen y tomen decisiones en grupo.
7. Aprendizaje de Máquina (Opcional):
- Explora técnicas de aprendizaje de máquina para mejorar la adaptabilidad de la IA. Por ejemplo, podrías implementar un algoritmo de aprendizaje por refuerzo para ajustar el comportamiento de los enemigos a lo largo del tiempo.
8. Reacción a Eventos del Juego:
- Haz que la IA reaccione a eventos del juego, como la muerte de otros enemigos, cambios en la situación o la aparición de nuevos obstáculos.
9. Optimización del Rendimiento:
- Optimiza el rendimiento de la IA para que no afecte negativamente el rendimiento general del juego. Usa técnicas como el culling o la limitación de la frecuencia de actualización.
10. Pruebas y Ajustes:
- Realiza pruebas exhaustivas para asegurarte de que la IA se comporte según lo esperado.
- Ajusta parámetros y lógica según el feedback obtenido durante las pruebas.
11. Simulación y Debugging:
- Implementa herramientas de simulación y debugging para comprender mejor el comportamiento de la IA y facilitar la identificación de problemas.
12. Escalabilidad:
- Diseña la IA con la escalabilidad en mente. Debería ser fácil agregar nuevos comportamientos o ajustar parámetros sin afectar negativamente la estabilidad del sistema.
13. Documentación:
- Documenta la lógica de la IA para futuras referencias y colaboración. Esto es especialmente útil si trabajas en equipo.
14. Iteración:
- Realiza iteraciones en la IA a medida que evoluciona tu juego. La mejora continua es esencial para adaptarse a las necesidades cambiantes del diseño del juego.