Home › Blog

Experiencia RAIS en el aprendizaje de Programación

Posted on by remmurd — No Comments ↓

La estrategia RAIS

RAIS (acrónimo de Reproducción del Ambiente de Innovación en el Salón de clases) es una estrategia que se enfoca en la utilización integral de los conocimientos para construir, crear, hacer, producir e innovar en el salón de clases. Esta estrategia se ha implementado en la Universidad de Los Andes desde el año 2009, con la intención de formar estudiantes con un pensamiento emprendedor.

En esta entrada está inspirada en el ensayo “Una experiencia RAIS en el aprendizaje de Programación” de Mujica et al, escrito para el 1er congreso del Estado Mérida en el cual se habla sobre la experiencia RAIS en Programación 3 en el semestre U-2016. Aquí se añade también la experiencia en el semestre U-2017 en Programación 3 y en Diseño y Análisis de Algoritmos.

Programación 3

Programación 3 es un curso perteneciente al cuarto semestre de la carrera Ingeniería de Sistemas de la Universidad de Los Andes (EISULA por sus siglas) como parte del ciclo básico. Este curso se consagra en el estudio de las primeras técnicas de diseño y análisis de algoritmos y de estructuras de datos, cuyo problema fundamental es el conjunto. En este problema fundamental se estudian las diferentes maneras de instrumentarlo y de resolver sus operaciones básicas, tales como la inserción de un elemento; verificación de la existencia de un elemento, lo cual conlleva a la búsqueda; eliminación de un elemento; y unión, intersección y particiones de conjuntos.

Entre las aplicaciones de los conocimientos con las que se trabaja en esta asignatura se encuentran la instrumentación de compiladores e intérpretes de programas, desarrollo de agentes inteligentes, desarrollo de buscadores, instrumentación de sistemas de gestión de bases de datos, desarrollo de videojuegos, simulación a eventos discretos, entre otras.

El curso Diseño y Análisis de Algoritmos

Diseño y Análisis de Algoritmos es un curso perteneciente al sexto semestre de la EISULA, como parte del ciclo formativo de la carrera. En éste se consolida el estudio de las estructuras de datos y algoritmos necesarios para soportar los problemas más complejos de las ciencias de la Computación y la Investigación de Operaciones. En este curso se estudian técnicas avanzadas de análisis y diseño de algoritmos, teoría de grafos y sus aplicaciones para problemas de optimización y combinatoria y una introducción a la Geometría Computacional.

De los campos de aplicación a los que hace referencia los conocimientos del área, vale mencionar los siguientes: Desarrollo de agentes inteligentes; algoritmos de enrutamiento en Redes de Computadores; modelado de entornos para la robótica móvil; análisis y optimización de problemas que pueden ser modelados por redes de flujo, tales como las redes eléctricas, redes hidráulicas, redes de producción de alimento y redes de transporte; búsqueda de rutas óptimas para problemas como vialidad, gestión de proyectos, mapeado y búsqueda de rutas en videojuegos; Computación Gráfica, entre otras.

Otros cursos de la EISULA

En la EISULA existen cursos, tanto obligatorios como electivos, que se consagran en la enseñanza de casos particulares en los cuales se aplican los conceptos aprendidos en los previamente mencionados para la resolución de los problemas en los cuales se especializan. Entre estos cursos cabe mencionar: Bases de Datos, Compiladores, Inteligencia Artificial, Computación Gráfica, Investigación de Operaciones, Modelado y Simulación de Sistemas, Robótica, entre otros. Estos cursos son impartidos en el ciclo profesional de la carrera entre el séptimo y el noveno semestre.

A pesar de que estas asignaturas están en un nivel más avanzado en la carrera, no ha sido impedimento para que los estudiantes de Programación 3 y Diseño y Análisis de Algoritmos estén en capacidad de enfrentar problemas complejos de aplicaciones y los resuelvan de manera exitosa.

Estrategia RAIS semestre U-2016

Para el semestre U-2016 en el curso Programación 3, fue aplicada la estrategia RAIS, basada en la formación de equipos de trabajo y elección de un producto. El curso estaba integrado por 42 estudiantes, para lo cual cada equipo debía estar conformado por un máximo de 5 miembros. Cabe señalar que la formación de los equipos de trabajo quedó al libre albedrío de los estudiantes, así como el elegir el nombre para su equipo o compañía. De igual manera, cada equipo debía elegir el producto a desarrollar, de modo que sintieran una gran motivación para lograrlo. La elección del producto debía cumplir con ciertas condiciones: 1) El producto debía tener un nombre; 2) El producto debía aplicar lo aprendido en el curso; 3) El producto debía ser algo que se pudiese vender a futuro; es decir, del curso debía salir un producto mínimo viable para un potencial emprendimiento; y 4) El alcance del producto debía ser realizable en el tiempo estipulado para el semestre.

Se les hizo énfasis a los estudiantes en que el cómo resolver el problema, objeto del producto, no debía ser una limitante para seleccionar el producto. Lo importante era tener claridad en lo que querían lograr, sin importar qué tan complejo fuese resolverlo, debido a que el conocimiento lo adquirirían, tanto en las clases como en libros, artículos, blogs, etc. Esto significó el primer reto para los equipos. Pensar en un producto que fuese lo más original posible; de no ser así, pensar en cuál sería el valor agregado que ofrece su producto respecto a otros similares; pensar en cómo venderlo, etc.

Como primer compromiso, a cada equipo de trabajo se les asignó como tarea describir su producto, de manera tal que si un inversionista lo leyera, éste sintiese el interés de financiarlo. Esto llevó a algunas fases de entrega y correcciones de cómo escribir una propuesta de valor que fuese interesante para individuos que quieran invertir en proyectos de este estilo. Una vez que se logró que las propuestas habían alcanzado el nivel deseado, se procedió a asignarles la siguiente tarea, que consistió en definir el plan de trabajo para lograr desarrollar el producto. Este plan de trabajo permitió a su ver la asignación de las tareas subsecuentes, tales como investigar cómo se resolverían cada una de las partes del producto. A medida que el desarrollo del producto avanzaba, se fue ejecutando la evaluación del producto, la cual se llevó a cabo en varios avances, uno semanal.

