martes, 13 de octubre de 2015

Programemos un juego en C (VI): Compresión de datos, cambios de base




Exploremos ahora una técnica de compresión bastante sencilla de implementar y bastante eficiente en cuanto a ocupación, basada en los cambios de base de numeración.

En nuestro juego usaremos 7 elementos diferentes que son " ", "#", "$", "@", ".", "*" y "|". Si en lugar de representar cada uno con un carácter de 8 bits, usamos un número entero sin signo, para almacenar un número entre 0 y 6 solo necesitamos 3 bits, por lo que desaprovechamos 5 bits de cada byte realmente, eso es mas del 50%, un despilfarro. Hay dos técnicas que se usan habitualmente, el BDC y el cambio de base.

BDC es acrónico en inglés de Decimal Codificado en Binario, como con 4 bits podemos almacenar un número del 0 al 16, en este sistema se usan 4 bits para almacenar un solo dígito del 0 al 9, y cada byte almacena dos números en su interior, uno en los 4 bits superiores y otro en los inferiores. De esta forma para almacenar un número como el 78, como 7 en binario es 0111 y 8 es 1000, si los ponemos juntos formarían el número binario 01111000, y en un solo byte tenemos almacenados dos números de forma sencilla. El número almacenado se lee igual en hexadecimal que en decimal codificado en este formato, una ventaja del sistema en base 16.

Los procesadores suelen disponer de instrucciones adecuadas para manipular número en este formato y operar con ellos, y es muy sencillo mostrar estos dígitos en un display de 7 segmentos usando un chip codificador BDC.

Si usamos esta técnica, debemos convertir los datos a números, así asociamos un número a cada elemento, por ejemplo: 0 = " ", 1 = "#", 2 = "$", 3 = "@", 4 = ".", 5 = "*", 6 = "|".

Mediante un programa debemos convertir las cadenas de caracteres con los datos a BDC, e ir almacenándolas en variables enteras sin signo de 8 bits, para eso en C se usa el tipo unsigned char, lo mejor es hacer un programa para convertirlo, es sencillo y práctico. Si en un nivel al final hay un número impar de dígitos, rellenamos con un cero al final, que no hará nada. Los dos primeros niveles del juego quedarían así en hexadecimal, que el C puede tratar directamente sin problemas:

00h,00h,11h,11h,16h,00h,00h,10h,00h,16h,00h,00h,12h,00h,16h,
00h,11h,10h,02h,11h,60h,01h,00h,20h,20h,16h,11h,10h,10h,11h,
01h,00h,01h,11h,11h,16h,10h,00h,10h,11h,01h,11h,11h,00h,44h,
16h,10h,20h,02h,00h,00h,00h,00h,00h,44h,16h,11h,11h,10h,11h,
10h,13h,11h,00h,44h,16h,00h,00h,10h,00h,00h,11h,11h,11h,11h,
16h,00h,00h,11h,11h,11h,16h 

11h,11h,11h,11h,11h,11h,61h,44h,00h,10h,00h,00h,11h,16h,14h,
40h,01h,02h,00h,20h,01h,61h,44h,00h,12h,11h,11h,00h,16h,14h,
40h,00h,03h,01h,10h,01h,61h,44h,00h,10h,10h,02h,01h,16h,11h,
11h,11h,01h,12h,02h,01h,60h,01h,02h,00h,20h,20h,20h,16h,00h,
10h,00h,01h,00h,00h,01h,60h,01h,11h,11h,11h,11h,11h,16h


Solo de esta sencilla manera hemos conseguir reducir a la mitad la ocupación de los 10.492 bytes que teníamos ya sin espacios no necesarios, y dejarlos en 5.246 bytes.

Pero analizando los datos hay una posible mejora, para almacenar un valor del 0 al 7 solo hacen falta 3 bits, con lo que en un byte puedo almacenar dos números y dos tercios, casi tres, una pena que nos falte solo un bit, pero si ese bit fuera siempre cero o uno ya no hace falta que lo almacenemos. Usaremos un pequeño truco, sabemos que la mayoría de los valores a almacenar son huecos o paredes, si le asignamos un número bajo la mayoría de las veces los elementos comenzarán siempre por cero.

Como tenemos 8 posibles valores con 3 bits y usamos 7, vamos a poner en marcha un truco. Los valores que vamos a almacenar van a ser 8, añadimos uno nulo que representa que es un hueco a saltarse, por lo que cuando decodificamos ese valor cero nos lo saltamos directamente. Ese valor lo usaremos solo cuando tengamos que almacenar un elemento en la posición alta del byte cuyo primer bit deba ser un uno. De esta forma aunque el 90% de las veces no hace falta, por poner una cifra diré que solo el 50% de las veces lo uso, por lo que el otro 50% de las veces almacenaré un tercer valor en un byte, o lo que es lo mismo guardo 2.5 valores en cada byte, y reduzco los 10.492 bytes a ocupar solo entre 4.197 y 3.617 bytes, la ganancia es muy grande.

Codificamos así los elementos ahora 0 = nulo, 1 = " ", 2 = "#",  3 = "$", 4 = ".", 5 = "*", 6 = "|", 7 = "@" y codifico de binario, presento los dos primeros niveles e este formato, agrupo de tres en tres y destaco los ceros añadidos cuando un grupo empieza por uno o para completar los bytes. De los 310 caracteres codificados hemos añadido 14, un cuatro y medio por ciento.

001 001 001 - 001 010 010 - 010 010 010 - 000 110 001 - 001 001 001
010 001 001 - 001 010 110 - 001 001 001 - 001 010 011 - 001 001 010
000 110 001 - 001 010 010 - 010 001 001 - 011 010 010 - 000 110 001
001 010 001 - 001 011 001 - 011 001 010 - 000 110 010 - 010 010 001
010 001 010 - 010 001 010 - 001 001 001 - 010 010 010 - 010 010 010
000 110 010 - 001 001 001 - 010 001 010 - 010 001 010 - 010 010 010
010 001 001 - 000 100 100 - 010 110 010 - 001 011 001 - 001 011 001
001 001 001 - 001 001 001 - 001 001 001 - 000 100 100 - 010 110 010
010 010 010 - 010 001 010 - 010 010 001 - 010 111 010 - 010 001 001
000 100 100 - 010 110 001 - 001 001 001 - 010 001 001 - 001 001 001
010 010 010 - 010 010 010 - 010 010 010 - 000 110 001 - 001 001 001
010 010 010 - 010 010 010 - 010 000 000

010 010 010 - 010 010 010 - 010 010 010 - 010 010 010 - 000 110 010
000 100 100 - 001 001 010 - 001 001 001 - 001 001 010 - 010 010 110
010 100 100 - 001 001 010 - 001 011 001 - 001 011 001 - 001 010 110
010 100 100 - 001 001 010 - 011 010 010 - 010 010 001 - 001 010 110
010 100 100 - 001 001 001 - 001 111 001 - 010 010 001 - 001 010 110
010 100 100 - 001 001 010 - 001 010 001 - 001 011 001 - 010 010 110
010 010 010 - 010 010 010 - 001 010 010 - 011 001 011 - 001 010 110
001 001 010 - 001 011 001 - 001 011 001 - 011 001 011 - 001 010 110
001 001 010 - 001 001 001 - 001 010 001 - 001 001 001 - 001 010 110
001 001 010 - 010 010 010 - 010 010 010 - 010 010 010 - 010 010 000

Pasando los valores a decimal nos queda esta codificación:

73, 82, 146, 49, 73, 137, 86, 73, 83, 74, 49, 82, 137, 210, 49, 81, 89, 74, 50, 145, 138, 138, 73, 146, 146, 50, 73, 138, 138, 146, 137, 36, 178, 89, 89, 73, 73, 73, 36, 178, 146, 138, 145, 186, 137, 36, 177, 73, 137, 73, 146, 146, 146, 49, 73, 146, 146, 128

146, 146, 146, 146, 50, 36, 74, 73, 74, 150, 164, 74, 89, 89, 86, 164, 74, 210, 145, 86, 164, 73, 121, 145, 86, 164, 74, 81, 89, 150, 146, 146, 82, 203, 86, 74, 89, 89, 203, 86, 74, 73, 81, 73, 86, 74, 146, 146, 146, 144


El otro sistema sencillo de codificación es el cambio de base. Un número cualquiera lo podemos escribir como potencias de 10, así el 5.24610 sería 5.103 + 2.102 + 4.101 + 6.100. De igual manera podemos escribir un número en base 7, cambiando el 10 por un 7. Si entendemos la lógica del sistema, veremos que en base 7 podemos escribir el número 5467 sería 5.72 + 4.71 + 6.70 = 27910


