Práctica 3
Resumen
En la práctica tres presentamos un tablero compuesto por cincuenta casillas (normal, embarrada, bloqueada, comisaría, sangre, cadáver, cuchillo...) en una matriz de 10x5. El tablero comienza con todas las casillas en "modo" normal. Colocamos la comisaría en una casilla aleatoria. Damos la opción al jugador de colocar el cuerpo en una casilla. Después puede colocar cuantos agujeros quiera. Por último, comenzarían a trabajar los algoritmos para resolver el problema.
Problemas a resolver
Búsqueda del cadáver y el cuchillo
El problema a resolver consiste en la exploración de las casillas necesarias para llegar al cadáver y al cuchillo de la manera más conservadora y segura posible. Esto conlleva a evitar exploraciones arriesgadas en las que el policía deba "saltar al vacío", pudiendo llegar a perder. Algunas configuraciones muy problemáticas serían las siguientes:
La siguiente, sería la configuración más difícil de resolver:
Vuelta a casa
Sería un problema parecido al de la anterior práctica. Utilizamos A* sobre las casillas ya exploradas para la vuelta a casa. Siempre buscamos el camino que menos casillas recorra.
Métodos de resolución
Búsqueda por BFS
En esta algoritmo desechamos las casillas por las que seguro no vamos a pasar y marcamos las que conocemos seguro aunque no hayamos pasado. Algunos ejemplos visuales sobre las anteriores configuraciones (Hechas hasta que haya que arriesgarse).
Como se pueden observar en las anteriores anotaciones, hicimos nuestras propias formas de optimizar el algoritmo. Sin embargo, estamos equivocados. No siempre que tengamos tres posiciones embarradas colindantes podremos asegurar que hay agujero en el centro de las mismas. Por lo tanto habría que explorar otro camino o, si no hay más opciones arriesgar.
Este comportamiento se asemeja un poco al de una persona real. No sabremos que hay en esa casilla hasta explorarlo.
Cuando el vigilante llega al cuchillo y al cadaver, el tablero quedaría de la siguiente forma:
A*
Utilizamos la misma implementación que en la anterior práctica. Esta vez sí funciona correctamente, no hay distinciones de costes de casillas por lo que no hay problemas al atravesar barro. Si el vigilante ha cogido el cuchillo y tiene la posición del cadáver, hay un camino seguro de vuelta.
Herramientas utilizadas
Implementación
- GameManager: componente que controla todos los aspectos visuales
- CreaTablero(): Se encarga de crear un tablero con todas las fichas normales.
- PonComisaria(): Invoca una comisaria en una casilla aleatoria.
- destapaCasilla(): Cuando el vigilante da el siguiente paso, destapa la casilla para saber qué es.
- TapaTablero(): Prepara el tablero para cuando el vigilante comience a patrullar.
- OnButton****Click(): Administran las funciones de los botones de la escena.
- ColocarCuchillo(): Coloca un cuchillo según las especificaciones alrededor del cadáver.
- OnClick(): Según se haya pulsado un botón u otro te permite colocar el cadáver o los agujeros.
- DetectiveSearch: componente que controla la búsqueda del cadáver y del cuchillo.
- Se encarga de administrar de manera conservadora, las casillas que tiene que explorar el detective para llegar a su meta. Busca una dirección por la que seguir su camino, valora el tipo y dependiendo del mismo, se comporta de una manera u otra. Si para seguir avanzando no queda otra opción que arriesgar, lo hace, si continúa con vida, sigue el mismo proceso que antes. Cuando el detective encuentra el cuchillo o el cadáver, deduce dónde podría estar el elemento restante. Cuando tiene los dos, volvería a casa por el camino más corto de entre las casillas exploradas.
Resultados obtenidos
- Objetivos completados
- Objetivos incompletados
- Dificultades
Las funciones visuales de la práctica van a la perfección, cosa que hemos mejorado respecto a lo anterior. El A* funciona correctamente, ya que al no tener costes según el tipo de casilla, encuentra siempre el camino más corto de vuelta a la comisaría.
Puede que haya algún caso de prueba sin contemplar ya que puede haber muchas configuraciones difíciles de tratar o que las hemos pasado por alto.
Hay configuraciones que seguramente den fallos, ya que cada vez que se nos ocurría una distribución de agujeros nueva y peculiar, era objeto de darnos problema debido a la interpretación de agujero o casilla segura.