Práctica 2
Resumen
En la práctica dos presentamos un tablero de compuesto por cien casillas (normal, embarrada, bloqueada) en una matriz de 10x10. En este tablero se colocan aleatoriamente tres unidades, tres fichas, que serán el sitio donde comenzarán a moverse para llegar al destino definido por el jugador. Este destino se define haciendo clic en una casilla no bloqueada después de seleccionar la ficha que quiere mover.
Problema a resolver
El problema a resolver es encontrar el camino más óptimo para que cada ficha llegue a su destino. A nivel de programación el problema es utilizar un algoritmo que encuentre el camino con menor coste entre un nodo origen y otro destino. Este algoritmo que buscamos es el A* o Astar.
Método de resolución
A*
Nuestro A * o algoritmo de búsqueda resuelve problemas buscando entre todas las rutas posibles y de entre estos caminos primero considera los que parecen conducir más rápidamente a la solución. A partir de un nodo específico de una matriz de nodos construye un árbol de rutas, expandiendo las rutas un paso a la vez, hasta que una de sus rutas termina encontrando el nodo objetivo.
En cada iteración de su bucle principal, el algoritmo determina cuál de sus rutas se expandirá. Esto lo hace con la selección del nodo con la menor estimación del coste, calculada con la función:
f (n) = g (n) + h (n)
Donde n es el nodo del que se está calculando el coste, g (n) es el coste de la ruta desde el nodo de inicio a n, y h (n) es una heurística que estima el coste de la ruta más barata desde n hasta el objetivo.
Usamos una cola de prioridad (open) para almacenar los nodos con los que se está trabajando y realizar la selección de nodos de coste mínimo. En cada paso del algoritmo, el nodo con el valor f (x) más bajo se elimina de la cola, sus vecinos que no estén en la cola se añaden y a los que ya estén les actualiza sus valores f y g. El algoritmo continúa hasta que un nodo al añadir un vecino encuentre la posición final o hasta que se vacíe la cola (lo que indicaría que no existe solución).
Para encontrar la secuencia real de pasos, cada nodo almacena su predecesor. Esto permite que después de ejecutar el algoritmo, el nodo final apuntará a su predecesor, y así sucesivamente, hasta que el predecesor de algún nodo sea el nodo de inicio.
Herramientas utilizadas
Implementación
- Ficha: componente de cada ficha de la matriz
- Vector2 positionInMatrix: posición lógica de la ficha dentro de la matriz.
- OnMouseDown(): comprueba el clic en la ficha y llama a SetFichaSeleccionada(), una función del GameManager.
- SetPositionInMatrix(): setter de positionInMatrix.
- GetPositionInMatrix(): getter de positionInMatrix.
- Casilla: componente de cada casilla de la matriz
- Vector2 positionInMatrix: posición lógica de la ficha dentro de la matriz.
- OnMouseDown(): comprueba el clic en la casilla y llama a OnClick(), una función del GameManager.
-
GameManager: gestiona y realiza los movimientos de la matriz y lee el input de teclado:
-
Atributos:
- public enum tipoCasilla: Controla lo que hay en un cuadrado del tablero. Si hay solo una casilla, el tipo de esta, si no, indica que hay una ficha.
- tipoCasilla [,] tablero: Matriz con los tipos de casillas.
- Atributos que necesita la IA:
- int [,] tablero01: Matriz de enteros, solo 0 y 1, que simbolizan casillas disponibles y no disponibles para pasar, respectivamente.
- Vector2 posicionInicial: Coordenadas de la ficha que vamos a mover.
- Vector2 posicionFinal: Coordenadas del destino de la ficha que queremos mover.
- public GameObject Casilla: Prefab de cualquier casilla del tablero
- public Sprite ******* Son los sprites que representan el tipo de casilla (normal, embarrada, bloqueada).
- public GameObject ******* Los gameObjects de las tres fichas y de las tres cruces.
- GameObject ******* Estos gameObjects son los que controlan la ficha que queremos mover y a donde.
- Start(): Llama a CreaFichas() y a CreaTablero()
- Update(): De momento solo debug.
- SetFichaSeleccionada(): Se encarga de cambiar la ficha seleccionada, tanto a nivel lógico como a nivel visual.
- OnClick(): Cambia las casillas de tipo y señala la casilla destino en caso de que el anterior click hubiera sido una ficha.
- Creafichas(): Coloca las fichas en un sitio aleatorio del tablero
- CreaTablero(): Rellena tablero de casillas colocando un numero de casillas embarradas y bloqueadas delimitado. Estas casillas tienen una posición aleatoria.
-
Atributos:
-
Astar1: Componente poseedor del algoritmo de búsqueda.
- Node[,]tableroNode: Guarda la matriz de nodos.
- bool [,] marked:Marca las casillas que ya no se tienen que comprobar.
- FastPriorityQueue <Node> open: Almacena los nodos abiertos (que se están procesnado).
- int[,] tablero: Recibe y guarda los tipos de casilla.
-
Class Node: Nodo del tablero.
- Enum state: marcan el estado de del nodo.
- public Vector2 pos:coordenadas del nodo.
- Int h: distancia desde el nodo hasta el nodo objetivo.
- Int cost:el coste que tiene pasar por ella.
- Int g:coste para llegas a ese nodo.
- Int f:h + g.
- public Node Padre: Representa el nodo padre al actual.
- public Node(): Constructora donde se inicializan los atributos anteriores
- List <Vector2> calculatePath() heurística que calcula el coste de la ruta más barata desde un nodo hasta otro.
- int ManhattanDistance(): heurística que calcula el coste de la ruta más barata desde un nodo hasta otro.
- Node addNeighbours(): añade vecinos a open y devuelve el nodo solución si lo encuentra.
- fillMarked(): Rellena la matriz marked.
- void fillTableroNode():rellena la matriz tableroNode.
- List
getPath(): devuelve la lista de posiciones del recorrido a partir del nodo final.
Resultados obtenidos
- Objetivos completados
- Objetivos incompletados
- Dificultades
Todo lo relacionado con Unity en la práctica que se utiliza antes de llamar al algoritmo funciona de una manera correcta y eficiente. La implementación de A* utilizada funciona de una manera eficaz.
Cuando la ficha llega a su objetivo, si se vuelve a clicar, aparece en la posición en la que se instanció en el tablero. Creemos que es por un problema de copiar el transform de los gameObjects, pero no hemos conseguido corregirlo por el momento.
La mayor parte de las dificultades las hemos encontrado en el GameManager. A la hora de controlar el click en los gameObjects 2D, los colliders de los objetos están a la misma altura, se solapan. La solución ha sido desactivar el componente BoxCollider2D en las casillas donde estén las fichas. Cuando se mueva la ficha esa casilla volverá a tener el componente activo.
Otro inconveniente fue el control de la ficha seleccionada y de seleccionar posteriormente la casilla destino, donde aparecería una cruz del color de la ficha. Además, hemos llegado a implementar tres versiones de A* para llegar a la óptima para nuestra práctica.
Relación bibliográfica
https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*
http://buildnewgames.com/astar
www.youtube.com/channel/UCJdQxmnPls4rIwxCHS1szTQ
https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp