Trabajo Práctico 1
Fecha de entrega: Viernes 28 de noviembre
Introducción
Objetivo
El objetivo del presente trabajo práctico es implementar un clon del juego Sandtrix utilizando la biblioteca gráfica SDL2.
El trabajo consiste en la resolución de un problema mediante el diseño y uso de TDAs y en la reutilización de algunos de los tipos, funciones y conceptos desarrollados a lo largo del curso en trabajos anteriores.
Alcances
Mediante el presente TP se busca que el estudiante adquiera y aplique conocimientos sobre los siguientes temas:
Encapsulamiento en TDAs,
Tablas de búsqueda,
Modularización,
Técnicas de abstracción,
además de los temas ya evaluados en trabajos anteriores.
Nota
Este trabajo es un trabajo integrador de final de cursada. En el mismo se van a aplicar todos los temas aprendidos y además se va a evaluar el diseño de la aplicación.
Es imprescindible entender los temas de TDA y modularización antes de empezar con el trabajo.
Es imprescindible diseñar el trabajo como etapa previa a la implementación.
Cualquier abordaje que pretenda empezar a codificar sin haber ordenado el trabajo primero está condenado a fracasar contra la complejidad del problema.
SDL2 en 5 minutos
Para la representación gráfica se utilizará la biblioteca gráfica SDL2.
Una aplicación gráfica tiene un pseudocódigo más o menos de este estilo:
main() {
inicializar;
while(1) {
leer la entrada del usuario;
procesar lo que haya que procesar;
dibujar la pantalla;
esperar un ratito para cumplir con los FPS;
}
destruir;
}
Se provee un esqueleto completo con esta lógica, donde se indica dónde el alumno tiene que completar con su código. De SDL2 sólo habrá que aprender a leer el teclado, a dibujar puntos y a cambiar el color. El resto ya está hecho.
Se proveen ejemplos tanto de teclado, como del dibujado de cosas.
El espacio de colores "DEF"
Los colores DEF desarrollados en el EJ2 no son otra cosa que un formato HSL (o mejor dicho SHL, porque ese es el orden). HSL es gama, saturación y luminosidad. En este formato la gama define el color, mientras que la saturación y la luminosidad qué tan vivo sea el color y qué tan luminoso.
Lo importante de este formato es que se pueden generar variaciones del mismo color manteniendo fija la gama y variando la saturación y la luminosidad.
En nuestro modelo, dos colores serán el mismo si comparte la misma E.
(Repetimos en DEF, D es la saturación, E la gama y F la luminosidad.)
En nuestro juego generaremos piezas rojas, amarillas, verdes y azules que se corresponden con los valores 0, 11, 22 y 44 de E respectivamente.
Para generar una pieza de color E cada pixel DEF tendrá la combinación \((12 + \mbox{rand}(8), E, 12 + \mbox{rand}(8))\), donde \(\mbox{rand}(a)\) es un número aleatorio entre 0 y \(a - 1\).
Cosas importantes sobre DEF. El valor 0x00 es el color negro, el valor 0xff
es el blanco, pueden usarse estos casos para verificar estos dos colores.
El juego
El juego Sandrix es una versión libre del Tetris. En el mismo caen de a una por vez piezas (tetraminos) de un determinado color. Mientras la pieza está cayendo el usuario puede rotarla, moverla a la izquierda, a la derecha o apurarla hacia abajo con las cuatro flechas del teclado. Hasta ahí describimos el Tetris.
En el Sandtrix el tablero es una simulación de arena. Cuando una pieza toca algún grano de arena del tablero cada uno de sus pixeles se convierte en un grano de arena y pasa a formar parte de la simulación. En este juego, las "líneas" se forman por color, si hay un camino de granos de arena que una la pared izquierda con la derecha, entonces se elimina todo ese bloque de granos de arena de ese determinado color.
Al igual que el Tetris en el Sandtrix no hay niveles, el juego se juega en continuo hasta perder. Se pierde cuando ya no entra una pieza nueva en el tablero.
Al momento de empezar a jugar una nueva pieza, en la pantalla se podrá ver cuál será la forma y el color de la próxima pieza a jugar.
El puntaje del juego estará dado por la cantidad de líneas eliminadas.
Las piezas
Las piezas del Tetris se llaman tetraminós y abarcan todas las combinaciones de figuras que se pueden lograr con 4 cajas consecutivas. Según sus formas reciben los nombres: I, L, J, S, Z, T y O. Estan ocupan distintas dimensiones, por ejemplo, la pieza I ocupa un espacio de 1x4 mientras que la O de 2x2.
En nuestro juego cada una de las cajas ocupa 8x8 píxeles, entonces la I ocupará 8x32 pixeles mientras que la O 16x16 píxeles.
Las piezas del Tetris se proveen como sprites con los nombres correspondientes
a su forma en dos versiones, por ejemplo el tetraminó I se provee con el nombre
"i" para la pieza del tablero y como "ic" para la versión "chica" que se
muestra como anticipo de la próxima pieza (en este caso las cajas son de 4x4).
Dado que las cajas tienen 8 de píxeles las piezas se moverán a izquierda de a 8 unidades. Es decir, la pieza estará siempre en una posición múltipo de 8 en x. Ahora bien, cuando una pieza se mueve lateralmente se animará moviéndola de a un pixel por vez. Es decir, cuando el usuario apriete la tecla derecha se sumarán 8 píxeles a la posición, pero se harán de a uno por vez.
Cuando el usuario presione la flecha hacia arriba las piezas rotarán 90 grados en sentido antihorario. Se intentará que el centro de rotación se mantenga en el tablero... con la aclaración de que la pieza tiene que terminar en una posición múltiplo de 8 otra vez. Tomar en cuenta que piezas como la I o la T que tienen un número de cajas de distinta paridad en cada uno de sus ejes no pueden girar sobre su centro y quedar en la misma posición. Plantear una forma de giro que después de dos giros de 90º la pieza no haya avanzado en x.
Las piezas no pueden escaparse nunca del tablero, por lo que no siempre será posible moverse a la izquierda o a la derecha. O después de un giro la pieza tal vez necesite ser empujada a izquierda o derecha.
Las piezas caen desde el centro del tablero (redondeado a 8) y desde el tope de la pantalla, es decir, la pieza asomará sólo si fila de pixeles inferior por la pantalla al ingresar.
Cuando una pieza se genera se genera con un color determinado dado por su E y con todos sus pixeles aleatorios según lo ya mencionado en la sección previa. Los colores de cada uno de los pixeles se deben preservar en toda la vida de la pieza, incluyendo rotaciones.
Más sprites
Además de los sprites de las piezas también se encuentran disponibles sprites con caracteres. Los mismos pueden utilizarse para imprimir textos en la pantalla.
El algoritmo para imprimir el número "130" en la posición \((f, c)\) de
la pantalla es el siguiente: Se pega el sprite correspondiente al "1" (con el
color deseado) en la posición dada. Se incrementa \(c\) según el ancho del
sprite y se repite el procedimiento, para cada uno de los números.
El tablero
El tablero del juego mide 10x18 cajas, es decir 80x144 pixeles. El tablero comienza con todos sus píxeles negros. Las piezas que están cayendo no forman parte del tablero por más que se presenten superpuestas al mismo. Recién cuando una pieza o llega al borde inferior o toca con alguno de sus píxeles un pixel no negro del tablero la misma se "pega" en el tablero.
Pegar una pieza en el tablero es literalmente pegar imagen en imagen, todos los pixeles no negros de la pieza se pegan en la posición correspondiente del tablero.
Sobre el tablero cada vez que el mismo se actualiza se realizan dos operaciones, una es avanzar un paso la simulación de arena, el otro es verificar que no se haya formado una línea. Se describirán las dos operaciones más adelante.
Simulación de arena
La simulación de arena es un autómata finito. No se crean ni se destruyen los granos de arena si no que se desplazan. La simulación se hacen partiendo de un tablero anterior y generando uno nuevo, es decir, las reglas se aplican sobre el viejo tablero y se reflejan en el siguiente.
Las reglas son las siguientes:
El nuevo tablero empieza todo en negro.
La fila inferior del tablero viejo se copia tal cual al nuevo.
Para cada pixel del tablero viejo que no sea negro:
Si generar \(\mbox{random}(4)\) es distinto de cero, el pixel se copia a la misma posición en el tablero nuevo. Es decir con probabilidad 3/4 no pasará nada.
Si no y la posición debajo de ese pixel se encuentra vacía en el tablero viejo entonces el pixel se copia una fila más abajo.
Si no y la alguna de las dos posiciones debajo a izquierda y derecha es decir \((f + 1, c \pm 1)\) están libres se eligirá aleatoriamente una de las dos (o sea, si sólo una está libre será esa pero si están libres las dos se debe optar al azar).
Tomar en cuenta que los píxeles de la primera y última columna no tienen posición a izquierda y derecha respectivamente.
Detección de línea
Se quieren detectar bloques del mismo color que unan la primera columna con la última en el tablero. Cuando decimos mismo color estamos diciendo mismo valor de E.
El algoritmo será el siguiente: Para cada pixel de la primera columna, si el pixel no es negro y no fue visitado previamente entonces se visitará con su color correspondiente. Si la visita devuelve afirmativo entonces se formó una línea.
El algoritmo de visitar será el siguiente: - Si el pixel ya fue visitado entonces el algoritmo devuelve negativo.
Si el pixel no es del color buscado, entonces el algoritmo devuelve negativo.
Si estamos en la última columna, entonces se devuelve positivo.
Si no, se marca como visitada la fila y columna actual y se visitan los pixeles que estén a derecha, arriba, abajo e izquierda del actual. Si alguna de esas visitas devuelve positivo se devuelve positivo. Notar el orden de las operaciones, respetarlo, es más probable que lleguemos a la última columna si avanzamos primero hacia la derecha.
Para llevar la cuenta de posiciones visitadas se puede generar una nueva imagen del mismo tamaño del tablero o una matriz e ir marcando los pixeles ya conocidos.
Notar que la operación de visitar en los 4 sentidos puede escaparse del tablero, en ese caso la respuesta es siempre negativa.
Notar que este algoritmo dado, con estas reglas dadas, no recorre todos los pixeles del bloque, sólo se garantiza que haya un camino desde la primera a la última columna.
Cuando se detecta que hay una línea todos los pixeles del bloque deben ser eliminados (es decir, pintados de negro). Se deja al alumno diseñar el algoritmo a ejecutar para eliminar el bloque una vez detectada la existencia de la línea.
El puntaje
El puntaje del juego será simplemente la cantidad de los píxeles eliminados hasta el momento.
La evolución del juego
En este trabajo desarrollaremos una aplicación gráfica que se ejecutará a una determinada cantidad de cuadros por segundo (FPS, frames per second). El recíproco de los FPS es la duración, en segundos, de cada cuadro. En cada cuadro se deberá redibujar completa la pantalla, lo cual no significa que la evolución de las piezas y del tablero sea a la misma velocidad. Es decir, en la pantalla se muestra FPS veces por segundo el estado del juego, pero el estado del juego se computa según su propia base de tiempo. Dicho de otro modo, si variáramos los FPS el juego tendría más o menos calidad pero seguiría jugándose a la misma velocidad.
El juego inicia con un tablero vacío (negro), cero líneas y cero puntos.
Se inicia con una pieza actual de un color dado y ya se debe decidir la pieza y el color siguientes.
La pieza actual está ubicada en una coordenada \((f, c)\) del tablero. \(f\) avanza a una determinada velocidad en píxeles por segundo. Como el juego se ejecuta a pasos de \(\frac1{\mbox{fps}}\) esa velocidad debe ser dividida en esos cuadros. Entonces en un paso de tiempo \(f\) pasará de un valor a un nuevo valor \(f'\). Si el número entero de \(f\) no varía no se hará nada, si varía se simularán de a pasos enteros. Ejemplo, si \(f\) valía 6.5 y pasa a valer 8.3 entonces habrá que simular con los valores 7 y 8.
¿Qué significa simular una pieza?, verificar que ninguno de los píxeles de esa pieza pegada en sus coordenadas \((f, c)\) toquen un grano de arena del tablero. Si eso sucediera esa pieza pasa al tablero, se genera una nueva pieza en base a la forma y color siguientes y se define el color y forma de la pieza que le siga.
En cada paso de tiempo la simulación de arena se avanza 3 veces. Sí, debería ser función de los FPS, pero ya fue. Avanzar la simulación de arena es mover todos los pixeles como corresponda, y verificar las tres veces si se formó una línea, si se formó sumar una línea, incrementar el puntaje y eliminar el bloque.
Las piezas caen a una velocidad de 25 píxeles por segundo, que se incrementará (acumulativo) en un 1% por cada segundo transcurrido. Ahora bien, cuando el usuario apriete la tecla abajo esa velocidad será de 5 veces más durante un tercio de segundo.
Cuando el usuario apriete izquierda o derecha se utilizarán 4 cuadros para mover efectivamente los 8 pixeles correspondientes.
En el espacio de la derecha del juego deben mostrarse la próxima pieza a venir,
el próximo color, el tiempo transcurrido del tiempo (en formato
"minutos:segundos:milisegundos"), el puntaje y la cantidad de líneas. Las piezas se
muestran según la variante "c" del sprite y el color utilizando el sprite
"tubo". La variable ticks contiene la cantidad de milisegundos desde el
inicio del juego.
Trabajo
Ya se dijo todo lo que había por decir. Se desarrollará un clon del Sandtrix, con las reglas dadas en la introducción.
El juego permitirá jugar, en principio, una única partida, desde el comienzo hasta el final.
El problema que se plantea en este trabajo deberá ser resuelto con las herramientas ya adquiridas, extendiendo de forma consistente los TDAs ya planteados de ser necesario y diseñando los TDAs nuevos que hagan falta. Se evaluará además el correcto uso de los TDAs respetando la abstracción y el "modelo" de Alan-Bárbara, así como la separación de la lógica del juego de la lógica de dibujado en la pantalla, que es un paso posterior sólo de presentación.
A esta altura del cuatrimestre es una obviedad decirlo pero: Todo lo que pueda ser iterativo o implementarse de forma indexada, debe ser hecho de esa manera. Todo lo que amerite tablas de búsqueda debe utilizarlas.
Se deben utilizar los siguientes TDAs:
sprites_t, como fue desarrollado en el EJ3.sprite_t, como fue desarrollado en el EJ3.color_t, como fue desarrollado en el EJ2.imagen_t, como fue desarrollado en el EJ2, agregando y adaptando las funciones implementadas en el EJ1. En este TDA se recomienda agregar las primitivas faltantes como establecer u obtener el color de un píxel, rotar, pegar con transparencia (es decir, pegar sólo los píxeles diferentes al color negro), inicializar con un color determinado, etc.
Se pueden extender los TDAs ya dados y también se pueden implementar TDAs
nuevos. Ahora bien, notar que todos estos TDAs preceden a la existencia del
juego Sandtrix. No sería correcto agregar, por ejemplo, en imagen_t una
primitiva para simular arena, eso no tiene nada que ver con imágenes
si no que es una función particular del juego y que puede (debe) ser
implementada externamente. Los TDAs están hechos para ser usados, no agregar
primitivas a menos que tengan sentido en el espíritu del tipo.
Aplicación
Se pide diseñar una aplicación que pueda ser ejecutada como:
$ ./sandtrix
que permita jugar al juego que describimos con toda la lógica que se mencionó.
Alcance
El alcance es lo especificado en este enunciado. En cualquier aplicación amplia como esta siempre pueden implementarse detalles adicionales, los mismos no forman parte del enunciado y no hay que hacer nada adicional para alcanzar la máxima nota. La prioridad es resolver completa la funcionalidad descrita para terminar con eso la materia.
Material
Fuentes
Se provee el archivo binario de sprites, además el PPM del fondo de la aplicación.
Se provee además el ejemplo de SDL2, el cual tiene todas las constantes que se
mencionaron de forma genérica en este enunciado, disponible para descargar en:
archivos_20252_tp1.tar.gz
Valgrind
En el caso de una aplicación construída con SDL2 se hace complejo el uso de Valgrind porque esta biblioteca tiene desprolijidades en su implementación que hacen que Valgrind tire múltiples errores y estos errores a la tasa que marquen los FPS del juego. Por eso para poder testear con Valgrind sobre el código desarrollado tenemos que suprimir los errores que son relativos a SDL2.
Se provee el siguiente archivo de supresiones para Valgrind:
suppressions_20252_tp1.supp
Con este archivo descargado Valgrind puede ser invocado como:
$ valgrind --suppressions=suppressions_20252_tp1.supp --leak-check=full ./sandtrix
con lo que el programa se ejecutará suprimiendo los millones de errores de SDL2.
Al haber errores y haberlos suprimido el reporte no será del todo satisfactorio, y va a haber memoria en el heap y elementos marcados como "still reachable". El siguiente es un reporte de ejemplo:
==27213== Memcheck, a memory error detector
==27213== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==27213== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==27213== Command: ./rezta
==27213==
==27213==
==27213== HEAP SUMMARY:
==27213== in use at exit: 196,326 bytes in 1,058 blocks
==27213== total heap usage: 32,817 allocs, 31,759 frees, 118,233,488 bytes allocated
==27213==
==27213== LEAK SUMMARY:
==27213== definitely lost: 0 bytes in 0 blocks
==27213== indirectly lost: 0 bytes in 0 blocks
==27213== possibly lost: 0 bytes in 0 blocks
==27213== still reachable: 2,037 bytes in 10 blocks
==27213== suppressed: 194,289 bytes in 1,048 blocks
==27213== Reachable blocks (those to which a pointer was found) are not shown.
==27213== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==27213==
==27213== For counts of detected and suppressed errors, rerun with: -v
==27213== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1018824 from 25)
Notar que pese a que se señala más de un millón de errores, el reporte de
pérdidas dice que no hay bloques ni definitiva, ni indirecta ni posiblemente
perdidos. Además el reporte, pese a haber sido corrido con --leak-check=full
no muestra ningún error en nuestro propio código.
Se busca que el reporte tenga estas características.
Ahora bien, prestar atención porque ignorar los errores de still reachable
puede enmascarar errores como por ejemplo no haber llamado a fclose() entre
otros.
Nota
Ejecutar con Valgrind implica a poner a un programa a analizar cada cosa que hace nuestro programa. Con un programa pesado en cantidad de operaciones como el nuestro, el programa va a andar muy lento.
La idea es correr con Valgrind como un chequeo a realizar, pero no todo el tiempo durante del desarrollo.
Para liberar la carga, sólo durante las corridas de Valgrind, se puede
reducir el valor de JUEGO_FPS a un valor que lo haga más manejable. Notar
que como el juego itera JUEGO_FPS las fallas de memoria más importante
van a ser evidentes con correr apenas un segundo de juego.
Funcionamiento
Este es un ejemplo de implementación con las reglas presentadas en este enunciado:
Entrega
Requisitos
Los únicos requisitos son que el programa resuelva correctamente la funcionalidad pedida y que lo haga utilizando TDAs con un diseño planificado a conciencia. Si hacés eso nada puede salir mal.
Entregables
Deberá entregarse:
El código fuente del trabajo debidamente documentado.
El archivo
Makefilepara compilar el proyecto.
Nota
El programa debe:
estar programado en C,
estar completo,
compilar...
sin errores...
sin warnings,
correr...
sin romperse...
sin fugar memoria...
resolviendo el problema pedido...
Trabajos que no cumplan con lo anterior no serán corregidos.
La entrega se realiza a través del sistema de entregas.
El ejercicio es grupal permitiéndose grupos de hasta 2 integrantes.
Si elegís hacer el trabajo en grupo te pedimos que nos avises o por mail o por Discord quién es tu compañero de grupo así lo cargamos en el sistema de entregas. (Si el grupo sufriera alteraciones avisanos también.)