El sistema seria convertir los números que vamos obteniendo a base 7, e ir montándolos en un número entero sin signo. si usamos dos bytes podemos almacenar 5 números en base 7 en su interior, contra el sistema BDC que almacenábamos solo 4. Un poco mas, pero los 10.492 bytes de partida quedan como 4.197 bytes, ganamos casi 1K con este sistema. Pasar de uno a otro es cuestión de multiplicar y dividir nada mas, lo malo de este sistema es que las divisiones  son operaciones lentas para los ordenadores, por lo que aunque es un buen y sencillo sistema, en nuestro caso no es el mas recomendable tampoco.

lunes, 12 de octubre de 2015

Programemos un juego en C (V): Compresión de datos, técnicas mas eficientes




Las técnicas de evitar repeticiones son sencillas y rápidas, ahora veremos técnicas que consiguen mejor ratio de compresión, aumentando un poco la complejidad. Cuando programamos para máquinas con recursos muy limitados, hay que promediar las cosas, si una rutina ocupa 1Kb y nos ahorra 3Kb es eficiente, si ahorra 2Kb efectiva, pero si ahorras 1Kb no sirve de nada, lo que ganas lo gastas. Luego está el tema de la velocidad, cuando descomprimes empleas un tiempo, si cuesta bastante descomprimir puede que no te sirva, ya que en máquinas lentas pueden afectar a la velocidad del juego. Todo es una lucha para conseguir que todo funcione correctamente.

Las técnicas con diccionarios se basan en buscar no elementos repetidos, sino en combinaciones de elementos diversos repetidos, comprimen mejor, pero requieren de un diccionario en el que se almacena los cambios que se han efectuado, para poder restaurarlos. Si el diccionario es muy grande no ganamos mucho, siempre en el término medio está la virtud. El procedimiento mas sencillo es la codificación de bytes pares.

Veamos como comprimimos nuestra cadena de ejemplo "aaaaabbbbbbbbbbbbbccddddddd", no es el mejor ejemplo, pero si uno bueno para entender el mecanismo. Empezamos cambiando las mas evidentes, aunque podemos elegir otros pares, hay que buscar siempre los que mas se repitan, por tanto "aa" por A, "bb" por B, "cc" por C y "dd" por D, nos queda "AAaBBBBBBbCDDDd". Solo con esto tenemos casi el 50%.

Segunda vuelta, cambiamos "AA" por 1, "BB" por 2, "CD" por 3 y "DD" por 4. Ya vemos que no tienen que ser elementos repetidos los que usamos, sino parejas. Nos queda "1a222b34d".

Tercera vuelta, cambiamos "1a" por M, "22" por N, 2b por O, 34 por P, y nos queda "MNOPd".

Cuarta vuelta, cambiamos "MN" por X, "OP" por Y y nos queda "XYd".

Quinta vuelta, cambiamos "XY" por * y nos queda "*d".

Sexta vuelta, cambiamos "*d" por A y nos queda "A".

Vemos que este método puede reducir todo a una sola letra, a costa de que el diccionario que lo acompañe sea mas grande, siempre se aplica en orden inverso para que no haya problemas. En nuestro caso el diccionario sería de 16 entradas de 3 elementos cada una, ocupa por tanto 48 posiciones, y hay que ver en que punto podemos dejar de comprimir cuando ya no ganes nada en contra de lo que ocupa el diccionario. También podemos ver que no podemos usar los mismos elementos sin tener mucho cuidado, si A puede significar "*d" o "aa" según el nivel, no sería posible recuperar los datos si no están bien separados los niveles. En nuestro ejemplo el diccionario ocupa mas que la cadena, pero si la cadena de origen fuera de 1.000 posiciones, y lo dejamos en 100, la compresión sería muy eficiente. Luego viene el tema de que hay que recorrer la cadena el número de entradas en el diccionario para descomprimir, o añadir información de los niveles para acelerar las pasadas, lo que como siempre es compromiso entre ganancia de espacio y velocidad. El diccionario resultante sería este

(6) A = *d
(5) * = XY
(4) Y = OP
(4) X = MN
(3) P = 34
(3) O = 2b
(3) N = 22
(3) M = 1a
(2) 4 = DD
(2) 3 = CD
(2) 2 = BB
(2) 1 = AA
(1) D = dd
(1) C = cc
(1) B = bb
(1) A = aa


