Trabajo Práctico 1
Fecha de entrega: Domingo 3 de diciembre
Introducción
Objetivo
El objetivo del presente trabajo práctico es implementar una versión simplificada del juego Zuma, haciendo uso de gráficos de curvas, listas enlazadas y 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,
Listas enlazadas,
Contenedores y tablas de búsqueda,
Punteros a funciones,
Archivos,
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.
El Juego
En el juego Zuma el jugador controla con el mouse a un sapo que dispara bolas de colores. El sapo se orienta hacia donde señala el mouse, y la bola que dispara sale en esa dirección. El juego tiene bolas de cuatro colores diferentes y se conoce tanto el color de la bola actual como de la siguiente.
En paralelo, van entrando en fila bolas de diferentes colores, las cuales avanzan sobre un camino hacia una calavera. Cuando una de las bolas llega a la calavera se pierde el juego.
El jugador debe disparar bolas a las bolas ya existentes. Cualquier bola que toque a una de las bolas que está en el camino se inserta en la fila de bolas. Ahora bien, si esa inserción genera 3 o más bolas consecutivas del mismo color las mismas se eliminan de la fila dejando un agujero. Al eliminar un conjunto de bolas de la fila podría pasar que la primera y la última bola del agujero tengan a su vez el mismo color y además sea un conjunto de más de 3 o más bolas consecutivas del mismo color, en ese caso se eliminarán todas esas bolas, pero además todas las bolas retrocederán para llenar el espacio.
Además hay bolas con características especiales que se activan al ser eliminadas. Una de ellas pausa el avance de las bolas por unos segundos, otra de ella hace retroceder a todas las bolas y otra de ellas hace desaparecer a todas las bolas que estén a un radio de ella.
El objetivo del jugador es eliminar todas las bolas del nivel, antes de que las mismas lleguen a la calavera. Si lo hace, avanza de nivel.
Cada vez que elimina bolas obtiene puntos, y estos puntos se multiplican cuando hace un combo que elimina los agujeros.
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 mouse, a dibujar puntos y a cambiar el color. El resto ya está hecho.
Se proveen ejemplos tanto de mouse, como del dibujado de cosas.
Las coordenadas del mouse SDL2 las informa en píxeles desde la esquina superior izquierda de la pantalla. Usaremos esa convención para dibujar cosas.
Implementación
TDA Bézier
Desde el comienzo del cuatrimestre se está construyendo un TDA Bézier, el cual se carga con puntos y luego puede evaluar curvas.
Se tienen del EJ3 las siguientes primitivas:
bezier_t *bezier_crear(size_t grado);
void bezier_destruir(bezier_t *bezier);
size_t bezier_cantidad_tramos(const bezier_t *bezier);
bool bezier_agregar_punto(bezier_t *bezier, float x, float y);
bezier_t *bezier_clonar(const bezier_t *bezier);
bool bezier_evaluar(const bezier_t *bezier, double t, double *x, double *y);
Además se tienen del EJ2 las siguientes funciones, que tienen que ser modificadas para ser primitivas del TDA:
void trasladar(float puntos[][2], size_t n, float dx, float dy);
void rotar(float puntos[][2], size_t n, double rad);
double cercania_a_bezier(int n, float puntos[n + 1][2], float px, float py);
(Notar que la última trabajaba con un único tramo y nuestro TDA es multitramo.)
Además es necesario agregar una primitiva:
double bezier_avanzar(bezier_t *bezier, double t_inicial, double distancia);
que dado un t_inicial devuelva un t mayor al dado tal que el punto esté a
la distancia pedida del punto inicial. Para implementar esta primitiva se
debe tomar un t_final igual a bezier_cantidad_tramos(bezier) y luego
encontrar el t buscado haciendo búsqueda binaria, hasta que inicial y
final sean muy parecidos. Si con el t_final inicial no alcanza para la
distancia pedida se debe devolver ese valor, al final de la curva.
Diccionario de curvas
En el EJ4 se implementaron funciones que permiten extraer curvas de Bézier de un archivo. Cada una de estas curvas tiene un nombre dado por una cadena de caracteres y permite instanciar un TDA Bézier.
Debe implementarse algún TDA contenedor que permita almacenar curvas de Bézier
dado un nombre y recuperarlas por ese nombre. Es decir, si al TDA se le pide
la curva "NIVEL1" debe ser capaz de devolver el bezier_t que la representa.
Lista de bolas
Para la lista de bolas se deberá implementar una lista doblemente enlazada.
Una lista doblemente enlazada es aquella donde sus nodos tienen un puntero no
sólo al nodo siguiente, sino también al nodo anterior. El siguiente del último
nodo será NULL mientras que el anterior del primero también.
La lista puede implementarse como un contenedor genérico, pero sería perfectamente válido que sea una lista de bolas y que conozca no sólo a las bolas sino que tenga primitivas específicamente para resolver las operaciones necesarias para el juego.
No es el objetivo implementar una lista doblemente enlazada con todas sus operaciones genéricas sino solamente las que hagan falta para el desarrollo del juego.
En principio las bolas que se insertan en la lista se hacen o desde el comienzo de la misma, a medida que van agregándose al juego. Ahora bien, también los disparos insertan bolas, en ese caso la bola se insertará en la posición de la bola que esté más cercana.
Como se verá, al insertar en una posición es importante poder saber si esa inserción provoca un agrupamiento de 3 o más bolas del mismo color, lo cual puede disparar que haya un nuevo agrupamiento y así. Por eso es importante poder conocer no sólo las bolas siguientes sino también las anteriores y eso justifica tener una lista doblemente enlazada.
Si estas operaciones las maneja la lista con primitivas o si las implementa el usuario a través de un iterador, es decisión de diseño.
El movimiento de las bolas
Las bolas se mueven siendo empujadas por las bolas que están más atrás. En realidad la única bola que hay que mover es la primera. Las demás se van a mover porque son empujadas.
Cada bola tiene un diámetro de 32 píxeles. Si se hace avanzar a la primera bola sobre la curva puede pasar que el centro de la bola siguiente esté a menos de 32 píxeles del centro de la bola. En ese caso se tiene que desplazar tal que esté a 32 píxeles. Lo cual puede hacer que la bola siguiente... y así se mueven todas las bolas.
Si un disparo inserta una bola en la lista, entonces todas las bolas que le siguen se desplazarán para adelante.
Ya se mencionó pero cuando se eliminan bolas quedan agujeros. Esto quiere decir, se sacan bolas de la lista y puede pasar que haya bolas que no se muevan porque no hay bolas que las empujen. Ese es el comportamiento del juego.
Ahora bien, cuando se hace un combo, es decir, un disparo provoca que se eliminen bolas y esto dispara más eliminaciones en cascada, se produce un colapso. Esto quiere decir que en ese caso, en vez de quedar un agujero, las bolas que quedan a posterior de la última bola eliminada se ajustan para estar todas a 32 píxeles.
Cuando la última bola de la lista haya llegado al final de la curva sobre la cual se desplazan se pierde el juego.
La velocidad de las bolas es variable: Al principio del juego se mueven a 500 píxeles por segundo, durante un tiempo determinado, para que se llene la pantalla. Después, durante el desarrollo del juego se mueven a 25 píxeles por segundo. Y cuando una bola llega a la calavera, otra vez se mueven todas a 500 píxeles por segundo y se pierde el juego.
Las bolas
Las bolas son de 4 colores distintos: Azul, rojo, verde y amarillo. Las que se están desplazando sobre la fila de bolas lo hacen siempre sobre la curva que representa al camino. Es decir, cada bola tiene una posición, pero esa posición está dada a fin de cuentas por el t que le corresponde sobre su curva.
Todo en el juego se dibuja con curvas, las bolas tienen representaciones gráficas diferentes según cada color.
El color de la próxima bola se define de forma aleatoria.
Las bolas pueden ser comunes o pueden ser especiales. Ya se mencionó que hay tres tipos de bolas especiales: Pausa, retroceso y exposión. Una bola puede ser especial de forma aleatoria con una probabilidad del 5%, y luego puede ser de cualquiera de los tipos especiales, también de forma aleatoria. Para el trabajo es necesario implementar al menos una de las bolas especiales.
Cuando una bola es especial se dibuja con la curva que corresponde a esa bola.
El sapo
El sapo en cada nivel está ubicado en una posición diferente definida por el nivel. El sapo está simpre mirando hacia donde esté el mouse.
El color de las próximas dos bolas que disparará el sapo son aleatorios y
están definidos. La próxima bola se dibuja en la boca del sapo, que está 26
píxeles a la derecha del centro del sapo. Mientras que el color de la bola que
le sigue a la próxima se dibuja en el lomo del sapo, con la curva de
"PROXIMABOLA" la cual ya está centrada 26 píxeles a la izquierda.
Si el usuario aprieta el botón derecho del mouse, se intercambian los colores de estas dos bolas.
Cuando el usuario aprieta el botón izquierdo del mouse se produce un disparo. Un disparo pone una bola del color de la que el sapo tenía en la boca a moverse por la pantalla, en la dirección que apuntaba el sapo y a una velocidad de 250 píxeles por segundo.
Al efectuar un disparo, el color de la bola del lomo del sapo pasará a ser el color de la bola de la boca y se generará un nuevo color de lomo aleatorio.
Al final del juego, cuando ya ingresaron todas las bolas en la fila, los colores que debería ofrecer el sapo deberían ser los de las bolas restantes, así está implementado en el juego original. No es necesario implementar esto.
Se permiten múltiples disparos. Los disparos se moverán por la pantalla a la velocidad de 250 píxeles por segundo hasta que o toquen una bola de la fila (es decir, la posición de sus centros sea menor a 32 píxeles) o se salga de la pantalla, es decir, x o y negativas o superiores a las dimensiones de la pantalla (se recomienda tomar un margen de 16 píxeles, un radio, para que la bola desaparezca después de atravesar completa y no cuando atraviesa su centro).
Niveles
Se proveen 4 niveles:
Nivel 1:
Curva:
"NIVEL1"Coordenadas del sapo: (241, 248)
Cantidad de bolas del nivel: 40
Cantidad de segundos a velocidad de 500: 0.5
Nivel 2:
"NIVEL2", (334, 247), 100, 2Nivel 3:
"NIVEL3", (305, 337), 100, 2Nivel 4:
"NIVEL4", (326, 113), 100, 2
Cada vez que se termina un nivel se pasa al siguiente.
Cabe destacar que si bien se proveen los datos de 4 niveles, la cantidad de niveles puede ser indeterminada. La selección del nivel se tiene que hacer de forma natural desde una lista de niveles arbitraria.
La cantidad de bolas del nivel representa cuántas bolas van a entrar en la
fila. Las bolas entran en el t = 0 de la curva de Bézier del nivel, siempre y
cuando la primera bola que ya está en la curva esté a una distancia de más de
32 píxeles del inicio. Una vez que ingresaron las bolas del nivel no deben
ingresar más bolas y se juega con las que quedan.
La calavera se debe dibujar en el punto final de la curva del nivel.
Al eliminar todas las bolas de un nivel se avanza al nivel siguiente.
Puntaje
Cada bola destruída suma 10 puntos.
Ahora bien, si hay combos estos puntos se multiplican. Para el primer combo el número se multiplica por 4, el segundo 8, tercero 16 y así.
Trabajo
Ya se dijo todo lo que había por decir.
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 pide diseñar una aplicación que pueda ser ejecutada como:
$ ./rezta
que permita jugar al juego que describimos con toda la lógica que se mencionó.
Se deben implementar TDAs donde se considere que es necesario.
Al menos las curvas de Bézier, el contenedor de curvas, la lista de bolas y las bolas tienen que ser implementados como TDAs con sus características y comportamiento.
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 con todas las curvas del juego.
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_20232_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_20232_tp1.supp
Con este archivo descargado Valgrind puede ser invocado como:
$ valgrind --suppressions=suppressions_20231_tp2.supp --leak-check=full ./rezta
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.)