Fundamentos de Programación | TP3 * Flood

TP3: Flood

Para el tercer y último trabajo práctico, se pide completar la funcionalidad de un código para el juego Flood, puntualmente la versión disponible en la colección de Simon Tatham.

Consiste en un tablero de colores, donde el "flood" será el color correspondiente a la esquina de arriba a la izquierda. El jugador podrá seleccionar un cambio de color al "flood", tomando una mayor área. El objetivo es convertir todo el tablero del mismo color.

Gameplay

Parte 0 - Archivos base

El siguiente trabajo práctico se encuentra dividido por partes, agregando funcionalidad en cada una. No es necesario leer todo el enunciado para comenzar a desarrollar, pero es importante que cada parte esté funcionando sin errores antes de seguir con la siguiente. Se provee el siguiente código base:

flood.zip

El empaquetado contiene:

  • El programa principal main.py con la interfaz gráfica ya implementada.
  • Implementaciones de los TDAs pila.py, cola.py. Incluyen métodos __str__ para facilitar el desarrollo y depuración.
  • Una biblioteca de funciones gamelib.py que facilita la interfaz del programa. Para el trabajo práctico no será necesario aprender las funciones de gamelib, pero si te interesa saber más, acá está la página de la biblioteca.
  • Los archivos a modificar durante el trabajo flood.py y juegoflood.py.
    • Los métodos a completar se encuentran documentados. La funcionalidad a agregar no debe romper los contratos de las mismas (tipos de datos en los retornos, responsabilidad, cantidad de parámetros, etc).

Antes de empezar el desarrollo del trabajo práctico, primero debemos asegurar que lo descargado funciona sin problemas.

Ejecutar el programa main.py. Debería observarse una ventana gris con algunos botones, y en la terminal el mensaje "No se implementaron todos los métodos de la Parte 1".

Si ese no fue el resultado y el programa cerró con alguna otra excepción significa que el componente gráfico no está funcionando correctamente en el sistema. Algunos errores comunes son los siguientes:

  • Gamelib (la biblioteca usada en el TP3) no suele funcionar correctamente con Windows para Linux (WSL) debido al componente gráfico que requiere. Si estás usando WSL, utilizá la línea de comandos tradicional de Windows junto con la instalación de Python normal.
  • Es posible que tkinter, necesario para el funcionamiento de Gamelib, no esté instalado. Intentá instalarlo para tu sistema operativo correspondiente.
  • Si ya intentaste con los items de arriba y el programa sigue sin abrir correctamente, preguntá por el canal del trabajo práctico en Discord.

Parte 1 - Esqueleto y estructura del juego

El objetivo de esta primer parte será completar los primeros cinco métodos de la clase Flood, el cuál manejará un tablero de colores.

La clase Flood deberá administrar un tablero de colores, donde recomendamos que la misma esté representada como una lista de listas de enteros. Entonces, por ejemplo, un tablero de 4x4 que fue mezclado con 3 colores podría tener este estilo:

[[0, 0, 1, 0],
 [1, 0, 2, 2],
 [2, 1, 0, 2],
 [1, 2, 2, 2]]

Para esta parte se pide desarrollar los siguientes métodos para la clase Flood dentro del del archivo flood.py:

  • Flood.__init__: inicializa el tablero para las dimensiones especificadas, con un solo color para todo el tablero.
  • Flood.mezclar_tablero: modifica el tablero para que, de forma completamente aleatoria, tenga n_colores a lo largo del mismo.
  • Flood.obtener_color: devuelve el color que se encuentra en las coordenadas solicitadas.
  • Flood.dimensiones: devuelve las dimensiones del juego en una tupla, indicando el alto y el ancho en ese orden.
  • Flood.obtener_posibles_colores: devuelve un iterable ordenado (como por ejemplo una lista) de todos los colores que fueron utilizados para generar el juego. Por ejemplo, si los colores toman valores numéricos, la función debe devolver una lista con [0, 1, ..., n_colores - 1].

