Aspectos funcionales
La idea es realizar un juego de tres en raya utilizando la matriz de 3x3 leds en combinación con la matriz de 3x3 pulsadores descritas ambas en post anteriores. Esta implementación inicial tiene las siguientes características y limitaciones:
- El microcontrolador utiliza un algoritmo tonto para realizar movimientos: elige aleatoriamente sobre qué celda jugar en cada turno.
- Siempre comienza jugando el microcontrolador.
- En lugar de círculos y aspas utilizamos la marca “luz fija” y “luz parpadeante”. El microcontrolador juega siempre con “luz parpadeante”.
- En cuanto el juego termina (ya sea porque gana el microcontrolador, porque gana el jugador o porque quedan en tablas), el juego se para.
El funcionamiento es el siguiente:
- Tras el reset, el microcontrolador mueve y marca una casilla del tablero (el microcontrolador siempre juega con la marca “luz parpadeante”).
- El microcontrolador espera a que el jugador humano mueva activando el pulsador correspondiente a la casilla que quiere marcar.
- Al activar el pulsador, se marca el led correspondiente como “luz fija” e inmediatamente después, el microcontrolador vuelve a mover.
Así sucesivamente hasta que gane uno de los dos jugadores o el juego quede en tablas. Como se puede adivinar, al ser el jugador de la máquina un jugador “tonto” que elige sus movimientos de forma aleatoria, es muy fácil ganar :-). En sucesivas versiones intentaré ir mejorando la “inteligencia” del microcontrolador.
Diagrama de clases
Las principales clases serían las siguientes:
Game: Se encarga de la mecánica abstracta de cualquier juego de dos jugadores, los turnos, quién gana, etc.
GameBoard: Tablero de cualquier juego (abstracto).
TTTGameBoard: Tablero del juego del tres en raya.
TTTLedGameBoard: Tablero del juego del tres en raya especializado en visualizar su estado en la matriz de leds.
GamePlayer: Jugador de cualquier juego (abstracto).
TTTGamePlayer: Jugador del juego del tres en raya.
TTTRandomGamePlayer: Jugador “tonto” del tres en raya. Elige los movimientos aleatoriamente.
TTTHumanGamePlayer: Jugador humano del tres en raya. Elige los movimientos leyéndolos de la matriz de pulsadores.
A continuación, se puede ver la rutina principal. Se utilizan dos estados de juego ("jugando" y "terminado"):
#include "util.H" #include "Timer.H" #include "MyLedMatrixManager.H" #include "MyKeyMatrixManager.H" #include "TTTRandomGamePlayer.H" #include "Game.H" #include "TTTHumanGamePlayer.H" #include "TTTLedGameBoard.H" using namespace std; using namespace avelino; #define GAME_STATUS_PLAYING 1 #define GAME_STATUS_FINISHED 2 MyLedMatrixManager ledMatrixManager; MyKeyMatrixManager keyMatrixManager; TTTRandomGamePlayer p1; TTTHumanGamePlayer p2; Game g; TTTLedGameBoard board; uint8_t gameStatus; int main() { Timer::init(); ledMatrixManager.init(); board.init(ledMatrixManager); p1.init(1, board); p2.init(2, board); keyMatrixManager.init(p2); g.init(p1, p2, board); gameStatus = GAME_STATUS_PLAYING; while (true) { ledMatrixManager.run(); if (gameStatus == GAME_STATUS_PLAYING) { if (!g.isFinished()) { keyMatrixManager.run(); g.run(); board.show(); } else gameStatus = GAME_STATUS_FINISHED; } else if (gameStatus == GAME_STATUS_FINISHED) { // } } return 0; }
Consideraciones adicionales a tener en cuenta
La generación de números aleatorios
Para la implementación de la clase TTTRandomGamePlayer (el jugador “tonto”) se necesitan las funciones “srand” y “rand” de la librería estándar de C (u otras similares). En lugar de la clásica solución
srand(time(NULL));
que no puede ser utilizada en este caso ya que el sistema carece de reloj de tiempo real, opté por utilizar como semilla aleatoria la lectura de una de las entradas analógicas del microcontrolador que se encuentra sin cablear (al aire):
ADCManager::init();
srand(ADCManager::get(0));
Siendo ADCManager una clase con dos métodos estáticos: “init” inicializa el subsistema de conversión analógico-digital del microcontrolador y “get” lee la entrada analógica que se le pasa por parámetros.
Evaluación del tablero
La evaluación del tablero del tres en raya para determinar quién ha ganado tras cada movimiento la he implementado basándome en el algoritmo descrito en el documento “A general algorithm for tic-tac-toe board evaluation” del profesor Aaron Gordon (departamento de ciencias de la computación y sistemas de información de la universidad de Fort Lewis, Estados Unidos). Dicho algoritmo organiza la cuadrícula de 3x3 en forma de cuadrado mágico: un cuadrado en el que la suma de las columnas, las filas y las diagonales siempre da el mismo resultado. El algoritmo es muy ingenioso y eficiente y para entenderlo bien vale la pena leerse el artículo (aunque está en inglés, es muy sencillo de leer y se entiende perfectamente). De todas formas, en un futuro post abordaré el estudio de este interesante algoritmo.
En la sección soft puede descargarse el código fuente del proyecto.
[ 2 comentarios ] ( 2108 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 1917 )En el post anterior presenté el desarrollo para Arduino de una matriz de leds utilizando la técnica de la multiplexación. En este post desarrollaré el mismo concepto pero esta vez para leer un teclado en forma de matriz de pulsadores.
Para realizar la matriz de pulsadores he distribuido, de manera similar a los leds, 9 pulsadores en una configuración de 3x3.
Como se puede ver en la figura, las tres columnas están conectadas directamente a tres salidas digitales del procesador (en este caso son las etiquetadas como A0, A1 y A2 del Arduino) mientras que las filas tienen en este caso una configuración un poco más compleja. Cada fila está equipada con una resistencia de pull-up de 1K y con un condensador de 1u en pull-down. Como cada fila está configurada como entrada, es necesario poner resistencias en pull-up para garantizar que se lea un 1 (5 voltios) cuando no haya nada pulsado. El condensador de 1u hace de filtro pasivo paso-bajo ante los posibles rebotes mecánicos de los pulsadores.
De forma similar a como hacíamos con la matriz de leds, vamos haciendo un barrido de cada una de las columnas (vamos poniéndolas a 0) y vamos comprobando el valor de todas las filas para cada activación de columna. En este caso, aunque hemos incluido un condensador antirrebote, no hay que fiarse y es mejor habilitar un mecanismo por software para minimizar el impacto del posible rebote de los pulsadores:
inicialización:
estado := SELECCIONAR_COLUMNA
columna := 0
fila := 0
ejecución:
si (estado = SELECCIONAR_COLUMNA) entonces
activarColumna(columna)
cargarContadorDescendenteTimer(10ms)
estado := ESPERAR_COLUMNA
en otro caso, si (estado = ESPERAR_COLUMNA) entonces
si (contadorTimer = 0) entonces
estado := LEER_FILAS
fin si
en otro caso, si (estado = LEER_FILAS) entonces
fila := 0;
encontrada := false
mientras ((fila < 3) AND (no encontrada)) hacer
si (activadaFila(fila)) entonces
encontrada := true
en otro caso
fila := fila + 1
fin si
fin mientras
si (encontrada) entonces
// NOTIFICAR: SE HA PULSADO LA TECLA (fila, columna)
estado := ESPERAR_REBOTE
cargarContadorDescendenteTimer(20ms)
en otro caso
columna := ((columna + 1) % 3)
estado = SELECCIONAR_COLUMNA
fin si
en otro caso, si (estado = ESPERAR_REBOTE) entonces
si (contadorTimer = 0) entonces
estado := ESPERAR_LIBERACIÓN
fin si
en otro caso, si (estado = ESPERAR_LIBERACIÓN) entonces
si (no activadaFila(fila)) entonces
// NOTIFICAR: SE HA LIBERADO LA TECLA (fila, columna)
estado := ESPERAR_REBOTE2
cargarContadorDescendenteTimer(20ms)
fin si
en otro caso, si (estado = ESPERAR_REBOTE2) entonces
si (contadorTimer = 0) entonces
columna := 0
estado := SELECCIONAR_COLUMNA
fin si
fin si
inicialización se ejecutará al principio del programa mientras que ejecución deberá ejecutarse continuamente en el bucle principal de la aplicación.
activarColumna(c) pone a 0 (0 voltios) la columna “c” y pone a 1 (5 voltios) el resto de columnas. activadaFila(f) devuelve “true” si la fila “f” está a 0 (hay un pulsador presionado que está poniendo a 0 voltios esa fila).
En cuanto se detecta una tecla pulsada se notifica y se espera un tiempo sin leer nada (ESTADO_REBOTE), cumplido ese tiempo, se espera a que la tecla pulsada se libere y en cuanto se libera se vuelve a esperar un tiempo sin leer nada (ESTADO_REBOTE2). Estos dos tiempos “muertos” son cortos pero necesarios para proteger a la aplicación de pulsaciones espúreas en caso de producirse rebote mecánico en los pulsadores.
He colgado un pequeño vídeo en el que se puede ver tanto la matriz de leds como la matriz de pulsadores en acción. Por ahora no hace nada del otro mundo: Cada tecla está vinculada a un led, lo enciende o lo apaga cuando se pulsa (no es nada del otro mundo pero bueno, es una prueba de concepto :-) )
[ añadir comentario ] ( 1563 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 1862 )La matriz de leds es un mecanismo de salida muy utilizado en el ámbito de los microcontroladores ya que permite controlar una gran cantidad de leds con relativamente pocos pines. En este post describiré cómo he aplicado la multiplexación para incluir una matriz de leds en el Arduino. En un segundo post describiré cómo implementar un teclado mediante una matriz de pulsadores.
Para realizar la matriz de leds he distribuido 9 leds en una configuración de 3x3 como se indica en la figura:
Como se puede apreciar los cátodos de los 9 diodos están conectados a las líneas verticales, que llamaremos columnas, mientras que los ánodos de los 9 diodos están conectados a las líneas horizontales, que llamaremos filas. Cada columna está conectada directamente a una salida digital mientras que cada fila está conectada mediante una resistencia a una salida digital. En total necesitamos 6 salidas digitales (3 + 3) para controlar los 9 leds.
Si asumimos que la información de iluminación la tenemos almacenada en una matriz booleana:
#define APAGADO false #define ENCENDIDO true bool leds[3][3]; // [0..2][0..2]
El procedimiento de multiplexación es muy sencillo y puede definirse, en pseudocódigo, como sigue:
inicialización:
columna := 0
cargarContadorDescendenteTimer(10ms)
ejecución:
si (contadorTimer = 0) entonces
activarColumna(columna)
para fila := 0 hasta 2 hacer
v := leds[fila][columna]
activarFila(fila, v)
fin para
columna := ((columna + 1) % 3)
cargarContadorDescendenteTimer(10ms)
fin si
inicialización se ejecutará al principio del programa mientras que ejecución deberá ejecutarse continuamente en el bucle principal de la aplicación.
activarColumna(c) debe encargarse de poner a 0 (0 voltios) la columna “c” y de poner a 1 (5 voltios) el resto de columnas. Poner a 0 voltios la columna “c” la “activa” en el sentido que los tres leds colocados a lo largo de ella son susceptibles de ser polarizados y, por lo tanto de encenderse.
activarFila(f, v) debe encargarse de poner a 1 (5 voltios) la fila “f” si “v” es “true” y de ponerla a 0 (0 voltios) si “v” es “false”. Poner a 5 voltios la fila “f” enciende el led localizado en esa columa “f” y en la columna previamente activada.
Con una adecuada temporización, la sensación es de que no hay parpadeo. Ya tenemos a nuestra disposición un pequeño display de 9 luces utilizando tan solo 6 salidas digitales. Este tipo de multiplexación puede ser ampliado, obviamente, a cualquier configuración (por ejemplo 3 x 4 = 12 luces con 3 + 4 = 7 salidas digitales).
En mi caso particular, he mejorado las características de la matriz incluyendo un tercer estado de “parpadeo”. Para este caso, partiendo del pseudocódigo anterior, tan solo hay que hacer algunos pequeños cambios:
Definimos la matriz de leds como multivaluada:
#define APAGADO 0 #define PARPADEANTE 1 #define ENCENDIDO 2 uint8_t leds[3][3]; // [0..2][0..2]
Y utilizamos un timer adicional más lento para generar el parpadeo:
inicialización:
columna := 0
cargarContadorDescendenteTimer1(10ms)
cargarContadorDescendenteTimer2(500ms)
parpadeoEncendido := true
ejecución:
si (contadorTimer1 = 0) entonces
activarColuma(columna)
para fila := 0 hasta 2 hacer
aux := leds[fila][columna]
v := (aux == 2) OR ((aux == 1) AND parpadeoEncendido)
activarFila(fila, v)
fin para
columna := ((columna + 1) % 3)
cargarContadorDescendenteTimer1(10ms)
fin si
si (contadorTimer2 = 0) entonces
parpadeoEncendido := no parpadeoEncendido
cargarContadorDescendenteTimer2(500ms)
fin si
Ahora tenemos que cada led puede estar en tres estados: apagado, parpadeando o encendido.
Existen otras técnicas de multiplexado, como el Charlieplexing (http://en.wikipedia.org/wiki/Charlieplexing) con las que se consiguen controlar una mayor cantidad de leds con menos pines pero a costa de unos mayores requerimientos de hardware (el charlieplexing requiere más circuitería y que las salidas sean triestadas).
[ añadir comentario ] ( 1480 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 1805 )Programar el microcontrolador AVR el Arduino con el lenguaje Processing está muy bien y es una forma muy rápida de desarrollar aplicaciones sencillas. Sin embargo cualquiera que quiera hacer algo medianamente estructurado o complejo echará rápidamente de menos el C o el C++.
Lo cierto es que el toolkit que se instala con Arduino viene ya con una completa toolchain GNU de C y C++: El propio lenguaje Processing es una especie de "subconjunto" de C y lo que hace el IDE del Arduino no es otra cosa que traducir a C los sketchs que hacemos en lenguaje Processing.
Para hacer nuestro primer programita en C++ para el Arduino vamos a probar hacer una versión OOP del famoso parpadeo (
blink.cc):#include <avr/io.h> #include <util/delay.h> using namespace std; class Led { public: Led(); void on(); void off(); }; Led::Led() { // bit 7 el puerto C en modo salida DDRC |= 0x80; } void Led::on() { // bit 7 del puerto C a 1 PORTC |= 0x80; } void Led::off() { // bit 7 del puerto C a 0 PORTC &= 0x7F; } int main() { Led led; while (1) { led.on(); _delay_ms(250); led.off(); _delay_ms(250); } }
Hacer parpadear un led en C++ con OOP no deja de ser como matar moscas a cañonazos pero bueno, se trata de una prueba de concepto :-)
Para compilar el programita utilizamos la toolchain de GNU que ya viene con el software del Arduino:
PREFIJO_RUTA_BIN/avr-g++ -DF_CPU=16000000UL -mmcu=atmega32u4 -Os -c -o blink.o blink.cc PREFIJO_RUTA_BIN/avr-g++ -DF_CPU=16000000UL -mmcu=atmega32u4 -Os -o blink.elf blink.o PREFIJO_RUTA_BIN/avr-objcopy -O ihex blink.elf blink.hex
Utilizo la opción
-mmcu=atmega32u4 porque en mi caso concreto estoy utilizando un Arduino Leonardo, que posee un procesador ATmega32u4.Ahora sólo falta subir el fichero
hex al Arduino mediante la utilidad avrdude incluida en la toolchain de GNU. El Arduino cuando arranca permanece unos pocos segundos en modo "boot" a la espera de ver si desde un ordenador conectado por USB se le envía algún fichero hex para instalar y ejecutar. En caso de que no se le envíe nada en este modo, el procesador del Arduino pasa a ejecutar el código que contenga ahora mismo la flash interna. Si estando en modo "boot" le llega algún nuevo programa, lo escribe en la flash interna y a continuación lo ejecuta.Para poder cargar un fichero hex en el Arduino bastará con lanzar el siguiente comando inmediatamente después de hacer un reset:
PREFIJO_RUTA_BIN/avrdude -patmega32u4 -cavr109 -P/dev/ttyUSBXXX -b57600 -D -Uflash:w:blink.hex:i -C PREFIJO_RUTA_ETC/avrdude.conf
Algunos de los parámetros que le paso al
avrdude son específicos para Arduino Leonardo, en caso de usar otro modelo de Arduino hay que mirar qué parámetros son los adecuados. Nótese que el ejecutable avrdude no se encuentra en la misma carpeta que el fichero avrdude.conf. Hay que asegurarse de que se usan las rutas correctas y acordes a las carpetas de instalación del software del Arduino.Si en el Arduino se encuentra previamente cargado un sketch realizado con lenguaje Processing es posible cargar un nuevo fichero hex sin necesidad de reiniciar el Arduino: Basta con abrir el puerto serie USB y configurarlo a 1200 bps (sin necesidad de enviar ni recibir ningún byte) para que el Arduino pase a modo "boot", como si lo hubiésemos reiniciado (gracias a Nicholas Kell por esta info).
He aquí un programa de ejemplo, compilable en cualquier *nix, que realiza este "reseteo soft":
#include <stdio.h> #include <stdlib.h> #include <fcntl.h> #include <termios.h> #include <string.h> int main(int argc, char *argv[]) { struct termios tio; int fd; if (argc < 2) return 1; fd = open(argv[1], O_RDONLY | O_NONBLOCK); tcgetattr(fd, &tio); tio.c_cflag = CS8; cfsetspeed(&tio, B1200); tcsetattr(fd, TCSANOW, &tio); close(fd); return 0; }
De esta manera y, de forma genérica, el script
upload.sh podríamos dejarlo como sigue:#!/bin/sh ./reset $2 sleep 2 PREFIJO_RUTA_BIN/avrdude -patmega32u4 -cavr109 -P$2 -b57600 -D -Uflash:w:$1:i -C PREFIJO_RUTA_ETC/avrdude.conf
Invocándolo de la siguiente manera:
./upload.sh blink.hex /dev/ttyUSBXXX
Y voilà, ya tenemos nuestro primer led parpadeante hecho en C++ :-)
[ añadir comentario ] ( 2499 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 1846 )En 1961 el Lee C.Y. de los Bell Telephone Labs desarrolló un algoritmo muy sencillo y eficaz para el trazado de rutas sobre mallas de puntos. Este algoritmo es muy usado en la actualidad para el enrutado automático de las pistas de cobre en las placas de circuitos impresos.
El algoritmo, que parte de dos puntos que se desean conectar, se divide en dos pasos:
Paso 1. Se genera un frente de onda partiendo del punto origen de la ruta hasta tocar al punto destino. Este frente de onda se va extendiendo por la malla mediante un recorrido en amplitud marcando los puntos por los que va pasando y asignándoles valores cada vez mayores a medida que el frente de onda se aleja del punto origen.
A continuación puede verse cómo se propagaría el frente de onda desde el punto $o=(5, 5)$ y llega hasta el punto $d=(9, 9)$ sobre una malla de 11x11.
0 10 9 8 7 6 7 8 9 10 0
10 9 8 7 6 5 6 7 8 9 10
9 8 7 6 5 4 5 6 7 8 9
8 7 6 5 4 3 4 5 6 7 8
7 6 5 4 3 2 3 4 5 6 7
6 5 4 3 2 o1 2 3 4 5 6
7 6 5 4 3 2 3 4 5 6 7
8 7 6 5 4 3 4 5 6 7 8
9 8 7 6 5 4 5 6 7 8 9
0 9 8 7 6 5 6 7 8 d9 10
0 0 9 8 7 6 7 8 9 10 0
Paso 2. Se genera la ruta partiendo del punto destino y volviendo hacia atrás sobre las marcas generadas por el frente de onda de tal forma que cada punto sólo se conecta con otro que tenga una marca con un valor menor. Así hasta llegar al punto origen.
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
En pseudocódigo sería algo así:
Entrada:
M : Malla de puntos en la que cada punto tiene una marca (número) y un trazo
origen : Punto origen de la malla
destino: Punto destino de la malla
Salida:
La misma malla M con los puntos trazados uniendo origen con destino
Algoritmo:
cola := {}
meter(cola, origen)
poner todas las marcas de la malla a 0
poner_marca(M, origen, 1)
hacer
p := sacar(cola)
para cada punto q de M vecino de p, no marcado, ni trazado hacer
meter(cola, q)
poner_marca(M, q, obtener_marca(M, p) + 1)
fin para
fin hacer mientras ((cola no vacía) y (p != destino))
si (p == destino)
p := destino
poner_trazo(M, p)
mientras (p != origen) hacer
aux := punto de la vecindad de p con marca inferior a p y más cercano a origen
poner_trazo(M, aux)
p := aux
fin mientras
en otro caso
error: no hay ruta desde origen a destino
fin si
En la sección soft de la web puede descargarse una implementación en C++ que he hecho de este algoritmo. Como se puede apreciar la mayor carga de complejidad computacional recae en la primera parte, encargada de la propagación del frente de onda ya que se trata de un recorrido en amplitud.
El código de ejemplo en C++ genera una malla de 11 por 11 puntos e intenta trazar sobre ella 6 rutas. Las 5 primeras rutas se trazan mientras que para el último par de puntos el algoritmo no encuentra una ruta válida.
tracing from (5, 5) to (9, 9)... ok
tracing from (5, 10) to (9, 3)... ok
tracing from (0, 10) to (10, 6)... ok
tracing from (1, 1) to (1, 1)... ok
tracing from (0, 1) to (2, 1)... ok
tracing from (6, 8) to (3, 2)... no route found
output grid:
5 5 5 0 0 0 0 0 0 0 0
5 4 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 3 3 3
0 0 0 0 0 0 0 3 3 2 3
0 0 0 0 3 3 3 3 0 2 3
0 0 0 0 3 1 1 0 0 2 3
0 0 0 0 3 0 1 1 0 2 3
0 0 0 3 3 0 0 1 1 2 2
0 0 3 3 0 0 0 0 1 1 2
0 3 3 0 0 0 0 0 0 1 2
3 3 0 0 0 2 2 2 2 2 2
Como se puede ver es un algoritmo muy útil para el trazado automático de circuitos impresos.
[ 2 comentarios ] ( 1765 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 1877 )
Calendario