El primer avance de la evaluación del desarrollo del producto consistió en que cada equipo debía presentar, ante los demás, su producto y especificar qué aspectos técnicos utilizarían para resolverlo, entre los que debían estar los relacionados con las estructuras de datos y algoritmos, y finalizar con una propuesta del alcance para los siguientes avances. En cada avance semanal, los equipos debían haber alcanzado lo propuesto en el avance anterior, explicar cómo solucionaron el problema, cuáles fueron sus dificultades y retos para solucionarlo y mostrar la solución al problema. En cada uno de los avances, los evaluadores dieron sugerencias a los equipos en cómo mejorar las propuestas de valor y como venderla (speech). De esta manera, además de formarse como programadores y emprendedores, reciben orientación en cómo hacer buenas exposiciones.

El proceso de desarrollo del producto abarcó seis (6) semanas del semestre. Durante las otras semanas se trabajó en la capacitación de los conocimientos a través de la investigación y las clases magistrales, además de las prácticas de laboratorio de la asignatura. Al final del semestre, se hizo una exposición, en la que cada equipo de trabajo debió presentar sus productos, ante un jurado profesoral encargado de evaluar los productos. En esta evaluación no entraban los aspectos técnicos. Esta actividad pretendió emular un ambiente de feria o festival, en el cual un grupo de emprendedores presentan sus productos a un grupo de empresarios e inversionistas.

Como resultados de la aplicación de la estrategia RAIS en la asignatura Programación 3, durante el semestre U-2016, se desarrollaron nueve (9) productos, en los cuales se abordaron problemas propios del curso, como problemas de cursos más avanzados, a los cuales los estudiantes aún no habían enfrentado. Es notable señalar como los estudiantes aceptaron los retos y vencieron la complejidad a la que enfrentaban en los diversos problemas. Todos los productos fueron completados de acuerdo a la propuesta inicial.

Entre los productos más destacados, desarrollados en el semestre U-2016, cabe mencionar una versión del juego llamado “Dots and boxes” y una versión del juego denominado “Tic tac toe”, también conocido como “Tres en línea”, o como se conoce en nuestro argot popular “La vieja”.

La versión de “Dot and boxes” fue desarrollada por el equipo “Codemakers”, el cual estuvo conformado por Juan Morón, Javier Mérida, Jesús Rojas y Marco Sandoval. En este producto juega una persona en solitario, de modo que fue necesario implementar un agente inteligente que fungiera de otro jugador. Esta inteligencia artificial fue desarrollada con una adaptación del algoritmo “Minimax” basada en la estructura de datos Árbol, estudiada en Programación 3. La adaptación al algoritmo se debió a que éste originalmente funciona para juegos en los cuales no se repiten turnos. Este equipo se enfrentó a retos tales como el desarrollo de la interfaz gráfica para poder jugar, la creación del agente inteligente y aprender a jugar bien para poder hacer que el agente inteligente supiera hacerlo también. A continuación se muestran tres capturas de pantalla de este juego.

805513083_50798 805513427_50091 805513858_49894

Capturas de pantalla del juego Dot and Box de Codemakers.

La versión de “Tic tac toe” fue desarrollada por el equipo “Apamate Games”, conformado por Paola Ocando, Mar Albarrán, Karen Escalante y Elías Guillén. Este producto tiene dos modalidades de juego, de un solo jugador o de dos jugadores. Este producto presentó retos relacionados con la necesidad de desarrollar una interfaz gráfica que fuese lo suficientemente agradable y llamativa para que el usuario se sintiera cómodo al jugarlo, así como diseñar una inteligencia artificial que jugara contra el jugador humano, y poder tener un oponente automático al jugar en la modalidad de un solo jugador. Esta inteligencia fue desarrollada mediante el algoritmo “Minimax”. El último reto planteado para este equipo fue convertir el clásico juego de una matriz de tres filas por tres columnas, a una matriz de cinco filas y cinco columnas, lo cual generó una complicación del algoritmo “Minimax”, para lo cual tuvieron que aplicar otra técnica denominada “Poda Alpha-Beta”. A continuación se muestran dos capturas de pantalla de este juego. 

tictactoe1 tictactoe2

Capturas de pantalla del juego Tic Tac Toe de Apamate Games.

Además de los dos proyectos mencionados, se desarrollaron otros productos interesantes que cubrían las expectativas del curso entre los cuales cabe mencionar los siguientes: “Text Predictor”, un editor de textos predictivo basado en la estructura de datos Árbol instrumentado como un diccionario de prefijos desarrollado por Astrid Rodríguez, Jesús Pernía, Roberto Blanco, Luis Lezama y Miguel Méndez;  “Championship”, un herramienta para la gestión de eventos deportivos desarrollada por Eduardo Pérez; “Tree Viewer”, una herramienta orientada a la enseñanza de los algoritmos sobre árboles binarios de búsqueda en la cual se muestra todo el proceso que ejecutan algunos de los algoritmos de manera gráfica desarrollada por Gerardo Montes, Boaly Yance, David Calderón, Luis Reyes y Argenis Rivas; y el equipo “PCJOKA” conformado por Katherin Candia, José Gregorio Suárez, Patricia Gómez y Charles Benítez desarrollaron una herramienta que sirve como diccionario de sinónimos para ayudar al entendimiento del significado diverso de algunas palabras para los sordo-mudos. Es importante señalar que de los productos desarrollados durante este semestre, varios han evolucionado en emprendimientos reales. Algunos de estos emprendimientos están orientados a mejorar los productos desarrollados en aula de clase para obtener un producto mínimo viable que sea comercializable; en otros casos, los productos desarrollados permitieron que los estudiantes aplicaran todo el conocimiento que adquirieron en el desarrollo de otros productos de emprendimiento.

Estrategia RAIS semestre U-2017

Para el semestre U-2017 se aplicó la estrategia RAIS en los cursos Programación 3 y Diseño y Análisis de Algoritmos. En este semestre se siguieron los mismos lineamientos en el semestre anterior en lo que refiere a la formación de equipos, elección de productos y trabajos de avance. En este semestre hubo un poco más de rigurosidad en las presentaciones, pues tenían limitación de tiempo intentando poner en práctica el clásico discurso del elevador.

Programación 3 estuvo conformado por un grupo de 40 estudiantes mientras que Diseño y Análisis de Algoritmos estuvo conformado por 50. En ambos cursos los equipos de igual manera tenían un máximo de 5 miembros. En ambos cursos se desarrollaron 8 y 9 productos respectivamente. En algunos productos se intentó llevar a cabo innovación sobre productos similares y hubo otros bastante originales. Entre los productos más destacados tenemos los siguientes: “Starving Hamster“, “Holzen the Hunter“, “OSO“, “Cribers“,  “BalTree“, “Maze Out” y “Greedy Spider“.

“Starving Hamster” es un videojuego de plataforma 2D que consiste en un pequeño hamster que decide recorrer todo un parque en la búsqueda de su amada, para esta misión debe evitar ser comido por criaturas como serpientes, águilas y gatos y, además, debe alimentarse constantemente para no morir de hambre. Este juego fue desarrollado por el equipo del mismo nombre (“Starving Hamster”) conformado por Jul Ramírez, Eugimar Carrera, María José Dávila y Dunia Marquina. Este juego insturmenta modelos de autómatas para el comportamiento de las criatuas. A continuación algunas capturas de pantalla de este juego.

804729850_59366 804729380_58883

Capturas de pantalla de Starving Hamster.

“Holzen the Hunter” es un videojuego del estilo ARPG 2D desarrollado por el equipo “Nightvision Designs” conformado por Jorge Rodríguez, Luis Silva, Héctor Sulbarán y Josmar Muñoz. Este juego instrumenta modelos autómatas para las criaturas básicas y árboles de decisión para los jefes. A continuación algunas capturas de pantalla de este producto.

804722551_82875 804725869_81308

Capturas de pantalla de Holzen the Hunter de Nightvision Designs.

“OSO” es una versión del juego de papel y lápiz llamado juego del oso eel cual consiste en un tablero rectangular en el cual se puede elegir entre escribir una letra “O” o una letra “S” para completar la palabra “OSO” la mayor cantidad de veces posible. Este juego tiene una adaptación del algoritmo “Minimax” semejante a la desarrollada en el juego “Dot and Box” para una inteligencia artificial. Fue desarrollado por el equipo “Richard Games” conformado por Oscar Albornoz, Lewis Ochoa y Luis Manuel Sandia. A continuación algunas capturas del juego.

OSO1 OSO2

Capturas de pantalla del juego del OSO de Richard Games.

“Cribers” es un entorno de programación orientado al trabajo en equipo el cual permite crear proyectos de grupo en el cual todos los miembros de un equipo pueden aportar. El computador donde se crea al proyecto es el servidor mientras que los otros miembros acceden como clientes. El editor cuenta con un sistema de mensajería instantánea para la comunicación del los miembros del equipo y permite editar el código de otro mientras éste observa los cambios en línea. Este producto fue desarrollado por el equipo “Cribers’ Crew” conformado por René Peña, Fernando Carrillo, Andrea Briceño, Juan Borges y Carlos Silva. A continuación una captura de pantalla del producto.

804726446_60176 804726340_59951

Capturas de pantalla de Cribers.

“BalTree” es una herramienta orientada a la enseñanza de resolución de operaciones aritméticas paso a paso en la cual el usuario podrá introducir una expresión y la herramienta le dirá todos los pasos para resolverla. Este trabajo se basa en el uso de Árboles Binarios para la resolución de las operaciones. Este producto fue desarrollado por el equipo BalTree conformado por Abraham Mousalli, Argenis Rivas, Émily Araque y Génesis Uzcátegui.

“Maze Out” Es un videojuego cuyo objetivo es resolver laberintos basado en la historia de un chico. Cada laberinto tiene un objetivo diferente. Este producto fue desarrollado por el equipo Maze Out conformado por Sarait Hernández, Ángely Contreras, Gustavo Mejía y Víctor Rojas.

“Greedy Spider” es un juego que consiste en impedir que una araña se coma sus presas atrapadas en la tela de araña. Para impedirlo, el jugador se encargará de cortar algunos hilos de la tela, quemarlos, congelar la araña, colocar señuelos etc. Es un juego por turnos y la idea es quitarle a la araña toda posibilidad de alcanzar la presa. Este producto fue desarrollado por el equipo Greedy Squad conformado por Daniela Baptista, Isamar Benítez, Josué Díaz, Carmen León y Migdalia Valero.

 

Conclusión

La implementación de la estrategia RAIS en estas asignaturas, condujo a los estudiantes a desarrollar las habilidades y competencias propias de un programador, así como destrezas en el trabajo en equipo y aspectos comunicacionales. Además, a través del desarrollo del producto y el trabajo colaborativo se promovieron elementos actitudinales que les permitirán tener una personalidad de individuos emprendedores y retadores.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Posted in Aleph-w, C++, PR3, Programación, Qt, Videojuegos

Manual de instalación de la biblioteca Aleph-w

Posted on by remmurd — No Comments ↓

Esta entrada pretende mostrar la serie de pasos a seguir para instalar la biblioteca Aleph-w en las distribuciones Debian o Ubuntu de GNU/Linux.

1- Instale las dependencias:
:~# sudo -i (Ubuntu) o su – (Debian)
:~# apt-get install build-essential libx11-dev xutils-dev gettext m4 libgsl0-dev libgmp-dev libmpfr-dev

Nota 1: Deseablemente instale el paquete clang.

Nota 2: Asegúrese de que el compilador gcc o el paquete clang tengan el soporte para C++14.

