Compresor de mapas

For all things Churrera. ¿Estás haciendo un juego? ¿quieres proponer un cambio? ¿tienes alguna duda? ¡Cuéntanoslo!

Moderador: na_th_an

antoniovillena
Mensajes: 494
Registrado: Jue, 24 Oct 2013, 15:52

Compresor de mapas

Mensajepor antoniovillena » Sab, 02 Nov 2013, 01:13

Tengo en mente hacer un compresor de mapas de propósito general pero que valga para la Churrera. Mi idea es adaptar el algoritmo ZX7 de Einar Saukas, primero probando a comprimir cada pantalla de forma independiente y luego hacer experimentos para obtener mayor compresión.

Teniendo en cuenta el tamaño estándar de la churrera de 15x10, el empaquetador que contiene la churrera (no se puede llamar compresor) permite almacenar 2 tiles por cada byte, por lo que el ratio que se consigue es del 50% (75 bytes en lugar de los 150 bytes teóricos). Claro que el empaquetador sólo funciona con 16 tiles o menos. Evidentemente el compresor tiene que mejorar esta cifra y además permitir un número arbitrario de tiles hasta un límite de 256 (en la churrera el límite es de 48).

Voy a usar el ejemplo de Dogmole para las pruebas, que son 8x3= 24 pantallas. Sin aplicar compresión (ni empaquetación) tendría 24*150= 3600 bytes de mapa. Con la compresión lo que se pretende es hacer lo mismo pero empleando menor cantidad de RAM. Necesito al menos un buffer de 150 bytes donde almacenar la pantalla actual, más lo que ocupen todas las pantallas comprimidas, más lo que ocupe el propio código descompresor. O sea que cada vez que quiera mostrar una pantalla primero habría que descomprimirla. Tengo que procurar por un lado que todo esto no supere los 1800 bytes para que la compresión merezca la pena, y por otro lado que no sea muy lenta la descompresión, al menos en comparación con lo que tarda en pintarse una pantalla.

Así que bueno, lo primero que he hecho es medir el tiempo que se tarda en pintar la pantalla (sólo los tiles) y el resultado es de 129696 ciclos (sin contención), que equivale a 1.86 frames o a 37 milisegundos. Aquí dejo todo el código fuente que he utilizado.
Adjuntos
buñuelera.zip
(75 KiB) Descargado 359 veces
Avatar de Usuario
son_link
Mensajes: 467
Registrado: Mar, 01 Oct 2013, 11:49
Ubicación: Atlantis, Galaxia Pegaso
Contactar:

Re: Compresor de mapas

Mensajepor son_link » Sab, 02 Nov 2013, 07:54

A ver que tal sale, estaría bastante bien para poder hacer juegos con un mapa mas largo, que en el caso de Sami Troid vendría de lujo (los Metroid son largos y hay que explorar de lo lindo), pero ya sería para una posible segunda parte
LOAD TAPE ERROR
Image
Avatar de Usuario
na_th_an
Mensajes: 26413
Registrado: Vie, 09 Ene 2009, 12:18

Re: Compresor de mapas

Mensajepor na_th_an » Sab, 02 Nov 2013, 11:19

Para la siguiente versión estoy implementando RLE para los mapas. En la mayoría de las ocasiones será más que suficiente. Con un máximo teórico de 128 tiles (si usamos metatiles) se puede usar el bit 7 para indicar si el siguiente byte es un tile a secas o una pareja (contador - tile). Con un máximo de 48 tiles, además, se podría usar un solo byte para parejas o tripletas de dos tiles iguales y comprimir aún más (00 = el byte es un contador, 01 = una sola vez este tile, 10 = dos veces este tile, 11 = tres veces este tile). No comprimirá tanto con ZX7, pero la ventaja es que la descompresión será muy rápida (casi no se notará). Para juegos en los que se cambia mucho de pantalla esto es primordial.

La siguiente versión, además, estará completamente preparada para funcionar en 128K y tener RAM3, RAM4 y RAM6 como almacenes extra de niveles o pantallas comprimidas y RAM1 con el PSG-player de WYZ, las canciones y los efectos de sonido. Ya lo tengo funcionando, sólo lo estoy adecentando (tengo que integrar todas las partes). De aquí a fin de año lo sacaré, cuando acabemos el güego que estamos montando para probarlo.
Como diría Rorshach: "Urm..."
antoniovillena
Mensajes: 494
Registrado: Jue, 24 Oct 2013, 15:52

Re: Compresor de mapas

Mensajepor antoniovillena » Sab, 02 Nov 2013, 11:41

ZX7 es muy rápido, pero un algoritmo RLE que haga lecturas a nivel de byte lo sería aún más. Lo que tengo hecho ahora es un esqueleto en el que se puede adaptar cualquier algoritmo y lo más importante, medir los tiempos de descompresión en ciclos. Mi idea es ir comparando diferentes variantes de ZX7 hasta encontrar la óptima, que sería un término medio entre ratio de compresión y tiempo de descompresión. En cuanto tengas el código del compresor/descompresor RLE y lo publiques hago los números. Así a bote pronto no tengo ni idea de lo que se tardaría en descomprimir una pantalla (ni en ZX7 ni en RLE), pero me da a mí que mucho menos que pintarla.