Los atributos y estructuras de la clase Flood necesarias para llevar adelante estas cuatro funciones quedan a criterio propio. Se recomienda guardar al menos el tablero en sí y la cantidad de colores con la cuál se mezcló el tablero.

Al finalizar esta parte, se podrá ejecutar el programa, el cuál debería mostrar un tablero de 5 colores mezclado. Debería generarse uno diferente al clickear el botón Nuevo.

Con el juego inicializado, ahora se pueden modificar las constantes del main.py para controlar las dimensiones, la cantidad de colores y otros aspectos visuales.

Parte 2 - Cambio de color

Ahora que está el tablero generado, faltaría agregar la lógica para cambiar el color del flood, así el juego puede ir progresando.

El bloque de color adyacente de la esquina superior izquierda es lo que nos permite ir avanzando. Cuando se cambia el color del bloque, este se volverá más grande por combinarse con los vecinos del nuevo color.

Se pide implementar el método cambiar_color(self, color_nuevo) de la clase Flood. Para esto el algoritmo debe:

  • Observar el color actual del food, dado por la coordenada (0, 0) (llamémoslo A), y el color a cambiar (llamémoslo B). Si A es igual a B, no se debería aplicar un cambio. Caso contrario, se continúa.
  • Pintar ese casillero y todos los casilleros vecinos que sean de color A con el color B, repitiendo con los casilleros vecinos (arriba, abajo, izquierda, y derecha) siempre y cuando sean de color A.

Este algoritmo suele ser fácil de implementar en forma recursiva. Para el trabajo práctico, solo se aceptan soluciones recursivas del mismo.

Al finalizar esta parte, se podrán seleccionar los colores haciendo click en el tablero.

Parte 3 - Deshacer y rehacer

En el caso de que el usuario se equivoque o decida probar una combinación diferente de colores, el juego debería permitir deshacer y rehacer las diferentes acciones.

El "deshacer" permite revertir las últimas selecciones de colores. Para esto el juego debe tener la capacidad de recordar una cantidad ilimitada de esas selecciones, y si deshacemos repetidas veces deberíamos siempre poder llegar al estado inicial del tablero.

Por otro lado, la herramienta "rehacer" permite "deshacer el deshacer" y solo tiene efecto luego de haber hecho "deshacer" una o más veces seguidas. La idea es que el usuario tenga la opción de usar "deshacer" y "rehacer" todas las veces que quiera para visualizar el cambio del tablero en sentido inverso (al "deshacer") y en sentido directo (al "rehacer"). En cualquier momento en el que el usuario hace cualquier acción que no sea "deshacer" o "rehacer", pierde la posibilidad de "rehacer" hasta la próxima vez que haga "deshacer".

Para resumir: este funcionamiento se asimila a cómo funcionan las operaciones de deshacer y rehacer en programas tradicionales, como fuera un editor de texto, o un editor de imágenes. Los casos borde deben funcionar similar a cómo suceden en dichos programas.

Estas funcionalidades se implementan con un par de pilas.

Para esta parte será necesario modificar la clase JuegoFlood de juegoflood.py. Esta clase es la que realiza las llamadas a los métodos de la clase Flood sobre su propio self.flood, y a su vez permitirá administrar múltiples instancias de Flood para implementar el deshacer y rehacer.

Antes de implementar la funcionalidad para deshacer y rehacer, es importante completar el siguiente método en Flood:

  • Flood.clonar: devuelve una nueva instancia de Flood con los mismos atributos que la misma. Se deberá llamar a este método en los métodos de JuegoFlood. Es necesario que la copia sea profunda para que no haya problemas a la hora de implementar el deshacer/rehacer. No está permitido el uso del módulo copy.

Una vez realizado el Flood.clonar se pide modificar los siguientes métodos para llevar adelante las funcionalidades solicitadas:

  • JuegoFlood.__init__
  • JuegoFlood.cambiar_color
  • JuegoFlood.deshacer
  • JuegoFlood.rehacer

