Algoritmos desarrollas en BpGame:

Backtracking

Es una técnica algorítmica para resolver problemas de forma recursiva al tratar de construir una solución de forma incremental, una pieza a la vez, eliminando aquellas soluciones que no satisfacen las restricciones del problema en cualquier momento.

Dentro de BPGame se implementa para la resolución de la ruta mas corta entre la bola y la cancha del jugador, donde se procesa una matriz binaria, un punto de inicio y punto de destino. En el caso de la matriz binaria, los ceros simbolizan obstáculos y los unos espacios disponibles, por lo que el backtracking toma en cuenta las celdas adyacentes del punto de inicio para ir paso a paso encontrando el camino y eliminando de la ruta los finales los espacios que no satisfacen las condiciones.

Pathfinding A*

El algoritmo Pathfinding es un algoritmo de tipo búsqueda muy utilizado para encontrar la ruta más corta, una de sus variantes es el Pathfinding A* que el mismo es similar al algoritmo Dijkstra pero A* utiliza una heurística para estimar la probabilidad de que cada nodo esté cerca de la meta, con el fin de tomar la mejor decisión. El Pathfinding A* es un algoritmo muy utilizado en videojuegos debido a que es preciso, rápido y eficiente, aunque sacrifique encontrar la mejor opción por una cercana a ella.

En BPGame este algoritmo es utilizado para mostrar al jugador 1 la ruta más corta para anotar un gol, para ello se divide en campo en un matriz que contiene los obstáculos, el balón y la meta que en este caso sería la meta. Se utiliza tres variables f, g y h.

Donde g es el costo del movimiento vertical (10) o horizontal (14), h es coste el coste de movimiento estimado para pasar del cuadrado donde se encuentra el balón a la meta , y f es la suma de las anteriores. Además se crean dos lista una lista abierta donde se almacena el nodo de partida y los nodos vecinos de esto y otra cerrada donde se va almacenando los nodos más óptimos que se deben seguir para llegar a la meta.

setPlayers

Este algoritmo recibe un numero entero de cuantos obstáculos se quieren distribuir por el tablero, entonces seguidamente crea las posiciones aleatorias de cada uno de los objetos y ademas agrega a la matriz binaria el lugar donde se encuentra cada uno de los objetos creados.

setBacktracking

Encargado de iniciar la matriz binaria con todos los elementos disponibles para agregar objetos.

Collision