Este tipo de compresión es sencillo de usar, pero requiere estudiar bien los datos de origen para maximizar el resultado. Para mejorarlo, podemos usar una variante en la que una combinación sea de mas de dos elementos. Veamos ejemplos con nuestros niveles. Los elementos que usamos en cada nivel son " ", "#",  "$", "@", ".", "*" y "|" son siete elementos. Podemos plantear las posibles combinaciones de los 7 elementos tomados de dos en dos nos da 42 posibilidades. Con esto tendríamos reducido nuestro tamaño a la mitad, añadiendo un diccionario de 126 caracteres. Otra técnica, en lugar de tantas combinaciones, vamos a usar otros niveles,  agruparemos los elementos repetidos de ocho en ocho, de cuatro en cuatro, luego de dos en dos, si lo hacemos en ese orden nunca hay problema para comprimir y luego descomprimir, y añado combinaciones muy usadas:

Z = "#|", A = "        ", B = "    ", C = "  ", D = "########", E = "####", F = "##", G = "........", H = "....", I = "..", J = ".#", K = " #", L = "# "

Con esto tenemos reducido a 6.030 caracteres. Podemos hacer una segunda vuelta, una tercera, y buscando combinaciones se puede reducir al nivel que deseemos. Por ejemplo podemos usar combinaciones como 1 = "C#", 2 = "#I", 3 = "$K", 4 = "CK", 5 = "#K", 6 = "#C", 7 = "F#", 8 = "BK", 9 = "B#", 0 = "$ ". Con estos dos niveles, que tampoco he estudiado demasiado, el resultado es que ocupa 5.270 caracteres, vamos ganando espacio. Seguro que si se estudian mejor las combinaciones de primer nivel ganaremos bastante espacio mas, eso es lo que hacen los programas de compresión, cuentan primero las combinaciones para encontrar las más usadas.

BEZ
B6 Z
9$CZ
CF6$#Z
1C00Z
F5 FKC E#Z
#4 F E6IZ
L$C$ACIZ
ELF5@FCIZ
9B DZ
BE7

D7Z
21B FZ
2CL$C$CZ
21$ECZ
2B@ FCZ
21KC3Z
EF F00Z
CL$C000Z
19B Z
CDE

Esto realmente va en línea, quedando en dos cadenas así, y seguramente si se distribuye en línea se ganará mejor compresión con las combinaciones "#| " y "#|#" que son muy numerosas.

BEZB6 Z9$CZCF6$#Z1C00ZF5 FKC E#Z#4 F E6IZL$C$ACIZELF5@FCIZ9B DZBE7

D7Z21B FZ2CL$C$CZ21$ECZ2B@ FCZ21KC3ZEF F00ZCL$C000Z19B ZCDE

En la siguiente entrada veremos el tercer sistema usual de compresión sencillo de usar, para el que necesitamos un poco mas de cálculos y el uso de las bases de numeración.

domingo, 11 de octubre de 2015

Programemos un juego en C: Indice

Estas son las entradas relacionadas con el tema:

Introducción:
INFERNO, un sokoban para nuestro Spectrum

Entradas
  1. Programemos un juego en C: Estructura básica planteada
  2. Programemos un juego en C (II): Estructura básica efectiva
  3. Programemos un juego en C (III): Retomando el tema
  4. Programemos un juego en C (IV): Compresión de datos, eliminado repeticiones simples
  5. Programemos un juego en C (V): Compresión de datos, técnicas mas eficientes
  6. Programemos un juego en C (VI): Compresión de datos, cambios de base

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|
IOW

Con 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.

Portada de Marzo de 1981. Fuente eldiario.es
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.

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
De 1979 es el MZ, un VIP pero separa la pantalla y teclado (denominadas "Mindless Terminal") de la CPU, conectándolas con una tarjeta llamada Flashwriter. En la caja incluye una placa con 18 slots de expansión y dos disqueteras de 315Kb. Incluye 48Kb de RAM, 4Kb de ROM.

Vector MZ. Fuente old-computers.com
El Vector 4 de 1983 era un modelo híbrido de transición 08/16 bits. Usando una placa con bus S-100, incluía tarjetas con un Z80 a 6Mhz y un 8088 también a 6Mhz. Mas rápido que el IBM PC que funcionaba a 4.77Mhz, no era compatible al usar una arquitectura completamente diferente. Disponía de 128Kb de RAM, ampliables hasta 256Kb, y dos disqueteras y una buena capacidad gráfica ya que disponía de pantalla gráfica en color. Disponía del sistema operativo CP/M, y se podía añadir tarjetas de red opcionales para montar red LinkNet por paso de testigo a 750kbs. Llegó a salir una versión del MS.DOS para esta máquina.


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.