Al finalizar esta parte, se podrán utilizar los botones de deshacer y rehacer del programa.

Parte 4 - Solución automática y cantidad de movimientos

Uno de los desafíos del Flood es intentar solucionarlo en la menor cantidad de movimientos posibles. Para esta última parte se implementará un algoritmo para encontrar una posible solución del juego, con un par de objetivos:

  • Permitirle al usuario una solución en cualquier punto del juego.
  • Dar una cantidad de movimientos para que el juego se "pueda perder".

Al hablar de una solución, primero es necesario determinar cuándo se terminó el juego. Entonces para comenzar:

Se pide implementar el método Flood.esta_completado para luego utilizarlo en el algoritmo de cálculo de solución.

El algoritmo a implementar intentará resolver el juego en la menor cantidad de movimientos posibles, y será del tipo Greedy. Este es un tipo de algoritmo que usa una heurística o regla para determinar el siguiente paso "óptimo" a partir de un estado local, aplicando un paso de forma iterativa hasta que se llegue a una solución. En el caso del Flood, no siempre va a garantizar la solución de menor movimientos posibles pero es una aproximación que se encuentra de forma rápida.

El algoritmo en sí de solución es intuitivo. Mientras el juego no esté completado, repetimos:

  1. Evaluamos cada color utilizando un criterio específico (*) y nos quedamos con el color que maximiza o minimiza el criterio.
  2. Cambiamos el flood según el color ganador.

El criterio del primer paso es la parte interesante del algoritmo. Puede ser un criterio de sentido común que nosotros mismos podríamos aplicar a la hora de jugar al juego. Como criterio simple, recomendamos implementar que se busque el color que más casilleros agregaría al flood actual.

Se pide implementar:

  • JuegoFlood._calcular_movimientos: calcula una solución del Flood, devuelve la cantidad de movimientos y una Cola con la secuencia de movimientos que solucionan el Flood. Completar la documentación del método describiendo en pocas palabras el criterio de solución utilizado.
  • Si se considera necesario, implementar un método dentro de Flood para facilitar el cálculo del criterio.

Al finalizar esta parte, la cantidad de movimientos "máxima" indicada en la ventana será la que devolvió el algoritmo, y también funcionará el botón solucionar.

Entrega

Se deberán entregar al formulario los archivos flood.py y juegoflood.py que se hayan utilizado. Si se realizaron cambios importantes en el programa principal o en los TDAs, también deben incluirse con la entrega.

Extra: Envío por Hopper

De forma extra y opcional, pueden ayudar a probar un Trabajo Práctico Profesional en desarrollo llamado Hopper (elaborado por Javier Di Santo, Camila Dvorkin, y Juan Pablo Rombolá). Están buscando voluntarios para que prueben el sistema y envíen feedback.

Similar a RPL que es una plataforma para la guía de ejercicios, Hopper es un sistema para trabajos prácticos, que permite entregar, ver versiones, ejecutar pruebas sobre lo entregado, y recibir la corrección, todo en una misma página.

Si quieren participar, los pasos a seguir son los siguientes:

  1. Ingresar a la plataforma de Hopper
  2. Crearse una cuenta, inscribirse en el curso de Algoritmos I - Essaya
  3. Subir los archivos flood.py y juegoflood.py por el sistema bajo "TP3"
  4. Ver la ejecución de pruebas/acciones de la entrega realizada, para comprobar que la entrega pase los casos contemplados. Si las pruebas no se ejecutaron correctamente, podés mandar otra entrega. No es criterio mínimo de aprobación del TP3 que las pruebas pasen!

Si decidís participar:

  • Antes que nada, ¡muchas gracias! ❤️
  • Recordá, sí o sí, mandar el trabajo práctico por nuestra típica página de Algoritmos 1. Hopper no reemplaza la modalidad de entrega que venimos practicando hasta ahora en la cursada
  • Si completaste todo, nos serviría que llenes los siguientes formularios: