Repository navigation
5) Algoritmos desarrollados
Para el desarrollo del juego fue necesario implementar 5 algoritmos para los movimientos, evolución y vista de los enemigos. De los 5 algoritmos solo el algoritmo genético no trabaja usando la matriz, los demás algoritmos usan 5 diferentes matrices ya que cada una corresponde a cada nivel del juego, en el cual el 0 corresponde a las rutas y 1 corresponde a los muros.
Este algoritmo se encarga de crear una vista lineal al chuchu, en el cual tendrá 6 distintas direcciones que se escogen al azar, en el cual la vista tiene un limite de tamaño en el cual solo puede abarcar 5 posiciones dentro de la matriz o ya sea el caso en el que encuentre un muro en su vista.
Al algoritmo se le debe pasar la matriz del nivel, las coordenadas de la posición del chuchu, después se genera al azar hacia cual dirección debe ir dirigida la vista del chuchu.
Despues de analizar hacia cual dirección debe ser la vista se analiza si la siguiente celda de la matriz es un 0 y que no se pase de los limites de la matriz, si estas condiciones se cumplen la vista del chuchu aumentará en linea recta hasta que algunas de estas dos condiciones sean cumplidas, ya sea que el limite de la vista llegue a 4 o se encuentre un muro o margen de la matriz.
Este algoritmo crea una población inicial para los espectros, debido a que por cada nivel hay un máximo de 3 espectros la población inicial será de 3, cada espectro tendra 4 genes los cuales surgen al azar.
Para el inicio de cada nivel se da una selección de los individuos para el cruce, en este caso ya que la poblacion es de 3 individuos se escogen dos para el cruce y el otro se elimina para ingresar al nuevo, para cada uno se calcula el fitness sumando los valores de cada gen y los dos con el mejor fitness son elegidos para el cruce.
En el cruce se toma al azar cuantos genes va a heredar el hijo del padre y la madre, tambien al azar se toma si tendra mutacion o no y se ingresará al individuo en la nueva población.
El algoritmo de backtracking es un algoritmo de programación de búsqueda a través de todas las posibles soluciones, en la solución del proyecto fue utilizado para que los espectros se devuelvan a sus respectivas rutas de patrullaje, esto se hace mediante una matriz donde el 2, 3 y 4 representan cada una de las rutas de los distintos espectros.
Primero comprueba que aun no ha llegado a la ruta de patrullaje y de que no haya muros, si estas dos condiciones no se cumplen continua avanzando.
El algoritmo almacena en una lista las posiciones en (x,y) por donde ya ha pasado para así evitar pasar por las mismas rutas anteriores.
Vuelve a comprobar los muros y los bordes del mapa, ademas comprueba que la ruta no sea repetida, si todo es correcto desmarca todas las marcas realizadas en este paso debido a que no hubo problemas.
El algoritmo de A* es un algoritmo de pathfinding, siendo este uno de los más eficaces en la actualidad. Dicho algoritmo busca aproximar cuales son los puntos más prometedores para explorar mediante el uso de una heúristica ideal, que toma en cuenta el valor mínimo conocido para llegar a un punto y algún valor mínimo teórico para llegar hasta el punto final.
El primer paso corresponde a agregar el primer nodo a una lista de nodos abiertos
Mientras que la lista de nodos abiertos no sea nula se realiza lo siguiente:
Se encuentra el nodo con la mejor heurística en la lista de nodos abierto:
Se agrega dicho nodo a la lista de nodos cerrados, y se elimina de la lista de nodos abiertos:
Se busca en el vecindario del este mismo nodo, y se agregan a la lista de nodos abiertos los que no estén en ninguna de las listas
Se evalúa la distancia del nodo actual al objetivo, y si son vecinos se guarda el camino que se ha seguido en una lista y el método termina su ejecución.
El algoritmo de Breadcumbing es un algoritmo de pathfinding usualmente usado en juegos. Su traducción a español corresponde a algo similar a ¨Seguir migajas¨, bajo la idea de que el jugador va dejando migajas que los espectros siguen. Por lo cual, el algoritmo consiste en guardar los puntos visitados por el jugador y su orden, para que los enemigos sigan este camino y lo persigan.
El algoritmo se ejecuta de la siguiente manera, tomando en cuenta que el jugador actualiza su historial de posiciones en una lista:
- Se analiza si la posición actual del espectro ha sido visitada por el jugador, en caso de que sea así se actualiza el valor de la última posición alcanzada por el espectro:
- Luego, se le asigna la siguiente posición en la que estuvo el jugador al espectro, si el espectro está en la última posición se mantiene igual:
