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.
No hay comentarios:
Publicar un comentario