Proy01: Motor Match3

En 1994 el desarrollador Eugene Alemzhin creó el videojuego Shariki, que en ruso quiere decir "las canicas". Se trata de un tablero matricial donde hay elementos de diferente color dispuestos en forma aleatoria. Cuando tres o más elementos adyacentes del mismo color se alínean de forma horizontal o vertical, forman una combinación, y son removidos del tablero. Su espacio es ocupado por otros elementos que caen por gravedad.

En cada turno el jugador puede intercambiar dos elementos vecinos, con el fin de crear una combinación de elementos adyacentes del mismo color. Su objetivo es conseguir eliminar tantos elementos del tablero como le sea posible. Cuando las combinaciones están conformadas por 4 o más elementos del mismo color, estas generan elementos especiales, que cuando son eventualemente eliminados, crean reacciones que eliminan más elementos y, por consiguiente, permiten obtener más puntos.

Shariki es un juego de rompecabezas (puzzle) y fue el primero de tipo match-3. Sus elementos eran canicas representadas por círculos (ver figura abajo). Este juego inspiró una cantidad asombrosa de adaptaciones, dos de las más conocidas son Bejeweled (PopCap, 2001) cuyos elementos son joyas (ver figura abajo), y Candy Crush Saga (King, 2012) cuyos elementos son dulces (ver figura abajo).

Shariki (1994)
shariki

Bejeweled (2001)
bejeweled

Candy Crush (2012)
candy crush

Elabore una solución que verifique el estado (tableros) del juego tipo match-3 en un momento dado. Su programa recibirá por la entrada estándar varios tableros a verificar. Las dimensiones de los tableros se indican como el número de filas y columnas y deben ser mayores o iguales a 3. Es seguida por el valor de cada celda del tablero. Después de una línea en blanco, continúan las dimensiones del siguiente tablero, sus celdas, y así sucesivamente.

Ejemplo de entrada:

5 6
R1 R1 R1 R1 R1 R1
R1 R2 R2 R2 R5 R4
R1 R2 R3 R6 R5 R4
R1 R2 R3 R6 R5 R4
R1 R3 R3 R3 R6 R4

5 4
R1 R6 R4 R5
H1 R5 R5 V2
R1 R6 R4 R5
R4 R4 B4 R5
R4 R6 R5 W3

Ejemplo de salida:

1:
-- -- -- -- -- --
-- -- -- -- -- --
-- -- -- -- -- --
-- B1 -- R6 -- --
B1 W2 W3 R6 R6 V4

2:
-- -- -- --
-- -- -- --
-- -- -- --
-- -- -- --
-- -- -- --

Cada celda consta de una letra y un número. La letra indica el tipo de elemento en ella, y el número indica el color del elemento, como se describe en las siguientes tablas para los elementos y colores respectivamente.

Código Nombre Descripción

R

Elemento regular

Al ser eliminado no provoca que otros elementos se destruyan.

V

Elemento de rayas verticales

Al ser eliminado provoca que se eliminen todos los elementos de la columna en que se encuentra.

H

Elemento de rayas horizontales

Al ser eliminado provoca que se eliminen todos los elementos de la fila en que se encuentra.

W

Elemento empaquetado (wrapped)

Al ser eliminado provoca que los ocho elementos alrededor suyo sean destruidos.

B

Bomba de color

Destruye todos los elementos de su mismo color que están en el tablero (en el orden izquierda a derecha y de arriba hacia abajo).
Código Color representado

1

Rojo

2

Naranja

3

Amarillo

4

Verde

5

Azul

6

Morado

Su programa debe leer y verificar que cada tablero provisto por los usuarios sea válido. El programa debe reportar el texto invalid input si detecta una entrada con valores faltantes, letras que no forman parte de los códigos de elementos, números fuera del rango esperado, o símbolos que no forman parte de las representaciones esperadas, con el fin de advertir a los usuarios para que puedan corregirlo. Una vez detectado un tablero no válido, el programa se detiene y no continúa procesando más tableros.

