Download: rambop.v2.zip
Quando criança, Rambo era um dos meus jogos prediletos. Era um RPG bem díficil
de completar, se você não soubesse a seqüência exata de telas a seguir! Eu gostava
tanto do jogo, que acabei comprando um cartucho original japonês, e até mesmo
traduzi alguns trechos do manual. Mas apesar
disso tudo, tinha um detalhe que sempre me incomodou: a tela de abertura.
Se o jogo é todo colorido, porque a tela de abertura tinha que ser
monocromática e feiosa? Certamente o pessoal da Pack-In-Video podia ter
feito uma tela melhor. E então eu resolvi encarar o desafio, pegar o jogo original
e melhorar a tela de abertura, mantendo os requisitos originais: MSX-1
com 16kb de RAM, e tudo dentro de um cartucho de 32kb de ROM.
Refazer a tela de abertura foi o trabalho de um fim de semana feito
com a ajuda do Cyberknight,
usando o Graphos III do
Renato Degiovani.
O real desafio foi colocar de volta a tela dentro da ROM. A tela original,
comprimida com RLE, ocupava 2.6kb de espaço. Então essa minha nova tela tinha
que ser comprimida nesse mesmo espaço, o que se revelou ser uma tarefa extremamente
difícil! No final, usando algoritmos no estado-da-arte em compressão, finalmente
foi possível colocar a tela de volta dentro do jogo.
O resultado está disponível aqui para download . Divirtam-se!!!
O primeiro desafio de Rambo Plus foi, é claro, desenhar a tela de abertura.
Como o processo usado foi muito similar ao usado em N-Sub,
eu não vou entrar em detalhes, e vou focar mais no segundo, e mais difícil desafio:
a compressão. A nova tela de abertura, comprimida pelo GIF, tinha 4328 bytes. A tela
original usava os endereços de AC10h a B768h da ROM, e também tinha um espaço sobrando
no final da ROM depois do endereço BD82h (preenchido com o texto 王様の耳はろばの耳,
"o rei tem orelhas de burro"). Isso significava que apenas 3542 bytes estavam
disponíveis, então qualquer compressão que eu fosse criar tinha que ser melhor que o GIF.
É aí que o problema começa! O GIF usa LZW, e esse algoritmo pode ser provado que é ótimo
(quando o tamanho do arquivo vai para o infinito). Então como alguém pode fazer
melhor que um algoritmo ótimo? A solução é o mantra da compressão: conheça seus dados.
O único jeito de bater uma compressão estatística é modelando seus dados,
extraindo redundâncias. Se tiver uma maneira de jogar dados fora, melhor ainda!
Dessa maneira, vamos ver o que sabemos sobre nossos dados. Sabemos que os
dados representam uma imagem, então não apenas existe redundância na horizontal,
mas também na vertical. Sabemos que a imagem é SCREEN 2, então cada
oito pixels consecutivos podem ter apenas duas cores (de 15). Isso significa
que podemos quebrar nossa imagem complexa em três imagens mais simples, a primeira
sendo uma imagem monocromática que representa os padrões (pattern), e as outras
duas contendo, respectivamente, as cores dos bits "1" e dos bits "0", sendo
ainda que essas duas imagens têm apenas 1/8 do tamanho horizontal da primeira.
As três imagens podem ser vistas abaixo, notando que eu aumentei oito vezes
a largura das imagens com as cores para que todas tivessem o mesmo aspect ratio.
A imagem com os padrões é bem diferente das imagens com as cores, então eles vão
precisar de tipos diferentes de compressão. Vamos analisar os padrões primeiro.
De imediato notamos que existe bastante espaço vazio, então o algoritmo que
formos escolher precisa tratar bem espaços vazios. Mas, antes de escolher o
algoritmo, existe algum jeito de melhorar os dados? Dá pra extrair redundâncias?
Tem como jogar dados fora? A resposta, surpreendentemente, é sim, podemos usar
uma compressão com perdas! O truque das compressões com perdas é que o usuário
final não pode perceber que foram jogados dados fora. No mp3, por exemplo, são
removidas todas as freqüências que o ouvido humano não consegue ouvir. No nosso
contexto, a imagem deve parecer a mesma, depois de retirados os dados.
Então, como fazer? Já que vamos buscar um algoritmo focado em comprimir
de maneira eficiente os espaços vazios, então qualquer transformação que
aumente os espaços vazios é boa. Na SCREEN 2, nós temos duas cores para
cada 8 pixels, se o pixel é "1", então escolhemos a primeira cor (INK),
se o pixel é "0", então escolhemos a segunda cor (PAPER). Mas o que
acontece se os oito pixels tem a mesma cor? Então tanto faz escolher
tudo um e tornar o PAPER irrelevante, ou escolher tudo zero e tornar
o INK irrelevante. Já que queremos aumentar os espaços vazios, iremos
escolher então tudo zero. Se a imagem original tem tudo um, então só
precisamos trocar INK com PAPER e complementar o pattern, isso é uma
operação com perdas, mas o usuário não tem como notar.
Ainda tem mais operações com perdas que podemos fazer. Suponha
que um octeto não tem apenas zeros ou apenas uns. Ele deve ter duas
cores então. Mas e se o artista (por erro ou algum outro motivo) usou
a mesma cor para PAPER e INK? Nesse caso a informação do pattern é
irrelevante! Podemos, com segurança, jogar fora o pattern e trocá-lo
por tudo zeros. Depois de fazer as duas operações citadas, as imagens
ficam como abaixo:
Como podemos ver, o Rambo propriamente dito já estava bem formatado, mas conseguimos
aumentar o espaço vazio no helicóptero. Terminado o modelamento dos dados,
agora podemos ver a compressão. Só de olhar para a imagem com os padrões já
dá pra ver que o RLE não vai funcionar. Nós temos um monte de espaço vazio
que o RLE iria codificar, mas o RLE só opera em um eixo, e precisamos explorar
a conectividade bidimensional da imagem. Isso usualmente é feito com análise
espaço-frequencial, como wavelets, mas no Z80 wavelets seriam lentas demais.
Podemos, entretanto, usar quad-trees!
A idéia por trás das quad-trees é simples. Esse algoritmo recursivo
começa olhando pro retângulo atual (que no início é a tela toda). O retângulo é
vazio? Se for, imprima um "0". Se não for, imprima um "1", quebre o retângulo
em quatro, e repita o procedimento pra cada retângulo menor, até que ele seja
vazio, ou que consista de um único pixel, nesse caso, imprima seu valor.
O algoritmo pode comprimir regiões inteiras para um único bit, então é
bem apropriado no nosso caso. Porém, ainda temos que fazer uns ajustes pequenos.
Como nossa tela inicial de 256x192 não é quadrada, podemos quebrá-la em três
regiões de 256x96, e parar a recursão quando o retângulo for 4x1, dessa maneira
cada passo da recursão pode ser facilmente calculado como x/2 e y/2. Na imagem
abaixo, eu pintei cada retângulo vazio com um tom cada vez mais claro de vermelho,
então é possível ver a partição do espaço feita pelo algoritmo.
O resultado parece bom, tem grandes áreas com vermelho escuro, então essas áreas
foram comprimidas para poucos bits. A bitstream completa para essa quad-tree no
final ficou com apenas 2334 bytes, muito bom. Agora precisamos comprimir as
imagens com as cores. A abordagem de espaços vazios não vai funcionar,
mas podemos notar as cores em uma mesma coluna vertical são iguais na maioria
dos casos. Podemos melhorar isso, jogando dados fora ou modificando de uma
maneira que o usuário não perceba? Claro! Suponha que o artista pintou
um octeto com azul sobre vermelho, e o seguinte com vermelho sobre azul.
Se nós invertermos o pattern, trocando zeros com uns, podemos também
trocar INK com PAPER, e os dois octetos agora terão a mesma cor. Um
jeito simples de fazer isso é ordenando lexicograficamente todos
os octetos, por exemplo, impondo que INK precisa sempre ser maior
que PAPER. Depois de ordenas as cores em todos os octetos, o comprimento
das faixas verticais vai aumentar.
Ainda tem outra transformação que podemos fazer. Nós vimos anteriormente
que padrões com oito pixels iguais foram trocados para tudo zero, e suas
cores foram setadas no PAPER. Mas e o INK delas? Nós podemos escolher
qualquer cor para o INK, já que ele não vai ser usado. De modo a aumentar
ainda mais o tamanho das nossas barras verticais, podemos escolher o INK
como sendo o mesmo do octeto anterior. Após fazer as duas operações,
as imagens ficam assim:
Muito melhor! E precisamos notar que, apesar de termos mudado bastante
as imagens, o usuário não vai perceber nada. Só precisamos agora escolher
o método de compressão. As faixas verticais seriam bem codificadas pelo RLE,
mas tem alguns padrões que ficariam ruins, como as cores alternadas no
cabelo do Rambo. Essas cores alternadas seriam bem comprimidas por alguma
variante do LZ, mas variantes de LZ não seriam boas nas faixas verticais.
A solução é usar o RLE e o LZ ao mesmo tempo! Podemos, por exemplo,
imprimir um "0" se a string que seguir for codificada com RLE, e imprimir
um "1" se a string que seguir for codificada com LZ. O truque pra fazer
isso funcionar é escolher certinho o número de bits que usam o RLE e o LZ.
Lembre que o RLE precisa de um número que identifica quantas vezes devemos
repetir a cor. Se esse número for representado com poucos bits, então
faixas muito grandes podem precisar de várias strings para serem codificadas,
o que não é bom. Por outro lado, se escolhermos bits demais, faixas pequenas
terão um monte de bits 0 sobrando na parte mais significativa do número.
No LZ o mesmo se aplica, mas temos dois números pra se preocupar: o tanto
que precisamos voltar na string, e o tanto que devemos copiar a partir
desse ponto.
Como escolher a distribuição ótima de bits então? Se estivéssemos
fazendo um compressor genérico, isso poderia ser um problema. Mas
nós vamos comprimir a abertura do Rambo uma única vez. Nesse caso,
nada será melhor que uma busca por força bruta no espaço dos números!
Mesmo se a força bruta levar algumas horas, não tem problema, já
que esse trabalho será feito uma única vez. Depois de implementado,
o algoritmo nem precisou de tanto tempo assim, alguns minutos foram
suficientes. Os números mágicos são 7 bits para o RLE, 8 bits para
o ponteiro de retorno do LZ, e 5 bits para a repetição do LZ. A bitstream
final, somando os padrões com as cores, ficou com apenas 3189, o
que não apenas pequeno o suficiente para caber na ROM, mas também
menor que o Info-ZIP na compressão máxima, o que é muito legal!
O toque final é escrever um decoder para essas bitstreams,
que seja rápido o suficiente para que o usuário não perceba
a descompressão, e pequeno o suficiente para caber no pouco
espaço que resta. Isso foi feito usando o Super Otimizador.
Ufa! Foi um monte de trabalho só pra ter uma tela de abertura
colorida, mas o resultado final valeu a pena.