2- Descargue la versión más reciente de las fuentes aquí.

3- Descomprima las fuentes en donde desee.
:~# tar -xjvf aleph-x.x.tbz

4- Entre al directorio mediante una terminal.
:~# cd aleph

5- Abra el archivo Imakefile y, a continuación, edite las líneas 11, 12, 13, 14 y 19 escribiendo los datos de su compilador. Las líneas antes mencionadas contienen lo siguiente (se muestra número de línea y contenido):


11 CC = $(GCCPATH)/gcc
12 AS = $(CLANGPATH)/llvm-as
13 AR = $(CLANGPATH)/llvm-ar clq
14 LD = $(CLANGPATH)/llvm-link -nostdlib
15
16 # now comment clang++ line and uncomment c++ line. Flag for standard could
17 # change according to compiler version. This flag is for gcc 4.6.3. On
18 # 4.7.x should work -std=c++11
19 CXX = $(CLANGPATH)/clang++

Por ejemplo, si mi compilador es g++ y quiero utilizar la versión instalada por omisión, las líneas del archivo deberían quedar así:


11 CC = gcc
12 AS = as
13 AR = ar clq
14 LD = link -nostdlib
15
16 # now comment clang++ line and uncomment c++ line. Flag for standard could
17 # change according to compiler version. This flag is for gcc 4.6.3. On
18 # 4.7.x should work -std=c++11
19 CXX = g++

6- Finalmente ejecute la siguiente secuencia de comandos:
:~# xmkmf
:~# make depend
:~# make libAleph.a

7- Si lo desea puede ejecutar make all para compilar todos los test.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Posted in Aleph-w, C++, PR3, Programación, Programación Genérica Tagged with: , , , , ,

Singleton en C++

Posted on by remmurd — No Comments ↓

Esta entrada la dirijo al análisis de un patrón de diseño que me ha sido útil en varias ocasiones. El problema con éste es que, como comúnmente programo en C++, estaba dejando pasar por alto algo muy importante: el buen manejo de la memoria.

En Ingeniería de Software, el patrón Singleton es un patrón de diseño que restringe la instanciación de una clase a un único objeto. Esto es útil cuando se necesita exactamente un objeto para coordinar las acciones de todo el sistema.

Dicho lo anterior entremos en el tema.

Características del patrón Singleton

Un singleton normalmente se implementa con una clase que tiene las siguientes características:

  • Un atributo estático para la única instancia que tendrá el objeto (en C++ sería un apuntador a la misma clase).
  • Constructores privados.
  • Un método estático que retorne un apuntador o una referencia a la instancia de la clase.

Detalles de la implementación

Al principio la instancia del objeto debe apuntar al una dirección “null”, en en el caso de C++ se inicializa apuntando a nullptr. Una vez que el método es invocado, éste debe verificar si el objeto apunta a “null”, de ser así entonces solicita memoria para el objeto y finalmente lo retorna. Esto es para evitar tener el objeto en memoria si nunca es utilizado. Solamente será instanciado la primera vez que se use.

En la implementación que yo desarrollé tengo dos versiones del método: uno que retorna un apuntador a la instancia y uno que retorna una referencia a la instancia.

La versión que retorna el apuntador a la instancia se ve de la siguiente manera:


static Singleton * get_ptr_instance()
{
  if (instance == nullptr)
    instance = new Singleton;
  return instance;
}

Y la versión que retorna la referencia se apoya en el método anterior, ésta luce como sigue:


static Singleton & get_instance()
{
  return *get_ptr_instance();
}

Hay que tener en cuenta que esta última versión de método podría tornarse peligrosa, pues si se invoca de la siguiente manera:


Singleton s = Singleton::get_instance();

Se creará una copia de la instancia y violará la regla de una única instancia, pues en C++ si no se especifica el constructor copia y el operador =, éste provee una implementación por omisión de éstos. Para evitar este problema se plantean dos soluciones, una es es escribir el constructor copia y el operador = como privados o prohibirlos igualándolos a la palabra reservada “delete” en la declaración.

Mi grandioso error

Como es bien sabido, cuando se usa el operador “new” de C++, la memoria solicitada no se libera hasta que uno mismo la manda a liberar por medio del operador “delete” o hasta que se reinicie la máquina.

Mi gran error en la primera implementación fue llamar al operador “delete” dentro del destructor de la clase, es decir, tenía programado el siguiente destructor.


~Singleton()
{
  delete instance;
}

Bueno, el punto es que eso nunca liberaría la memoria. ¿Cuál fue mi confusión? Comúnmente cuando uno tiene un atributo dentro de una clase al cual se le asigna memoria dinámicamente dentro de ésta, hay que asegurarse de liberar la memoria en el destructor. La diferencia aquí es que no estamos hablando de un objeto cualquiera sino de un apuntador a la misma clase que lo contiene que además de eso será la única instancia existente.

El destructor de una clase se invoca cuando es invocado el operador “delete” sobre un apuntador o cuando un objeto sale de su ámbito. Ahora bien, ¿qué debería ocurrir para que se liberase la memoria de la instancia? Que el destructor fuese invocado, pero para que sea invocado debería, o bien, una instancia salir de ámbito o llamarse el operador “delete” sobre un puntero instanciado con “new”. En este caso como el Singleton fue instanciado mediante el operador “new”, es necesario hacer el llamado al operador “delete” explícitamente para que se pueda invocar el destructor. El caso es que como yo lo había implementado había creado una paradoja en la destrucción, pues nunca se llamaría el operador “delete” porque nunca se invocaría el destructor porque nunca se llamó a un “delete” (sí, una paradoja).

Al final de la ejecución del programa, lo que se libera automáticamente es el apuntador, es decir, el espacio de memoria que almacena la dirección reservada para la instancia, pero jamás liberaría la instancia como tal.

Después de que descubrí el error garrafal que cometí, llegué a la conclusión de que al final de la ejecución del programa es que se debe llamar al “delete” sobre el apuntador a la instancia de la siguiente manera:


delete Singleton::get_ptr_instance();

Esto plantea entonces dos posibles escenarios, y son:

  • ¿Qué pasará si el el objeto nunca es utilizado durante la ejecución del programa? La respuesta es, cuando se llame a “delete” sobre la consulta del apuntador a la instancia, ésta internamente utilizará el operador “new” para solicitar memoria para liberarla inmediatamente. Creo que eso no tiene sentido hacerlo.
  • El otro es que habría que asegurarse de llamar al operador “delete” en cualquier circunstancia que saque al programa de la ejecución para que la memoria no quede reservada.

Solución al problema de liberar la memoria

C++ provee 3 tipos de apuntadores “inteligentes” (smart pointers) los cuales se encargan de recibir un puntero a un espacio de memoria reservada y cuando el objeto sale de ámbito y se invoca su destructor, manda a liberar la memoria del puntero el cual maneja. Éstos son:

  • unique_ptr: Un objeto de estos maneja un apuntador y lo liberará cuando éste se destruya, no admite copias.
  • shared_ptr: Hace el mismo trabajo que unique_ptr con la salvedad de que se admiten copias y la memoria será liberada sólo cuando la última copia del shared_ptr sea destruída.
  • weak_ptr: Éstos sólo pueden existir como copia de un shared_ptr, la destrucción de un weak_ptr no afecta a los shared_ptr que mantengan copias del apuntador, sin embargo, cuando el último shared_ptr es destruído todas las copias de weak_ptr existentes quedarán inconsistentes.

Como el Singleton maneja una sola instancia, entonces decidí utilizar el unique_ptr, por lo que el apuntador a la instancia lo definí de esta forma:


static std::unique_ptr<Singleton> instance;

Y el método que retorna el apuntador a la instancia queda de la siguiente manera:


static Singleton * get_ptr_instance()
{
  if (instance.get() == nullptr)
    instance = std::unique_ptr<Singleton>(new Singleton);
  return instance;
}

Generalización del Singleton

En algunas aplicaciones que he desarrollado, he tenido que programar dos o tres diferentes clases bajo este patrón. Y es realmente fastidioso tener que programar el mismo modelo para cada una de éstas, así que decidí generalizarlo.

Mi primer intento de generalización fue crear una clase llamada puramente Singleton y que cualquier clase que tuviese este patrón heredará de ésta. El problema con este modelo fue que solamente heredaba la variable estática de instancia, tenía igualmente que escribir todos los constructores y los metodos que retornan las referencias para hacer el respectivo casting de clase padre a clase hija, pues al llamar a get_instance() me retorna un Singleton y allí no se manejan las variables y métodos de la clase hija.

En un segundo intento (y con este me quedé) la programé (digamos) a la inversa. Programé un Singleton que deriva de cualquier clase que requiera ser usada bajo este patrón. Así, cada vez que quiero reutilizar el patrón, lo que hago es escribir una clase con sus atributos y métodos (por ejemplo una clase llamada Mi_Singleton_Base) y debajo de toda la definición escribo la siguiente línea:


using Mi_Singleton = Singleton<Mi_Singleton_Base>

Así cada vez que quiera usarla, lo hago de la siguiente manera:


Mi_Singleton & ms = Mi_Singleton::get_instance();

Referencias:

Patrones de Diseño
Bjarne Stroustrup, The C++ Programming Language 4th ed

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Posted in C++, Patrones de diseño, Programación, Programación Genérica Tagged with: , , , ,

Analizando las minas explosivas (continuación)

Posted on by remmurd — No Comments ↓

En el post anterior hablé sobre una posible estructura de datos para representar el tablero de este juego. Ahora veamos como hacerle una interfaz gráfica.

La interfaz de la que pienso hablar es de la que yo implementé con la biblioteca de Qt4 para C++.

Lo primero que vamos a crear es un panel de juego, el panel de juego es la ventana en donde queremos dibujar el tablero de juego y programar las interacciones sobre el mismo.

Para crear el panel nos valemos de la clase QWidget definida en Qt que representa una ventana básica la cual puede ser colocada dentro de otra ventana. Para esto entonces creamos una clase a la que llamaremos Game_Panel que deriva de QWidget:

class Game_Panel : public QWidget
{
  Matrix * matrix;
  bool finished;
  //...Operaciones públicas de la clase Game_Panel
};

Como se puede observar la clase contiene como atributos un puntero a un objeto de la clase Matrix (la que definimos en el post anterior) y una variable booleana que permite saber si el juego ya finalizó o no.

En este panel se manejan 3 señales, las señales son un mecanismo que tiene Qt que permite “lanzar avisos al aire”, es decir, se puede emitir cuando ocurra algún evento que quizás interese ser capturado (que otros objetos se enteren que ocurrió) para efectuar alguna acción al respecto desde otra parte.

las señales que se definen acá son:

signals:
  win();
  lost();
  flags_changed();

Entre las operaciones tenemos la de inicialización del panel la cual recibe como parámetros las dimensiones del tablero y la cantidad de minas que tendrá, el prototipo es el que sigue:

Game_Panel(const size_t & w, const size_t & h, const size_t & mines);

Y la implementación da memoria a un objeto de tipo Matrix con los atributos pasados como parámetro y también da un tamaño al panel de las dimensiones de la matriz multiplicado por una escala que viene dada por el tamaño al que se quiera dibujar cada casilla del tablero (en nuestro caso el valor es 20 definido en la macro SCALE).

La segunda operación que vamos a definir es la que dibuja el tablero en el panel, para esto sobreescribimos un método virtual que está en la clase QWidgwet que tiene el siguiente prototipo:

void paintEvent(QPointEvent *);

Éste es un método que es invocado automáticamente al abrir el panel y al hacer un llamado explícito al método repaint() de la ventana se activa una bandera para que Qt sepa que debe mandar a redibujar el panel.n Para la implementación del método de dibujo contamos con un directorio (dentro de nuestro directorio de proyecto) llamado “images” el cual, como se puede intuir, contiene las imágenes que utilizamos en el juego. Para el tablero están las imágenes de cada número mostrado al destapar casillas nombradas como su número con formato png (ej: 1.png contiene el valor de casilla 1), la que al destapar se muestra vacía se llama 0.png, la que representa una casilla tapada se llama Cuadro.png, la que representa una casilla tapada con bandera se llama Bandera.png, entonces la implementación del método de dibujo es como sigue:

void paintEvent(QPaintEvent *) // Como no usare el objeto QPaintEvent dentro lo dejo sin nombre para que el compilador no arroje advertencias de variable nunca usada
{
  QPainter painter(this);
  // Iterara sobre la matriz
    // Por cada paso de iteración
    QPixmap image;
    //Verificamos el estado de la casilla actual, s = 'c' en images cargamos la imagen Cuadro.png, si es bandera cargamos la imagen Bandera.png
    //Si no es ninguno de los casos anteriores, entonces significa que la casilla está destapada, así que verificamos el caracter y cargamos la imagen correspondiente al valor de la casilla (del 0 al 9 o mina en caso de ser *)
    //Luego mandar a pintar la imagen en la posición (i, j) actual de la matriz multiplicada por la escala para que se desplace el dibujo y no se monten las imágenes encima de las otras
  painter.drawPixmap(j * SCALE, i * SCALE, SCALE, SCALE, image);
  //Fin de la iteración sobre la matriz
}

Se instancia un objeto de tipo QPainter que es la clase que se encarga de hacer dibujos en el panel (más detalles en otros post futuros). Luego usamos un objeto de tipo QPixmap (usamos este tipo porque es al que yo puedo mandar a dibujar del tamaño que yo quiera en el momento de dibujarlo). El método que me permite cargar una imagen en el objeto QPixmap es load (ej: image.load(“images/1.png”)) El cual recibe como parámetro la ruta de la imagen. El método drawPixmap de la clase QPainter recibe como parámetros la posición de la imagen (x, y), las dimensiones de la imagen (w, h) y el objeto de tipo QPixmap a dibujar, la razón por la que se multiplica por la escala es porque la imagen se va a dibujar de tamaño 20 x 20 y los valores (i, j) representan posiciones en la matriz por lo que para i = 0 y j = 0, la imagen se va a dibujar en la posición (0, 0) del panel y para la posición (1, 0) de la matriz se va a dibujar en la posición (0, 20) del panel para respetar el ancho de tamaño 20 de la imagen anterior).

Ahora vamos a definir la operación de interacción del jugador con el tablero, para eso sobreescribimos un método virtual de la clase QWidget llamado mousePressEvent el cual es invocado automaticamente al recibir cualquier señal de click del mouse, el prototipo es como sigue:

void mousePressEvent(QMouseEvent *);

En este caso si nos interesa usar el objeto de tipo QMouseEvent, este objeto que lleva como parámetro contiene información como las coordenadas del panel en donde se hizo el click, el botón con el cual se hizo click, etc. y esto nos será realmente útil. La implementación del método es como sigue:

void mousePressevent(QMouseEvent * evt)
{
  // Si la variable finished esta en true retorno
  // Obtengo la posicion del panel en donde se hizo click
  QPoint p = evt->pos();
  // Convierto la posicion dada a posiciones en la matriz, si al dibujar multiplico por la escala, al dividir y truncar el resultado a un numero entero (OJO no es redondear) me lleva a la posicion en la matriz.
  const size_t j = size_t (p.x() / SCALE);
  const size_t i = size_t (p.y() / SCALE);
  // Pregunto si el boton fue el derecho
  if (evt->button() == Qt::RightButton)
    {
      //Hago el llamado de la operación flag de la clase Matrix en la posición (i, j)
      //Emito la señal de que las banderas cambiaron (emit flags_changed()).
    }
// Si no es el botón derecho, pregunto si es el botón izquierdo
  else if (evt->button() == Qt::LeftButton)
    {
      // Aqui hay dos casos
      // Si la pocisión al que le hace click el usuario tiene una mina y no tiene bandera entonces se invoca a la operacion discover_all_mines de la clase Matrix, coloca el juego como terminado (finished = true) y emite la señal de perdió (emit lost()).
      // En caso contrario mando a destapar la casilla invocando al método discover de la clase Matrix e igualo mi variable de finalización a lo que retorna la operación are_uncover_all de la clase Matrix, si queda en true entonces emito señal de ganar (emit win()) sino sigo mi juego normal
    }
}

La otra operación importante de mencionar es reinit la cual libera la matriz existente, pide memoria para una nueva, coloca a finished en false y llama al metodo repaint.

…

Como podemos haber visto en otras implementaciones de este juego, existe una cara arriba de nuestro panel la cual, clásicamente, tiene unos lentes de sol, cuando el jugador gana ella se pone feliz, cuando el jugador pierde ella llora o se pone triste, y al hacerle click el juego se reinicia. Veamos como se implementa.

Definiremos un QWidget para pintar la cara al que llamaremos Smile (lo siento, fue lo que se me ocurrió) que tiene como único atributo un objeto de tipo QPixmap.

class Smile : public QWidget
{
  QPixmap image;
  //...Operaciones públicas y privadas de la clase Smile
};

En esta clase tambien se define una se&ntildeal para emitir a la que llamaremos smile_clicked la cual vamos a emitir al momento de hacerle click. También se definen dos tipos de operaciones especiales llamadas slots, los slots son unos métodos especiales que pueden o no recibir parámetros pero siempre retornan void. El caso especial de estos métodos es que ellos pueden ser conectados con alguna señal para que el sistema lo invoque automáticamente una vez que una señal es emitida pero también pueden ser invocados como los métodos comunes (nombre_objeto.metodo_slot()).

Las señales y los slots son los siguientes:

signals:
  void smile_clicked();
public slots:
  void sad();
  void happy();

Aquí definimos una operacion privada llamda normal la cual internamente manda a cargar en image la imagen de la cara con lentes almacenada en el directorio images (image.load(“images/lentes.png)) y repinta el panel. En el constructor lo primero que hacemos es invocar a la funcion normal() para que se inicie con la imagen con lentes.

Análogamente los métodos de tipo slot sad y happy hacen lo mismo que normal pero con las imágenes triste.png y feliz.png respectivamente.

El médoto paintEvent manda a pintar la imagen en la posición (0, 0) con su tamaño (que en este caso es 40) y el método mousePressevent lo que hace es que invoca al método normal nuevamente y emite la señal smile_clicked().

…

Ahora si vamos a unir todo en un solo esqueleto de juego.

Para eso crearemos una clase llamada Game_Frame basada tambien en QWidget la cual tiene como atributos un Game_Panel, un Smile y una etiqueta que esta siempre mostrando cuantas banderas se han colocado sobre el maximo que se pueden colocar. En este ejemplo no hay un módulo que permita cambiar el tamaño del tablero y la cantidad de minas dinámicamente por lo que también son atributos de esta clase las dimensiones del tablero y la cantidad de minas que va a tener.

class Game_Frame : public QWidget
{
  Game_Panel panel;
  Smile smile;
  QLabel lbl_flags;

    void init_gui();

    size_t h;
    size_t w;
    size_t m;
};

Vamos a tener un a operación privada llamada init_gui() que es la que se va a encargar de armar el esqueleto del juego organizadamente y se implementa como sigue:

void init_gui()
{
  QVBoxLayout * vlayout = new QVBoxLayout;
  QHBoxLayout * hlayout1 = new QHBoxLayout;
  hlayout1->addWidget(&smile);
  vlayout->addLayout(hlayout1);
  QHBoxLayout * hlayout2 = new QHBoxLayout;
  hlayout2->addWidget(&panel);
  vlayout->addLayout(hlayout2, 1);
  lbl_flags.setFixedSize(100, 20);
  QHBoxLayout * hlayout3 = new QHBoxLayout;
  hlayout3->addWidget(&lbl_flags, 1);
  vlayout->addLayout(hlayout3, Qt::AlignCenter);
  setLayout(vlayout);
}

Ahora veamos los detalles.

Un Layout es un tipo que modela marcos que permiten la organización de Widgets (en general) dentro de otro Widget (los botones, radiobuttons, checkboxes, etc. son basados en QWidget). Aquí utilizaremos dos tipos, horizontales y verticales, ellos permiten añadirle widgets y otros layouts y se añadiran en el orden en que se programen. Ejemplo:

QLabel * label1 = new QLabel("label 1");
QLabel * label2 = new QLabel("label 2");
QLabel * label3 = new QLabel("label 3");

Si los anadimos en un QHBoxLayout (layout horizontal) seria algo como esto:

QHBoxLayout layout;

layout.addWidget(label1);
layout.addWidget(label2);
layout.addWidget(label3);

El resultado es este:

+-------+
|label 1|
|label 2|
|label 3|
+-------+

Si por el contrario es vertical sería así:

QVBoxLayout layout;

layout.addWidget(label1);
layout.addWidget(label2);
layout.addWidget(label3);

El resultado es este:

+-----------------------+
|label 1 label 2 label 3|
+-----------------------+

Nota: Los marcos realmente no se ven, los dibujé como referencia solamente para que se entienda.

Entonces en nuestro caso se instancia uno vertical que es el principal y un horizontal por cada elemento del juego, al primer horizontal le añadimos la cara y este es añadido en el vertical, al segundo horizontal le añadimos el panel y este es añadido al vertical y al tercer horizontal le añadimos la etiqueta y este es añadido al vertical.

En esta clase definimos dos slots, uno para reiniciar el juego cuando el objeto smile emita su señal de click y otro de cambiar la información de las minas en la etiqueta cuando el panel emita la señal flags_changed.

public slots:
  void reinit_game();
  void change_mines_info();

Las implementaciones son así:

void change_mines_info()
{
  //Asignar a la etiqueta lbl_flags el texto "Minas: " y concatenerle la cantidad de banderas que tiene le matriz actualmente / la cantidad de minas totales.
}

void reinit_game()
{
  // Invocar al metodo reinit del panel con parametros w, h, m e invocar a change_mines_info para que se reinicie la etiqueta.
}

El constructor se encarga entonces de invocar al metoro init_gui() y de establecer las conexiones entre signals y slots, la implementación es la siguiente:

Game_Frame()
{
  init_gui();
  connect(&panel, SIGNAL(win()), &smile, SLOT(happy()));
  connect(&panel, SIGNAL(lost()), &smile, SLOT(sad()));
  connect(&smile, SIGNAL(smile_clicked()), this, SLOT(reinit_game()));
  connect(&panel, SIGNAL(flags_changed()), this, SLOT(change_mines_info()));
}

connect es la función que permite conectar un signal con un slot, una vez que se establece dicha conexión, al emitirse una señal conectada, se ejecutará la acción programada en el slot que se le conectó a dicha señal. los parámetros que recibe connect son: puntero al objeto que emite la señal, la macro SIGNAL con el nombre se la señal que se quiere, puntero al objeto que esta interesado en captar la señal, la macro SLOT con el nombre del slot que nos interesa ejecutar al ocurrir la señal.

Ya teniendo esto, tenemos el juego funcional.

P.S.: Las implementaciones de los códigos mostradas acá son básicas, más que todo para entendimiento. Los detalles de la implementación están en el código fuente disponible para revisión y/o descarga en: https://github.com/R3mmurd/Mines

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Posted in C++, Programación, Qt, Videojuegos Tagged with: , , ,

Analizando las minas explosivas

Posted on by remmurd — No Comments ↓

Cuando me inicié en el mundo de la programación de juegos, lo primero que se me ocurrió modelar fue el famoso juego “Buscaminas”.

Para programar este juego lo primero que hice fue entenderlo. El juego consiste en lo siguiente:

-Un tablero de N filas por M columnas en las que hay un numero K de minas distribuidas aleatoriamente.
-La finalidad es destapar todas las casillas excepto las que tienen minas, una vez lograda esa misión, se gana el juego.
-Se tiene una opción de colocar una bandera en donde se cree que pueda existir una mina, de modo que ya el usuario sepa que no debe hacer click en dicha casilla o que lo haga por accidente y pierda.
-Las casillas que no tienen minas tienen un número que representa la cantidad de minas que hay alrededor de ella (mas no indican donde están)
-Las casillas que no tienen ningún número no tienen ninguna mina alrededor.

Lo primero que voy a escribir es como modelé el tablero.

La estructura de datos natural que permite representar un tablero es un arreglo bidimensional (también llamado matriz) de dimensiones N x M, que podría ser de caracteres, pero para nuestro efecto la haremos un poco más compleja, en cada posición de la matriz almacenaremos un caracter y un estado lo cual lo podemos representar en lenguaje C++ de la siguiente manera:

struct Box
{
  char s;
  char c;
};

Donde ‘s’ es el caracter que representará el estado de la casilla (s de status) y ‘c’ el caracter que indica que es lo que hay en la casilla (c de character), los valores que vamos a usar para el caracter son los numeros del ‘0’ al ‘8’ (ambos inclusive) y el ‘*’ para representar una mina y para el estado usaremos las iniciales del nombre de cada estado en ingles, es decir ‘c’ de covered (cubierta), ‘u’ de uncovered (descubierta) y ‘f’ de flag (bandera). Los valores iniciales de Box son s = ‘c’ y c = ‘0’.

Para modelar el tablero entonces definiremos una clase que contiene una matriz dinámica de objetos de tipo Box, las dimensiones de la matriz, cuantas minas tiene el tablero, cuantas banderas se han colocado y cuantas casillas se han destapado.

class Matrix
{
  Box ** matrix;
  size_t w;
  size_t h;
  size_t mines;
  size_t flags;
  size_t uncovered_boxes;
  //...Operaciones privadas y públicas de la clase Matrix
};

Teniendo esto definamos las operaciones que se efectúan en la matriz.

Lo primero en que normalmente pensamos es en una operación de inicialización, es decir, el constructor de la clase, pero para que el constructor arme el tablero, nos valdremos primero de una operación privada a la que llamaremos inc_mines_around(i, j) que se encargará de incrementar el número de minas alrededor de una casilla dada.

El prototipo es como sigue void inc_mines_around(const size_t & i, const size_t & j) y lo que hace es que para todas las posiciones alrededor a (i, j), es decir (i – 1, j – 1), (i – 1, j), (i – 1, j + 1), (i, j – 1), (i, j + 1), (i + 1, j – 1), (i + 1, j), (i + 1, j + 1), verificará que sea una posición válida en la matriz de ser así, entonces incrementa en 1 el valor del caracter de la misma.

Entonces el constructor de Matrix es como sigue:

Matrix(const size_t & w, const size_t & h, const size_t & mines);

Donde w define el ancho que tendrá la matriz, h la altura y mines la cantidad de minas que tendrá el tablero.

La inicialización entonces consiste en dar memoria a la matriz con las dimensiones deseadas, hacer una iteración desde 0 hasta mines, por cada paso en la iteración se genera una posición aleatoria (valiéndonos del generador de números aleatorios de GSL) y colocando un valor c = ‘*’ en la posición dada e invocando a la función inc_mines_around en dicha posición.

Otra operación útil es flag(i, j) la cual coloca o quita una bandera en la posición (i, j) pasada como parámetro, lo primero que hace es validar que no se encuentre ya destapada la casilla, de ser así no hace nada, en caso de estar tapada ve el estado actual si s = ‘f’ entonces hace s = ‘c’ y decrementa el valor de flags en 1 y en caso contrario, si flags = mines entonces no hace nada, sino hace s = ‘f’ e incrementa el valor de flags en 1.

La operación de descubrir una casilla tiene un detalle importante, resulta que si el valor de una casilla esta comprendido entre ‘1’ y ‘8’, la destapamos y ya, pero cuando es un ‘0’ (queriendo decir que no tiene minas alrededor) no tiene sentido para el usuario tener que destapar manualmente todo el contorno de la casilla porque ya sabe que no hay minas alrededor, así que ese proceso se automatiza.

La operación se implementa como sigue

void discover(const size_t & i, const size_t & j)
{
  // Validar que la posicion (i, j) sea valida en la matriz, de no ser asi retornar
  // Verificar el estado de la posicion (i, j), si esta descubierta o tiene bandera retornar
  // Hacer para la posicion (i, j) c = 'u'
  // Hacer el llamado recursivo para todo el entorno de la matriz si c = '0'
  if (matrix[i][j].c == '0')
    {
      // Llamada recursiva para cada casilla que lo rodea
      discover(i - 1, j - 1);
      discover(i - 1, j);
      discover(i - 1, j + 1);
      discover(i, j + 1);
      discover(i + 1, j + 1);
      discover(i + 1, j);
      discover(i + 1, j - 1);
      discover(i, j - 1);
    }
}

También existe una operación que destapa a todas las minas (útil para mostrar todas las minas del tablero cuando se pierde) que consiste en iterar sobre la matriz colocándole el valor s = ‘u’ a cada casilla que contenga mina y no tiene bandera y una operación que verifica si se han destapado todas las casillas posibles y retorna verdadero en caso de que así sea y falso en caso contrario, se implementa verificando si la cantidad de casillas descubiertas es igual a la cantidad de casillas del tablero menos la cantidad de minas.

En el siguiente post voy a escribir acerca de una interfaz gráfica para desarrollar el juego.

Los códigos fuentes del juego están disponibles en: https://github.com/R3mmurd/Mines

Nota: En el código fuente hay algunas diferencias respecto a la explicación acá
en la implementación de Box, sin embargo tienen el mismo significado.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Posted in C++, Programación, Videojuegos Tagged with: , ,