Para cada tablero leído, si es válido, su programa debe aplicarle las reglas del juego que eliminan elementos y mueven otros por gravedad. El tablero resultante debe imprimirse en la salida estándar precedido por el número secuencial del tablero. Las reglas del juego se resumen a continuación.

  1. Buscar la próxima combinación con la mayor prioridad. Si hay dos combinaciones de igual prioridad, la que esté más arriba a la izquierda (es decir, en orden natural de lectura izquierda a derecha y de arriba a abajo) se eliminará primero. Las líneas verticales u horizontales de 5 o más, todas tienen la misma prioridad indiferentemente de su tamaño. Si en una celda se forma tanto una horizontal como vertical del mismo tamaño, se escogerá la vertical para producir un efecto más hilarante en el usuario gracias a la gravedad.

  2. Eliminar los elementos que conforman la combinación de mayor prioridad. Si se elimina un elemento especial (rayado, empaquetado o bomba de color) que es parte de la combinación, se eliminan también los elementos que se ven afectados por el efecto del elemento especial.

  3. Generar un elemento especial si la combinación lo provoca. Consúltese la tabla de abajo.

  4. Desplazar hacia abajo los elementos simulando gravedad. No ocurre reemplazo, es decir, no se crean nuevos elementos que ingresan por la parte superior, como ocurre en algunas variantes del juego.

  5. Repetir desde el paso 1 por si hay más combinaciones, algunas des las cuales pudieron ser provocadas por efecto de las eliminaciones y la gravedad. Detenerse cuando no se detecten más combinaciones.

Prioridad Tipo de combinación Efecto

1

Vertical u horizontal de 5 o más elementos

Genera bomba de color (B)

2

En forma de L o T (ver adelante)

Genera elemento empaquetado (W)

3

Vertical de 4 elementos

Genera elemento de rayas verticales (V)

3

Horizontal de 4 elementos

Genera elemento de rayas horizontales (H)

4

Vertical u horizontal de 3 elementos

No genera ningún elemento

Las combinaciones a reconocer son cuatro patrones: horizontal (H), vertical (V), en forma de L, y en forma de T. Para saber si un grupo de elementos conforman un patrón, deben verificar en el orden de izquierda a derecha y de arriba hacia abajo. Los números en la siguiente figura indican el orden de verificación.

combinations

Las formas L se verifican primero que las T en el mismo orden en que aparecen en la figura anterior. Recuerde que los verticales y horizontales tienen más prioridad que las L y T cuando están conformados por 5 o más elementos, o menor prioridad con 4 o menos elementos. En caso de que la combinación produzca un elemento especial, éste se generará siempre en la celda más arriba a la izquierda, indicada por 1 en la figura.

Evaluación

Fecha límite de entrega: 30-noviembre-2022 a la medianoche.
Medio de entrega: repositorio individual de control de versiones.

  1. [5%] Buen uso de control de versiones (commits, ignores). Estructura de directorios.

  2. [5%] Análisis (readme.md o readme.adoc): problema, compilación de la solución (build), manual de usuario.

  3. [10%] Apego a una convención de estilos (linting).

  4. [10%] Documentación de interfaces (javadoc) e implementaciones (comentarios con el pseudocódigo dentro del código).

Diseña en pseudocódigo e implementa una solución algorítmica que:

  1. [10%] Lee, imprime y valida tableros. Reporta errores.

  2. [25%] Encuentra y elimina la primera combinación de más prioridad: V5+, H5+, L, T, V4, H4, V3, H3.

  3. [5%] Aplica recursivamente el efecto de elementos especiales que son eliminados.

  4. [5%] Genera elementos especiales si la combinación lo provoca.

  5. [10%] Aplica gravedad tras cada combinación eliminada.

  6. [15%] Se detiene cuando no hayan más combinaciones. Pasa los casos de prueba.

En todos los rubros se evalúan las buenas prácticas de programación. Recuerde que toda solución digital debe compilar, de lo contrario se evaluará con cero como se indica en la carta al estudiante.

Aspectos técnicos

Estructura de directorios

En su repositorio personal cree una carpeta proy01/ o match3_engine/ para este proyecto. Debe mantenerse la estructura de archivos y directorios característica de un proyecto de Unix o de IntelliJ. La estructura de un proyecto de Unix se resume en la siguiente tabla.

Recurso Descripción Versionado

bin/

Ejecutables

No

build/

Código objeto (.class) temporal

No

design/

Diseño de la solución en pseudocódigo o UML

Sí

doc/

Documentación generada por Javadoc

No

src/

Código fuente (.java)

Sí

tests/

Casos de prueba propios o provistos por los docentes

Sí

Makefile

Compila, prueba, genera documentación

Sí

readme.md

Documento de análisis y manual de usuario en Markdown o AsciiDoc

Sí

.gitignore

Ignora los recursos que NO deben estar en control de versiones (columna Versionado)

Sí

La siguiente tabla muestra la estructura de archivos y directorios para un proyecto de IntelliJ.

Recurso Descripción Versionado

.gradle/

Archivos de Gradle generados automáticamente.

NO

.idea/

Archivos de IntelliJ generados automáticamente.

NO

design/

Contiene el pseudocódigo de su solución.

SI

doc/

Contiene su documentación generada por Javadoc.

