- Introducción:
-
INFERNO, un sokoban para nuestro Spectrum
- Entradas
- Programemos un juego en C: Estructura básica planteada
- Programemos un juego en C (II): Estructura básica efectiva
- Programemos un juego en C (III): Retomando el tema
- Programemos un juego en C (IV): Compresión de datos, eliminado repeticiones simples
- Programemos un juego en C (V): Compresión de datos, técnicas mas eficientes
- Programemos un juego en C (VI): Compresión de datos, cambios de base
domingo, 11 de octubre de 2015
Programemos un juego en C: Indice
Estas son las entradas relacionadas con el tema:
Programemos un juego en C (IV): Compresión de datos, eliminado repeticiones simples
Vamos con un tema que parece auxiliar pero no lo es. Hoy día el manejar mas memoria, mas disco, mas procesador, mas interface gráfico no es problema en los juegos, no es como antes que buscábamos ahorrar al máximo, ya que no podíamos ampliar nada o casi nada. Por ello hay un aspecto que considerar, que es como guardar los datos de los niveles.
Parece una chorrada, pero en modo texto puro, un archivo con los 40 niveles del juego ocupa unos 12Kb. Parece poco, pero durante años tener de 1 a 8 Kb fue lo habitual. Un Spectrum de 16Kb nos deja 4Kb para la lógica del juego, y en un 48Kb (que también es la memoria libre habitual en los C64) ocupamos el 33% solo en eso. Por tanto hay que comprimir datos.
No voy a dar una explicación de los algoritmos mas usados de compresión, solo de los mas sencillos que son los que menos recursos requieren, y que en estos casos en que el conjunto de datos a comprimir consta de pocos caracteres son rápidos y eficientes, solo hay que darle un poco mas de vueltas a las cifras. Primero explicaré que un algoritmo de compresión que se puede revertir se llama sin pérdidas, pues recupera el original al 100%, RAR o ZIP son de este tipo. Los algoritmos que comprimen pero no es posible recuperar el original al 100%, por lo que realmente no se puede deshacer la compresión, se llaman con pérdidas. El formato jpg es así. La diferencia real es que los primeros guardan los pasos que usan junto a los datos comprimidos, de esta forma es posible deshacerlos, mientras que los segundo no lo hacen, pues buscan optimizar sin que se vea muy afectado el original.
Nosotros necesitamos compresión sin pérdidas, y dentro de ellos veremos los algoritmos de eliminación de repeticiones, el de codificación de pares y la recodificación binaria, métodos sencillos, rápidos de programar y de ejecutar, y lo que es mejor fáciles de entender.
En esta entrada empezaremos por los de eliminación de repeticiones. Para empezar hay que ver lo que debemos comprimir, por lo que veamos como son los niveles del sokoban, están almacenado como una serie de cadenas de caracteres, luego cada carácter se convierte en un elemento gráfico (se puede hacer de otra forma pero no viene al caso). Veamos los dos primeros niveles, donde "#" representa la pared, "$" la caja, "@" al jugador, el "." es el destino, "*" si el destino está ya ocupado por una caja, y "|" representa el fin de la línea. Una representación que sea visualmente bonita de las pantallas sería por ejemplo así:
##### |
# # |
#$ # |
### $## |
# $ $ # |
### # ## # ######|
# # ## ##### ..#|
# $ $ ..#|
##### ### #@## ..#|
# #########|
####### |
############ |
#.. # ### |
#.. # $ $ # |
#.. #$#### # |
#.. @ ## # |
#.. # # $ ## |
###### ##$ $ # |
# $ $ $ $ # |
# # # |
############ |Los 40 niveles clásicos en este formato ocupan 12.598 caracteres. La primera técnica básica, y muy evidente, es eliminar todo lo que no sea necesario, en nuestro caso los espacios por la derecha y el último salto de línea de cada nivel. Solo con esto lo dejamos en 10.492 caracteres, casi 2Kb. Con esto lo que pretendo que se entienda es que el programa lo queremos visualmente bonito, para que sea mas sencillo de entender, pero a veces es mejor ser mas práctico, el extremo es una página Web. Si eliminamos todos los saltos de línea y espacios por la izquierda y derecha no necesarios, podemos quitar a veces una cantidad importante de caracteres, que al navegador no le hacen falta para nada, de echo los elimina el. Esto hace que las páginas carguen un poco mas rápido.
#####|
# #|
#$ #|
### $##|
# $ $ #|
### # ## # ######|
# # ## ##### ..#|
# $ $ ..#|
##### ### #@## ..#|
# #########|
#######
############|
#.. # ###|
#.. # $ $ #|
#.. #$#### #|
#.. @ ## #|
#.. # # $ ##|
###### ##$ $ #|
# $ $ $ $ #|
# # #|
############ Ahora empezaremos las técnicas de compresión mas usadas y sencillas, no podemos usar compresores que necesiten esos recursos que nos pretendemos ahorrar, por tanto ni Lempel-Ziv ni KBG, vamos a los sencillos. Hay dos técnicas básicas, eliminar repeticiones y cambiar la codificación, la primera siempre funciona, la segunda depende mucho de los datos para que sea mas o menos eficiente, y en los juegos que tienen realmente pocas variaciones de elementos son eficientes. Veremos las mas sencillas.
Una técnica muy básica es que cuando existan caracteres repetidos, poner el carácter y el número de repeticiones, pensando que si son menos de 3 no merece la pena pues no ganas nada. Así ante la cadena "aaaaabbbbbbbbbbbbbccddddddd" podemos comprimirla usando "a5b13ccd7". Podemos usar notación prefija en la forma "5a13bcc7d". Esta técnica es buena cuando hay muchas repeticiones, que es nuestro caso, Se puede seguir optimizando usando hexadecimal, con lo que sería "a5bDccd7", así ganamos que las cifras hasta 15 ocupen un solo carácter, pero para poder usar esto debemos tener claro no confundir D con d. Yo para ahorrar tiempo de proceso para analizar la cadena, usaré una forma en la que los número sean de una cifra y donde uso 0 en lugar de 10, por lo que llegaremos a "a5b0b3ccd7". Como vemos no hay problema en tener dos grupos de b seguidas. Usando esta técnica, nos queda así:
4#5|
4# 3#|
4#$ #|
#3 $##|
# $ $ #|
#3 # ## # 3#6|
# 3# ## #5 ..#|
# $ $ 0..#|
#5 #3 #@## ..#|
4# 5#9|
4#7
#0##|
#.. # 5#3|
#.. # $ $ #|
#.. #$#4 #|
#.. 4@ ## #|
#.. # # $ ##|
#6 ##$ $ #|
# $ $ $ $ #|
# 4# 5#|
#0##Con esto solo los datos pasan a ocupar 7.925 caracteres, ya empieza a notarse, pero podemos seguir mejorándolo, buscaremos un método para reducir de 2 a 1 los caracteres que necesitamos. Se trata de usar una substitución de caracteres, reemplazando combinaciones de elementos repetidos por un solo carácter, con la condición de que este carácter no se use entre los que necesitamos. En nuestro caso voy a reemplazar cuando haya 15 repeticiones de un espacio por "A", 14 repeticiones por "B", 13 repeticiones por "C", y así hasta la "O" que reemplaza a un solo espacio. Con esta técnica y solo para los espacios nos quedamos en 8.427 caracteres. Como en mi caso cadenas de mas de 10 elementos seguido hay pocas, usaré la técnica empleando esta tabla:
10 " " = A, 9 " " = B, ... 1 " " = J
10 "#" = O, 9 "#" = P, ..., 1 "#" = X
10 "." = 0, 9 "." = 9, ... 1 "." = 1
Con esto solo los datos pasan a ocupar 6.179 caracteres, siendo muy rápido el descomprimirlos, quedando de esta forma
GT|
GXHX|
GX$IX|
IVI$W|
IXI$J$JX|
VJXJWJXHS|
XHXJWJTI2X|
XJ$I$A2X|
TJVJX@WI2X|
GXFP|
GR
OW|
X2IXFV|
X2IXJ$I$IX|
X2IX$UIX|
X2G@JWIX|
X2IXJXI$JW|
SJW$J$JX|
IXJ$I$J$J$JX|
IXGXFX|
IOWCon técnicas muy sencillas vemos que conseguimos reducir los datos de 12.598 iniciales, a 10.492 y dejarlos en 6.179, lo que representa un 49% de reducción.
De las técnicas de reducción por repeticiones no se puede ganar mucho mas espacio, para seguir aumentando la ganancia hay que usar otras técnicas mas eficientes, y en la siguiente entrada veremos como las codificaciones con diccionarios, que son las base del ZIP, RAR y similares, nos pueden permitir ganar aun más, sin necesidad de complicarnos mucho la vida en ellos.
sábado, 10 de octubre de 2015
Programemos un juego en C (III)
Como casi siempre, voy a rachas y ahora toca volver a la programación, que empecé y se quedó muerta.
Cambio un poco, ya no es lo mismo usar mi viejo y muy querido Turbo C que algo mas moderno y mucho mas cómodo (la edad me lleva a la comodidad). Al final usare el entorno de Visual Studio que es un muy buen IDE, pero con el lenguaje Visual C++ en lugar de mi querido Visual Basic o el C#, ya que así puedo migrar el programa a otro entorno mas fácilmente.
A pesar de la mala fama que tiene, Microsoft hace tiempo que lanza herramientas gratuitas de programación, hasta ahora en uno solo de los lenguajes del entorno, pero para Visual Studio 2015 ha sacado una versión gratuita del entorno completo llamada Community. Permite hacer casi todo lo que haces con la de pago, pero es para uso personal, no hay control de código fuente ni posibilidad de programación en equipo (es bonito ver como otro cambia una línea en tu programa y te aparece a ti en tu fuente, sin interferencias ni errores).
Volvamos a lo que ya estaba escrito, aunque use el Visual C++ el programa estará escrito en C estándar, y como el C++ es un superconjunto del C, poco hay que cambiar, detalles por comodidad como los comentarios con doble barra, o cambios necesarios como que definimos main como entera y cambiamos exit por return. Con esto podemos seguir adelante con el tema, ampliando los puntos en que pone el comentario // ++ que indica precisamente acciones a realizar. Conforme avanzamos ampliaremos las variables que necesitamos. Veamos la programación descendente, planteamos funciones para las cosas, aunque de momento no hagan nada, pero ya las vamos a ir completando. En este punto lo dejaremos así, mi intención es que presente una pantalla, y ya iremos ampliando:
// *******************************************************************
// INFERNO, un sokoban en C usando Visual Studio y Visual C++
// Jose Antonio Vaqué, octubre 2015
// *******************************************************************
#include <stdio.h>
// Constantes que usaremos
#define MAX_NIVELES 50
typedef enum { FALSE, TRUE } boolean;
typedef enum { N, S, E, O, F } Tecla;
// Estructura para un nivel del juego
typedef struct nivel {
int nro;
}NIVEL;
NIVEL niveles[MAX_NIVELES];
// Variables globales
int nivelactual;
Tecla tecla;
// Prototipos de funciones
void PrepararGlobales();
void PrepararNiveles();
void MontarNivel(int nro);
void PresentarNivel(int nro);
void LeerTeclado(Tecla *teclaleida);
int main() {
printf("Inferno");
PrepararNiveles;
PrepararGlobales;
boolean fin_juego = FALSE;
do {
MontarNivel(nivelactual);
boolean fin_nivel = FALSE;
do {
PresentarNivel(nivelactual);
LeerTeclado(&tecla);
// ++ Acción según tecla
pulsada
// ++ Verificar si se ha
completado el nivel
} while (!fin_nivel | !fin_juego);
if (!fin_juego) {
// ++ Mensaje de fin del
nivel
// ++ Aumentar nivel
}
else {
// ++ Mensaje fin del juego
}
} while (!fin_juego);
return 0;
}
void PrepararGlobales() {
nivelactual = 0;
}
void PrepararNiveles() {
}
void MontarNivel(int nro) {
}
void PresentarNivel(int nro) {
}
void LeerTeclado(Tecla *teclaleida) {
}Ahora ya tenemos la base, iré ampliando las funciones que he dejado solo definidas, y el programa irá creciendo. Cuando funcione en Windows, lo pasaremos a otras máquinas usando compiladores cruzados para el Z80, y veremos que lo que cambia de una máquina a otra es, principalmente, las rutinas gráficas, que como pienso dejar muy definidas en funciones aparte, es mas sencillo su cambio.
viernes, 9 de octubre de 2015
Vector Graphic, lo que un ama de casa aburrida puede hacer
Índices: El camino al O.P. Historia de la Informática
Esta es otra historia del momento, como casi todas las empresas de esa época la californiana Vector Graphics tiene una curiosa historia detrás. Podéis verla contada de forma mas bonita aquí, aunque yo aporto otros datos complementarios.
Bob Harp era un físico, casado en los 70 con Lore Harp, recién llegada de Alemania. Aunque tenía un titulo de antropología y dos hijas, Lore no era la típica ama de casa, necesitaba algo mas en su vida, y lo encontró junto a su amiga y vecina Calore Ely montando su propia empresa. Pero empecemos un poco antes.
Bob compra un ordenador, evidentemente el elegido no puede ser otro mas que el Altair 8800. Como sabemos, esta máquina había que montársela, y tenia fama de que la placa de memoria daba muchos problemas, y en esta unidad también fallaba la placa de memoria. Como pasó en otras ocasiones, en lugar de devolver la placa defectuosa decide reparársela el mismo, lo que le llevó a ver que era mejorable, y acabó desarrollando su propia placa de 8Kb de RAM.
Lore debió ponerse insoportable sin nada que hacer, y Bob le sugiere montar una empresa para vender su placa de memoria, lo que en ese momento era un buen mercado emergente, hay pocas tarjetas de ampliación de calidad en ese momento. Sin idea de lo que era realmente, con pocos conocimientos de informática ni de electrónica, sin pensárselo dos veces las dos amigas crean Vector Graphic en agosto de 1976, con un capital social de 6.000 dólares y usando dos mesas en el cuarto de invitados, con Lore como CEO y Carole como responsable de marketing.
Todos se vuelcan en la fabricación de las placas en casa, llenando toda la casa según cuenta en un artículo de 1982 de la revista Time. Lanzan el producto como venta por correo a través de las mismas revistas que venden los ordenadores, los envían contra-reembolso y sin posibilidad de devolución. La tarjeta de memoria es un éxito, se diseñan alguna placa adicional, y en 1977 se lanzan a la carrera, deciden fabricar un ordenador completo compatible con el Altair 8800.
En abril de 1977 tuvo lugar la Feria de Informática de la Costa Oeste, en donde Jobs y Wozniak presentan el Apple II, y muy cerca está el stand donde Vector Graphic presenta el Vector 1.
 |
| El Vector 1 en verde. Fuente oldcomputers.net |
Era un ordenador enfocado al uso profesional pero con una estética cuidada, con carcasa a elegir entre verde o naranja. Bastante económico, su precio en kit era de 600 dolares, y montado se vendía por 850 dólares (la mitad que un Apple II aproximadamente). Las ventas fueron muy buenas, y su estrategia también, buscaron distribuidores nacionales y extranjeros, y en cuatro años vendían por valor de tres millones de dolares mensuales. En
1982 las ventas alcanzaron los 36 millones de dólares con 2 millones de
beneficios, y empleaba a 425 trabajadores.
Lore empezó a protagonizar portadas, al igual que Jobs no sabían mucho de informática, pero destacaba como genio de los negocios. Aunque apodada "la doncella de hierro" (instrumento de tortura medieval), se preocupaba mucho por el bienestar de los trabajadores y sus familias.
La empresa crecía, nuevos modelos surgieron, pero Bob dejó la empresa y el matrimonio, ya que pensaba que debían fabricar un compatible con el IBM PC. En su lugar lanzaron el Vector 4, aunque con procesador 8086 y pantalla gráfica en color, no era compatible con el PC.
Lore empezó a protagonizar portadas, al igual que Jobs no sabían mucho de informática, pero destacaba como genio de los negocios. Aunque apodada "la doncella de hierro" (instrumento de tortura medieval), se preocupaba mucho por el bienestar de los trabajadores y sus familias.
 |
