Fate by Fire: The Sword of Neisius

[Justin W.]

Well here it is my first post at UTI's new forum.

Fate by Fire: The Sword of Neisius is a rpg designed and created by Pascal Miller and myself.

It will be the biggest rpg ever on the ti83+. Plus it now has an added feature it will be in 4-level grayscale. A first ever on the ti83+. Now it's not what you're thinking. Ti83+ (crappy flickery grayscale). Wrong. This is a routine made by Diederik Kingma. It is nearly perfect. Crystal clear grayscale. The whole game will be in grayscale. So beautiful graphics are asured.

As soon as I tweak my decompression routine I'll post a screenshot. Yes it uses compression so huge maps. About 350 screens worth... :D

More to come.

[Pascal]

My first post too. Yea the game should be very nice when it is done. Progress is pretty quick thanks to Justin, who seems to finish some new routine every day-today it was grey scale, I won't be surprised if by next time I talk to him he will some how make the game in color.

[Justin W.]

Tomorrow's task is a working decompression routine

[NETWizz]

Justin, I could use a little compression routine. Please tell me a good method to compress data. If I knew how a compression routine works, I can figure out how to decompress.

Thanks.

[Justin W.]

OK I will explain RLE compression. (run-length-encoding)

Lets say that we have a data block that contains the following.

.db $20,$20,$20,$20,$20,$20,$21,$56,$35,$98,$98,$98,$98,$98,$01,$01

Now you need to check to see if there are more than 3 bytes exactly the same in succession. The reason you check to see if it's greater than 3 because a piece of compressed data is 3 bytes long.

1st byte=flag byte ;signifies that this is a run (piece of comressed data)
2nd byte=number of bytes ;number of that particular byte
3rd byte=the byte ;the byte to copy

So if your flag byte was $FF. (which is more effective for tilemaps because it is unlikely to have 255 tiles)

you could compress the above data to this.

.db $FF,$06,$20,$21,$56,$35,$FF,$05,$98,$01,$01

If it reads a byte that equals $FF it treats the next two bytes as a run.

so it would write 6 bytes to a location of your choice of $20


If there is any confusion please ask

[NETWizz]

What about this?

$FF,$FF,$FF,$FF,$56,$56,$56,$56,$FF,$44,$36,$36,$36
compress

$FF,$04,$FF,$FF,$04,$56$FF,$01,$FF,$44,$FF,03,$36

As you can see, the problem comes when $FF occurs in the data less than 3 times consecutivly because we must compress it no matter what to avaoid it accidently being interpreted as a flag yeielding scarry results when uncompressed. :D

For example, if we compressed teh above as
$FF,$04,$FF,$FF,$04,$56$FF,$44,$FF,$03,$36

Then decompressed it we would have
$FF,$FF,$FF,$FF,$56,$56,$56,$56,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$FF,$36,$36,$36

Therefore, we must compress (IF you can call it that) a single $FF to $FF,$01,$FF

Now, More on your routine
The following should not be compressed
$36
$36,$36
$36,$36,$36

The wierd one is $36,$36,$36 because compressing it would yield $FF,$03,$36 which would not be smaller, but it would add time to the decompression.

Now, the last problem comes when you have more than 256 bytes. Yes, I mean 256 not 255.

Here is why. You will never see $FF,$00,$36 because it would be irrelevant to say that there are 0 $36 bytes to decompress

Now, I think if we treat 0 as 1 then:

$FF,$00,$36 would mean one $36 and $FF,$FF,$36 would mean 256 $FF's


Although that is true, I propose that 256 is bad because the 00 could be an important part of the routine. So, I think we should really use 00 to $FF as 0 to 255 not 1 to 256.

For example:

$36,$36,$36,$FF,$56,$56,$56,$56,$56

$36,$36,$36,$FF,$00,$FF,$05,$56

Okay

We cannot save space compressing 3 $36's, so we do not bother.
$FF,$00 can mean that the flag is really a $FF value from the data because we would never use a flag to say that there are 0 consecutive bytes of $XX so, $FF,$00 is better than $FF,$01,$FF

This means that if we have two or more consecutive $FF's, we would want to use

$FF,$02,$FF because our little 0 trick will not work

Now, what if we have a $00 in the data?

Data: $FF,$00

Compressed:
$FF,$00,$00

The reason of cource is that we have only one $FF and the first $00 is ignored because it just tells us that $FF is not a flag, so we must have another $00.

I doubt this will happen very often, but the flag shoud be a value that does not occur in the data much. $FF often occurs, so it should not be a variable.

Whatever you do, do not use $C9 as a flag because there are many rets that will magically take up an extra byte when compresssed if c9 is the flag.

BTW, the most interesting thing I learned today is that it is impossible to compress random noise. Rememember, random does not equal pseudo random in this case.

[NETWizz]

Justin, the last flaw in our encryption/decryption routine is as follows:

If a byte is repeated more than 255 times, we cannot compress it well.

For example:

$12 259 times


$FF,$FF,$13,$FF,$04,$13

Put simply, 255 is the maximum in one run.

We would need more runs if more than 256 bytes followed.

In this situation, if we used a 16-bit (Word) to specify the number, we would have

$FF,$0103,$13

I put $0103 together because it is a 16-bit word that takes up two bytes. The $01 part represents 256 and the 03 the other three. When added, you realize that you have 259 $13's

Now, that you have upgraded to 16-bit encoding, you have new problems

1. For every run less than 256, a byte is wasted e.g. $FF,$00,$04,$13 and, we would not even bother to compress that because there is no savings.

2. We would have to specify the encoding at the beginning of the compressed data and make two passes. One to compress it at 16-bit and one to compress it with 8-bit encodign to see which yields the smaller result.

You would specify the encoding at the beginning

e.g.

$00 for 8-bit and $01 for 16-bit...

Still, you would probably never use 16-bit unless you are compressign an all black picture or something because it is rare for more than 255 bytes of consecutive code to be in a program unless it is pic data or free ram. Besides, if you have more than 255 consecutive bytes, you are going to save many bytes anyway.

259 bytes to 6 bytes is good enough if you ask me

One last thing, who is going to mkae this super compression program? I think it would be quite difficult to make; thouth, eventually I may make an attempt.

[Justin W.]

Ok well let me explain. The best method is to search your data to see if there is a byte that does not recur in your data. If there isn't you find the byte that occurs the least.

Then when you are compressing the data and you find the flagbyte value you turn it into a run.

flagbyte=$02

.db $01,$01,$01,$01,$01,$02,$03,$03,$03,$03,$03,$03

compressed

.db $02,$05,$01,$02,$01,$02,$02,$06,$03


This is the only way you could ever end up with a higher data size than the original data. Yet it is unlikely that the user will use all 256 bytes within their data block. So you just simply find a byte that is unused and set it as a flag byte.


Now for the 16bit size for large data blocks that are the same. I would simply set a flag for data less than or equal to 255, and then set a secondary flag for a 16bit size.

[Justin W.]

If it is necessary I can code it rather easily. It is not that hard and I am currently working on a rle compression program for pictures. It's called Zippic and it will compress pics into an appvar. This of course will be useful to basic programmers as it will allow them to have many more pics.

[David]

The standard of RLE encoding is that 0 is equal to 256 repetitions. Even though it looks weird, it is best kept that way for compability.

I wrote a RLE compression routine once. I can post it to you if you want.

If you are trying to compress a tilemap, you often use a limited number of bytes.
Let's say you have 16 tiles numbered 0-15. Then you'd only need the lower 4 bits (a nibble) to represent one tile (2^4 = 16). In other words, it would be possible to compress the tilemap 50 % as one could store two tiles in one byte

[NETWizz]

My compression routine where you do not encode data unless you have more than 3 consecutive bytes is faster and will compress more completely.

As for RLE, you are correct, it will work.

I think it would be cool to save the uncompressed size and save a byte for flags. When In Nimbus, it could be called an RLE compressed Ion, etc

Then, when they wish to run it, the size is saved, so we inseart the correct number of bytes at usermem and uncompress it there. If writeback is neccessary, we would make the changes to the uncompressed data and recompress.

What do you think?

We could even wright a VB or C program to compress all NimbusOS programs.

[Justin W.]

That actually sounds really cool. You wouldn't expect to get really high compression unless they have large data blocks in their code though.

[Justin W.]

Oh and here's a screen shot of the grayscale in action. It actually looks better on calculator.

[Justin W.]

Also keep this in mind that, that screenshot is one of a ti83+ with perfect 4-level grayscale. Thanks to one of my fellow programmers at maxcoderz. Diederik Kingma.

[NETWizz]

David, please post the RLE encoder.

Juistin, How does your greyscale engine work? I would assume it uses system interrupts.

[David]

Here's the code for the rle encoder:

[Justin W.]

[NETWizz]

I thought you said it was 4 level greyscale.

I guess 2 level is black, so you must have two shades of grey.

I know that interlace means that every other line is drawn, but how is the image drawn exactly?

[NETWizz]

[Justin W.]

The person to ask how it works and could explain it to you the best is Diederik Kingma. [email=dedurk@hotmail.com]dedurk@hotmail.com[/email]