Pero ya te digo que mi idea es un compresor de tiles de propósito general, si puede aplicarse a la Churrera genial, si no, pues nada. En teoría se puede aplicar a cualquier juego similar.
antoniovillena
Mensajes: 494
Registrado: Jue, 24 Oct 2013, 15:52

Re: Compresor de mapas

Mensajepor antoniovillena » Sab, 02 Nov 2013, 13:03

Acabo de hacer las pruebas de compresión con ZX7 para el juego Dogmole. En concreto he hecho 2 pruebas, la primera con el algoritmo zx7 sin modificar (usando símbolos de 8 bits) con el resultado de 1216 bytes. Y en la segunda prueba he cambiado la longitud de los símbolos a 4 bits (sólo tenemos 16 tiles) y el resultado que me da es de 1022 bytes.

Como el descompresor ocupa 69 bytes (el estándar, el modificado no lo sé), se necesita un buffer de 150 bytes para descomprimir y 24 bytes para delimitar cada uno de los streams comprimidos, esto nos da un total de: 69+150+24+1022= 1265 bytes. Tengan en cuenta que todavía me falta por afinar algunos parámetros, ya que la ventana es demasiado grande (2176 bytes cuando sólo necesitamos 150) y las ocurrencias justo una línea más arriba (15 bytes anteriores) son bastantes frecuentes.

Así que bueno, los resultados provisionales son un ratio de 0.7 (1268/1800) en ocupación de RAM y uno de 0.57 en cuanto a compresión se refiere con respecto a la versión empaquetada (4 bits por tile) que tiene actualmente la Churrera.
Adjuntos
compresion.zip
(7.8 KiB) Descargado 351 veces
Avatar de Usuario
D_Skywalk
Mensajes: 352
Registrado: Mar, 01 Oct 2013, 13:36

Re: Compresor de mapas

Mensajepor D_Skywalk » Sab, 02 Nov 2013, 13:10

Me encanta, yo aún no se si voy a necesitar compresión para mi güego pero si me ayuda a estar más desahogado perfecto, estoy usando los 48 tiles y alguno extra que necesitaré a parte XD

Muchas gracias antonio por compartirlo :corchoneta:
David Skywalker
Weblog: http://david.dantoine.org
antoniovillena
Mensajes: 494
Registrado: Jue, 24 Oct 2013, 15:52

Re: Compresor de mapas

Mensajepor antoniovillena » Sab, 02 Nov 2013, 13:26

De nada Skywalk.

Tengo buenas noticias. He ajustado los parámetros de la ventana y se ha mejorado el ratio de compresión. Las pantallas comprimidas ocupan ahora 881 bytes, la ocupación en RAM es de 1124 bytes y los ratios son de 0.62 y de 0.49 respectivamente.
Adjuntos
compresion_tuneada.zip
(3.55 KiB) Descargado 367 veces
Avatar de Usuario
D_Skywalk
Mensajes: 352
Registrado: Mar, 01 Oct 2013, 13:36

Re: Compresor de mapas

Mensajepor D_Skywalk » Sab, 02 Nov 2013, 16:40

Vaya, no conocía lodePNG... cuantas veces habré necesitado algo así! :brasas:
Necesitas que haga alguna prueba con lo que has enviado? Yo de ensamblador no entiendo mucho pero si puedo hacer algo :?
Puedo intentar usarlo en justin (16 tiles y usa la compresión churrera) que está terminado y te digo las impresiones, no se por si vale :corchoneta:

na_th_an, esas novedades para la siguiente churrera son flipantes... :wan: :dalefran:

Un Saludo!
David Skywalker
Weblog: http://david.dantoine.org
antoniovillena
Mensajes: 494
Registrado: Jue, 24 Oct 2013, 15:52

Re: Compresor de mapas

Mensajepor antoniovillena » Sab, 02 Nov 2013, 17:25

Gracias Skywalk. Hasta que no defina el algoritmo de compresión no hagas nada, ya te avisaré. Respecto al lodepng lo he encontrado googleando, en principio pensé hacerlo con libpng pero era un lío a la hora de compilarlo.
Avatar de Usuario
na_th_an
Mensajes: 26413
Registrado: Vie, 09 Ene 2009, 12:18

Re: Compresor de mapas

Mensajepor na_th_an » Sab, 02 Nov 2013, 22:26

Si lo necesitas, el engine de la Churrera tiene siempre dos buffers de 150 bytes para acelerar cálculos y un par de cosas más. Un buffer contiene una copia de la pantalla actual (y es el que se modifica al mover bloques y cosas así) y el otro contiene los comportamientos. A lo mejor te vienen bien para descomprimir.
Como diría Rorshach: "Urm..."

Volver a “La Churrera”

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 4 invitados