Collision es una clase que contiene una serie de algoritmos encargados de detectar cuando un Sprite toca otro, esta clase es una adaptación de un tutorial de internet de Sonar Systems (https://www.youtube.com/watch?v=g5hFOANHjlQ) el cuál fue de mucha ayuda para realizar las colisiones de los bordes, goles y colisiones con obstáculos.

Algoritmos desarrollas en Genetic Puzzle:

Genetic Algorithm

El algoritmo genetico es un tipo de algoritmo que simula la selección natural. En este se crea un algoritmo que va creando soluciones y clasificándolas respecto a que tan buenas soluciones son. Cada grupo de soluciones es una generación, y cada generación dependerá de la información de la generacion anterior. Cada Solucion en una generacion es conocida como individuo y la representacion de sus genes dentro de los sistemas informaticos se da por medio de bit, donde cada bit representa la aparicion de un gen especifico.

Creacion de genes (Filas)

Dentro de Genetic Puzzle los individuos representan las posibles soluciones que tiene el ordenamiento. El ordenamiento de las sub imagenes se realizara por filas, por lo que cada Individuo tendra una cantidad de genes equivalente a la cantidad de filas en las que se dividio la imagen y cada gen sera compuesto por una representacion de filas*columnas, donde se pondran con un 1, representando que esta presente esa sub imagen en esa fila hasta un maximo segun la cantidad de columnas en que se subidividio la imagen.

La creacion de Filas se ejemplefica en la siguiente imagen:

https://github.com/LuisDiego1010/Proyecto_II_DII_Lets_Play-/blob/main/Wiki/Creacion%20aleatoria%20de%20una%20fila.png

En esta se crea un gen aleatorio. Para ello se detecta si donde quiere ubicar un 1 se halla un cero y se ubica por medio de operaciones de bit wise.

Creacion de un individuo

El proceso de creacion de Filas se repite para todas las filas del individuo con expecion de la ultima. La ultima fila de todos los individuos tiene solo una posibilidad de exisitr sin que repita una subimagen ya que todas las otras posiciones en el genoma ya han sido tomadas.

Esto se realiza por medio de un complemento. como ejemplo podemos considerar el algoritmo tal que:

https://github.com/LuisDiego1010/Proyecto_II_DII_Lets_Play-/blob/main/Wiki/Creacion%20de%20un%20individuo.png

En este codigo se crean todas las filas de un individuo de la primera generacion, por lo que es posible que se repitan genes en algunas filas. El lado del cliente tiene una correcion para que aunque se presenten repeticiones del gen se consideren la ultima representacion.

Para la creacion de la fila final se hace la creacion de una fila por herencia de una doble inversion del genotypo, lo que significa que la fila final adquerira los genes de los padres, los cuales además tienen los genes que le hacen falta al individuo.

Creacion de una Generacion.

La creacion de una generacion se da por tres procesos. La creacion aleatoria, que se realiza en la primera generacion. la creacion por herencia y la creacion vacia, que es utilizada por otros metodos como place holders.

Las primeras dos creaciones son las que son utilizadas directamente en la determinacion del algoritmo genetico.

https://github.com/LuisDiego1010/Proyecto_II_DII_Lets_Play-/blob/main/Wiki/Creacion%20de%20Generaciones.png

En esta implementeacion la creacion de Nuevas generaciones se realiza eliguiendo dos individuos para crear un nuevo individuo que se guarda en un objeto de generacion. En la creacion de nuevos Individuo se eligue la primera fila de ambos Individuos progenitores y apartir de ello se crea una nueva fila.

Normalmente la implementacion de esto se realiza haciendo uso los individuos con mejores fitnes, pero en esta implementeacion, al ser imposible indentificar el caso correcto, o al haber una posibilidad de tener varias soluciones correctas se decidio utilizar cualquier individuo de tal forma que conforme avancen las generaciones el promedio del fitness se reduzca generando así mayor cantidad de soluciones con alta posibilidad, envez de centrarse en busca exactamente la mejor posibilidad. Aunque para algunos metodos como la mutacion si se hace uso de las mejores soluciones disponibles para hacer avanzar los fitnes en la direccion correcta.

Creacion de FIlas por herencias

La creacion de Filas por herencia se da apartir de las mismas filas de progenitores, independientemente del gen que tengan. Estas filas se van uniendo de tal forma que crean un gen nuevo, pero que maniene caracteristicas de los anteriores. Para ello se implemente el siguiente codigo.

https://github.com/LuisDiego1010/Proyecto_II_DII_Lets_Play-/blob/main/Wiki/Creacion%20por%20herencia%20de%20una%20fila.png

En este se toma n/2 cantidad de unos (gen activo) presentes en la fila madre y se aplica al gen del nuevo individuo. Lo mismo sucede con el gen de padre, nada más que de este se toma la cantidad de unos desde n/2 hasta n, de tal forma que los primeros n/2 genes son dados por la madre, y los restantes por el padre.

Calculo de fitness

Para el calculo del fitnes con el que despues se clasificaran los genes se hace uso de la informacion que fue recolectada en el cliente. En esta implementacion se decidio hacer el calculo del fitness por columna de tal forma que sumando el fitnes de las columnas se consigue el fitnes del individuo. El calculo del fitnes por columna se hace identificando el fitnes de cada elemento segun su posicion en la columa y en la fila y obteniendo la diferencia de sus valores RGB con los valores totales que deberia de haber en la fila.

https://github.com/LuisDiego1010/Proyecto_II_DII_Lets_Play-/blob/main/Wiki/Calculo%20de%20fitness.png

Tomando como ejemplo el algoritmo con el que se calcula para esta implementacion: el RFit es el fit que le corresponde 1 de la fila segun la posicion que tenga en el genoma. Para este caso considerando que si dos subimagenes son iguales estas pueden intercambiar posiciones y seguir, visualmente, siendo una solucion pero por posicion no es la imagen original, por ello la funcion de determinacion de fitnes no llegara a ser 0, para asi lograr llegar a varias resultados que pueden o no ser validos.

Calculo de mutacion e inversion.