| Portada de Marzo de 1981. Fuente eldiario.es |
El acierto de Bob no fue tenido en cuenta, Lore volvió a casarse y dejó la dirección, pero las ventas cayeron en picado, caida ayudada porque el Vector 4 fue anunciado prematuramente, lo que motivó un retraso de ventas esperando el nuevo modelo. Ella regresó un par de años después, pero fue imposible remontar el vuelo, y en el 84 es la caída definitiva. En 1985 entra en quiebra.
Productos de Vector Graphics
El primer producto fue la tarjeta de memoria para el bus S-100 de 1976.
 |
| Tarjeta de 8Kb de memoria estática. Fuente s100computers.com |
En 1976/77 el Vector 1, una computadora completa clon del Altair 8800, usando el bus S-100, inicialmente con microprocesador 8080A, aunque luego salió una tarjeta usando un Z80. Disponía de 1Kb de RAM, ampliables a 64Kb. Podía usar disqueteras manejando una versión del CP/M.
 |
| Vector 1 color óxido. Fuente old-computers.com |
El Vector 1+ añadía una unidad de disquetera interna y posibilidad de externas.
 |
| Vector 1+. Fuente vintage-computer.com |
En 1977 el Vector 3, también llamado Vector VIP tenía un teclado fijo, lo que fue un lastre pues no gustaba en ese momento un aparato con teclado fijo que lo hacía mas aparatoso y poco flexible. Usaba un 8080A o un Z80, y disponía de base de 56Kb de RAM, su pantalla integrada era monocroma en modo texto únicamente.
 |
| Vector 3 o Vector VIP. Fuente old-computers.com |
 |
| Vector MZ. Fuente old-computers.com |
 |
| Vector 4. Fuente old-computers.com |
Los ordenadores de Vector Graphics incluían muchas innovaciones, como el controlador de vídeo y teclado integrado Flashwriter.
 |
| Fuente s100computers.com |
Los primeros modelos utilizan el controlador y la unidad de disquete de 5¼" de Micropolis. Los modelos posteriores usaban unidades de disquete y disco duro de Tandon. Casi todas usado un formato propio de 100 pistas por pulgada con 16 sectores. Algunos modelos incluyen unidades de disquete de 8" y una unidad de disco duro.
 |
| Controladora de disquetera y disco duro. Fuente s100computers.com |
Aunque principalmente utiliza el sistema operativo CP/M, corrió otros incluyendo OASIS, Micropolis Disk Operating System (MDOS) y Micropolis Z80 (MZOS). Aunque no era compatible con el IBM PC, existió una versión del MS.DOS para el Vector 4. Vector Graphic disponía de un muy conocido procesador de textos llamado Memorite. Combinado con Flashwriter daban capacidad de procesamiento de texto económico a los Vector.
 |
| MS.DOS para el Vector 4. Fuente betaarchive.com |
jueves, 8 de octubre de 2015
Valencia va de Retro 2015
Como siempre, una vez terminado es cuando lo pongo. Este año ha sido bastante mejor, hemos conseguido montar un evento completo y redondo. A partir de ahora todo es ir mejorando los detalles, porque Valencia ya está perfectamente ubicada en el mapa de Eventos Retro, y con un nivel muy alto.
lunes, 22 de diciembre de 2014
Entrevista en el Blog de Manu
Otro blog recomendable para los aficionados al retro, que toca un poco de todo, es del Manuel Sagra, conocido como Manu, que siempre ha echo unos reportajes increíbles de los RetroMadrid.
La entrevista a publicó el 20 de Noviembre, pero como llevo mal mi blog ultimamente, lo pongo ahora para el que no sepa
La entrevista a publicó el 20 de Noviembre, pero como llevo mal mi blog ultimamente, lo pongo ahora para el que no sepa
sábado, 1 de noviembre de 2014
El albañil, el arquitecto, el físico y el informático
Eres el afortunado poseedor de una casa con jardín, y para disfrutar del verano decides montar una barbacoa, por lo que llamas a un albañil que te monta una preciosa. No contento, decides que una pila iría muy bien para lavar las cosas, por lo que llamas a un fontanero que te la monte. Magnífico, pero un enchufe para la batidora te ayudaría con las salsas, llamas al electricista y te monta uno especial para intemperie.
Como la vida te sonríe amplias la casa, para lo que llamas a un arquitecto, le cuentas lo que quieres, este hace unos bocetos, te gustan, luego hace planos detallados y un plan de trabajo. Pone a un arquitecto técnico (antiguo aparejador) a dirigir la obra, este coordina los equipos de albañiles, fontaneros, electricistas, etc.
La ciencia para que tu casa no se caiga la pone un físico, que es el que calcula las fuerzas que actúan en un punto, la resistencia de los materiales, los efectos del frío y el calor.
Nadie llama a un físico para que le haga una casa, y por supuesto si digo que soy arquitecto nadie me pide que le levante una pared de ladrillos, ni se espera de un albañil un cálculo de las fuerzas radiales en un domo.
Yo me pregunto, ¿porque si soy ingeniero informático me siguen pidiendo que les arregle un PC o les instale un Windows?
La informática, como la construcción, tiene muchos especialistas, programadores, diseñadores, instaladores de redes o de sistemas, todos bajo la dirección de los ingenieros e ingenieros técnicos, que hacen su labor ya que un grupo de ingenieros informáticos desarrolla las bases de la ciencia de la informática. Todos tienen una labor diferente, y todos son importantes, pero dejemos que cada uno haga sus tareas, informémonos antes de las cosas, y no pidamos a quien no sabe del tema que te arregle algo.
Lo malo es que internamente ni siquiera los que estamos dentro de la profesión quieren respetar estas cosas, hay demasiados "informáticos" que piensan que los ingenieros son programadores, ya que lo estudian en la carrera, y demasiados ingenieros que también, por desgracia.
Defendamos nuestra profesión, al fin y al cabo, actualmente es la que mueve el mundo (o maneja los mecanismos que lo controla).
Como la vida te sonríe amplias la casa, para lo que llamas a un arquitecto, le cuentas lo que quieres, este hace unos bocetos, te gustan, luego hace planos detallados y un plan de trabajo. Pone a un arquitecto técnico (antiguo aparejador) a dirigir la obra, este coordina los equipos de albañiles, fontaneros, electricistas, etc.
La ciencia para que tu casa no se caiga la pone un físico, que es el que calcula las fuerzas que actúan en un punto, la resistencia de los materiales, los efectos del frío y el calor.
Nadie llama a un físico para que le haga una casa, y por supuesto si digo que soy arquitecto nadie me pide que le levante una pared de ladrillos, ni se espera de un albañil un cálculo de las fuerzas radiales en un domo.
Yo me pregunto, ¿porque si soy ingeniero informático me siguen pidiendo que les arregle un PC o les instale un Windows?
La informática, como la construcción, tiene muchos especialistas, programadores, diseñadores, instaladores de redes o de sistemas, todos bajo la dirección de los ingenieros e ingenieros técnicos, que hacen su labor ya que un grupo de ingenieros informáticos desarrolla las bases de la ciencia de la informática. Todos tienen una labor diferente, y todos son importantes, pero dejemos que cada uno haga sus tareas, informémonos antes de las cosas, y no pidamos a quien no sabe del tema que te arregle algo.
Lo malo es que internamente ni siquiera los que estamos dentro de la profesión quieren respetar estas cosas, hay demasiados "informáticos" que piensan que los ingenieros son programadores, ya que lo estudian en la carrera, y demasiados ingenieros que también, por desgracia.
Defendamos nuestra profesión, al fin y al cabo, actualmente es la que mueve el mundo (o maneja los mecanismos que lo controla).
Suscribirse a:
Entradas (Atom)