NO

gradle/

Carpeta con archivos necesarios para construir el proyecto con la versión de Gradle con la que fue creado.

SI

src/

Archivos con su código (archivos fuente).

SI

tests/

Casos de prueba propios o provistos por los docentes.

NO

build.gradle

Archivos de dependencias del proyecto.

SI

gradlew

Archivos de configuración del proyecto.

SI

gradle.bat

Archivos de configuración del proyecto.

SI

settings.graddle

Archivos de configuración del proyecto.

SI

.gitignore

Indica cuales archivos y carpetas no deben ser incluidos al control de versiones.

SI

Haga buen uso del repositorio de control de versiones. Cada commit debe tener un cambio con un significado, un mensaje significativo, y "no romper el build". No haga "megacommits" que implementan muchas funcionalidades distintas y acumuladas en varios días de desarrollo.

Sea severamente cuidadoso(a) al agregar archivos a control de versiones. No agregue archivos ejecutables, código binario, o carpetas que surgieron de la salida de un programa automatizado. Además de los archivos que tienen "No" en la columna "Versionado", haga que su .gitignore ignore archivos generados por el sistema operativo, como .DS_Store en macOS o thumbs.db en Windows. Si no lo está ya, es mejor que este archivo se encuentre en la raíz de su repositorio de control de versiones y no en su carpeta del proyecto.

Su solución debe ser una obra intelectual propia por la naturaleza individual de la evaluación. Si reutiliza código de alguna fuente, dé el respectivo crédito. Por ejemplo, si son unas pocas líneas, basta un comentario en el código fuente que diga: // Adaptado de <URL>. Si reutiliza varios archivos, la referencia debe estar en su readme.md, en una sección de "Créditos", donde liste el nombre de la biblioteca, el creador, la dirección electrónica, la licencia, si la tiene. Nota: no es necesario dar crédito a los ejemplos y materiales provistos por los docentes en este curso.

Análisis

En un archivo readme.md en notación Markdown, o si lo prefiere readme.adoc en notación AsciiDoc, plasme el resultado de la fase de análisis. Si no conoce el formato Markdown o AsciiDoc, asegúrese de seguir un manual o buscar un tutorial, ya que la buena calidad del código también será evaluada. Por ejemplo, un párrafo en estas notaciones se forma al separar por dos cambios de línea y no por uno. Su documento de análisis debe incluir:

  1. Una descripción del problema a resolver. Puede replicar o adaptar la primera parte de este enunciado.

  2. Un manual de uso, que indica cómo construir (compilar) la solución, y cómo correrla. Conviene proveer ejemplos de cómo correr el programa, sea de forma interactiva, o en lote redireccionando la entrada estándar. Provea un ejemplo de cómo reacciona el programa ante una entrada no válida. No es necesario hacer capturas de pantalla de la terminal, se puede copiar y pegar la salida en un bloque de código de Markdown o AsciiDoc.

  3. Una sección de créditos, donde indica su nombre e información de contacto (correo institucional). Si utiliza recursos de terceros, como imágenes o archivos de código fuente, dé el respectivo crédito.

Identificación de patrones

Para identificar combinaciones con patrones L o T, puede usar la siguiente matriz compuesta de: Ocho filas correspondientes a los cuatro patrones L seguidos de los cuatro patrones T. Cinco columnas correspondientes a las cinco celdas que conforman cada patrón. Cada celda corresponde a un "desplazamiento" o "corrimiento" (offset) a partir de la primera celda del patrón.

/**
  * Offset coordinates of each cell within LT figures from [1] cell. For
  * example if cell 1 of L1 is in row r and column c of the matrix, the
  * remaining cells of the L1 figure are at:
  * <pre>
  * [r+0,c+0]
  * [r+1,c+0]
  * [r+2,c+0] [r+2,c+1] [r+2,c+2]
  * </pre>
  */
private static int[][][] ltShapes = {
  // 1         2         3         4         5
  {{+0, +0}, {+1, +0}, {+2, +0}, {+2, +1}, {+2, +2}},  // L1
  {{+0, +0}, {+1, +0}, {+2, -2}, {+2, -1}, {+2, +0}},  // L2
  {{+0, +0}, {+0, +1}, {+0, +2}, {+1, +0}, {+2, +0}},  // L3
  {{+0, +0}, {+0, +1}, {+0, +2}, {+1, +2}, {+2, +2}},  // L4
  {{+0, +0}, {+0, +1}, {+0, +2}, {+1, +1}, {+2, +1}},  // T1
  {{+0, +0}, {+1, +0}, {+2, -1}, {+2, +0}, {+2, +1}},  // T2
  {{+0, +0}, {+1, +0}, {+1, +1}, {+1, +2}, {+2, +0}},  // T3
  {{+0, +0}, {+1, -2}, {+1, -1}, {+1, +0}, {+2, +0}},  // T4
};

Por ejemplo para determinar si existe un patrón T4 a partir de la celda m[r][c] de la matriz, debe cumplirse que todas las siguientes cinco celdas tengan elementos del mismo color:

m[r+0][c+0]  // 1
m[r+1][c-2]  // 2
m[r+1][c-1]  // 3
m[r+1][c+0]  // 4
m[r+2][c+0]  // 5

Casos de prueba

Puede descargar el archivo de casos de prueba (tests.7z), descomprimirlo a la carpeta de su proyecto, y agregar los archivos .txt de la subcarpeta tests/ a control de cambios. Para correr su solución contra todos los casos de prueba, puede usar el Makefile genérico en un ambiente Unix (como Linux o macOS). Los siguientes comandos instalan los programas necesarios para compilar, correr, y comparar la salida de su programa contra los casos de prueba en una distribución de Linux basada en Debian (ej.: Debian o Ubuntu):

make instdeps
make test

Solución para pruebas

Esta solución binaria (match3.jar) puede correrse en modo verboso, con el argumento de línea de comandos -v, para ver paso a paso cómo se aplican las reglas del juego a los tableros en los casos de prueba. Se usa la notación tablero.combinacion.especial: antes de cada tablero para indicar el número de tablero leído en la entrada estándar, el número de combinación encontrada en él, y el número de objeto especial eliminado. El siguiente sería un ejemplo de invocación:

$ java -jar match3.jar -v < tests/input001.txt

Linting

Su código debe apegarse a la convención de estilo de Google, y por lo tanto, no generar diagnósticos del linter checkstyle con la configuración /google_checks.xml. Si usa Makefile puede correr este linter con el comando:

make lint

Si usa Visual Studio Code, puede obtener los diagnósticos directamente en el editor. Siga estos pasos para configurarlo:

  1. Instalar la extensión Checkstyle for Java.

  2. Configurar la extensión. En el campo "Java › Checkstyle: Configuration" agregar /google_checks.xml.

Las reglas de estilo de Sun Microsystems (/sun_checks.xml) son más exigentes que las de Google, y será la convención para el proyecto02.

Proy02: GUI Match3

Fecha límite de entrega: 14-diciembre-2022 a la medianoche. Medio de entrega: repositorio grupal privado de control de versiones. Es necesario que el equipo cree un repositorio nuevo y agregue a su profesor. El equipo podrá reutilizar código del proyecto01 de sus integrantes.

Cree una aplicación de interfaz gráfica de usuario que permita a las personas usuarias jugar interactivamente con las reglas de match 3 del proyecto 1. Este proyecto puede realizarse en grupos de dos o tres integrantes. Se entrega en un repositorio grupal privado de control de versiones al cual deben agregar su docente del curso.

  1. [5%] Buen uso equilibrado de control de versiones (commits, ignores). Estructura de directorios.

  2. [5%] Documento de análisis (readme.md o readme.adoc): problema, compilación (build) de la solución, manual de usuario con capturas de pantalla ("cómo jugar"). Integrantes. Crédito a recursos de terceros (imágenes, sonidos).

  3. [10%] Diseño orientado a objetos (UML). Diseño orientado a eventos (máquina de estados).

  4. [10%] Apego a una convención de estilos (linting).

  5. [20%] Crea tableros generados aleatoriamente o cargados desde archivos. Visualiza el tablero en la interfaz de usuario.

  6. [10%] Reutiliza el motor de match3 del proyecto01 para aplicar las reglas del juego que eliminan las combinaciones de acuerdo a su prioridad, generan elementos especiales, aplican efectos especiales, y aplica gravedad.

  7. [10%] Refleja en la interfaz gráfica el efecto de aplicar las reglas del juego.

  8. [10%] Permite al usuario intercambiar dos elementos adyacentes. Deshace la jugada si no genera una combinación. Aplica las reglas del juego si la jugada es correcta (punto 6).

  9. [10%] Agrega nuevos elementos al azar tras aplicar gravedad. Detecta cuando no hay más jugadas posibles y toma alguna acción (game over, generar un nuevo tablero al azar…​).

  10. [10%] Realimenta al usuario de cambios en el tablero mediante animaciones (eliminaciones y gravedad).

En todos los rubros se evalúan las buenas prácticas de programación. Recuerde que toda solución digital debe compilar, de lo contrario se evaluará con cero como se indica en la carta al estudiante.