New efficient metasprite format

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

User avatar
Bregalad
Posts: 8007
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

New efficient metasprite format

Post by Bregalad » Mon Jan 21, 2013 6:01 am

I'm about to implement a new metasprite format that increases the efficicency of coding sprites dramatically, as suggested by Drag.

It is backwards compatible with the old format, so that when I implement it I can slowly change my sprites and test them ones after eachother without having all the "not yet converted to new format" ones display as garbage.

I don't know but I feel like it should be possible to improve it even further. Like by using the rarely used priority bit for compression.
Anyhow, here is the format :

1) 1st sprite is NEVER compressed
2) Extra bits in the attribute byte specify how the *next* sprite is compressed, as follows :

Code: Select all

** THIS IS DEPREDATED -- SEE MY LATER POST FOR A BETTER VARIANT **

yyyyyyyy --- Sprite Y coordinate (ommited if compression 1, 2, 3, 5, 6, 7)

vhbcccpp --- Attribute byte (always)
||||||||
||||||++---- Sprite Colour
|||+++------ Compression bits : 000 - next sprite is not compressed (next has : Y, AT, Tile, X)
|||                             001 - next sprite has X coordinate = current X + 8, and Y = current Y (next has : AT, Tile)
|||                             010 - next sprite has Y coordinate = current Y + 8 (next has : AT, Tile, X)
|||                             011 - next sprite has Y coordinate = current Y + 8, and X = first sprite's X (next has : AT, Tile)
|||                             100 - this is the last sprite of the metasprite (no next sprite)
|||                             101 - same as 001, with tile # = current tile # + 1 (next has : AT)
|||                             110 - same as 010, with tile # = current tile # + 16 (next has : AT, X)
|||                             111 - same as 011, with tile # = current tile # + 1 (next has : AT)
||+--------- Behind BG : If set, the sprite is behind background
|+---------- Horizontal flipping
+----------- Vertical flipping

tttttttt --- Tile number (ommited if compression 5, 6, 7)

xxxxxxxx --- Sprite X coordinate (ommited if compression 1, 3, 5, 7)
Last edited by Bregalad on Tue Feb 26, 2013 1:56 pm, edited 1 time in total.

User avatar
tokumaru
Posts: 11932
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: New efficient metasprite format

Post by tokumaru » Mon Jan 21, 2013 6:36 am

Interesting idea, metasprites will probably compress very well with this. There's a trade-off though, interpreting the metasprite definitions will take significantly longer.

User avatar
Bregalad
Posts: 8007
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: New efficient metasprite format

Post by Bregalad » Mon Jan 21, 2013 6:48 am

Sure, especially since I'll have to first decompress from this format to the "regular" 4-byte format, and then process the metasprite in OAM. Because of sprite cycling, currently I have a routine that mazes sprites "forwards" or "backwards".

Now since we don't know the total # of sprites before decoding it, and since each sprite has a variable # of bytes, it's impossible to draw it "backwards" without decompressing it first, so either I decompress all my sprites each time, or I have to give up sprite cycling (which is a bad idea).

Now if I use the normally unused priority bit, I could come up with 14 different predictions for the next sprite (instead of only 6), but I don't know how I could come up with so many predictions, haha. I guess I'll have to take a closer look at my sprites' pattern and see what comes regularly.

EDIT : Oh I know, instead of having 14 predictions, I should allow to make runs or combos of the same prediction. For example, if the next 2 sprites are aligned horizontally and are increasing tile numbers, I could store them by prediction. This way I could have 3 or 4 sprites in only 4 bytes ! (and without refraining to have the freedom to arrange my sprites as I like, unlike SMB which forces a simple rectangular pattern for enemy sprites)

User avatar
tokumaru
Posts: 11932
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: New efficient metasprite format

Post by tokumaru » Mon Jan 21, 2013 7:30 am

Bregalad wrote:Sure, especially since I'll have to first decompress from this format to the "regular" 4-byte format, and then process the metasprite in OAM. Because of sprite cycling, currently I have a routine that mazes sprites "forwards" or "backwards".
Personally, I prefer to handle sprite cycling as they are output to the OAM mirror, but interpreting all the different compression combinations should still take a while.
Now since we don't know the total # of sprites before decoding it, and since each sprite has a variable # of bytes, it's impossible to draw it "backwards" without decompressing it first, so either I decompress all my sprites each time, or I have to give up sprite cycling (which is a bad idea).
Yeah, not knowing the number of sprites could be a problem. If the priorities between the sprites of the same metasprite don't matter, you could just render the sprites in the "top layer" from slot 0 up and the sprites in the "bottom layer" from slot 63 down, without the need to know how many sprites each metasprite has. Later you could maze each half or just randomize the order in which objects are drawn.
Now if I use the normally unused priority bit
"Normally unused" is very relative... You may not use it frequently, but I sure take it into consideration every time I start designing a game.

User avatar
Bregalad
Posts: 8007
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: New efficient metasprite format

Post by Bregalad » Mon Jan 21, 2013 7:50 am

Personally, I prefer to handle sprite cycling as they are output to the OAM mirror, but interpreting all the different compression combinations should still take a while.
Yes, but my game has a top-down view, and sprite priorities are important, as they are part of the view, unless the completely bidimentional platformers.
Yeah, not knowing the number of sprites could be a problem. If the priorities between the sprites of the same metasprite don't matter, you could just render the sprites in the "top layer" from slot 0 up and the sprites in the "bottom layer" from slot 63 down, without the need to know how many sprites each metasprite has
I don't use sprite multi-layering (because I'd end up with flickering sprites and I don't want that), and the idea to go backwards in memory is good, but it will also reverse the priorities... so I'd have to sort my priorities backwards, and then maze the sprites forwards, but by going backwards in memory... could be an interesting alternative.
"Normally unused" is very relative... You may not use it frequently, but I sure take it into consideration every time I start designing a game.
Currently I only use it for sprite zero hits, and they are mazed separately from other sprites of the game. But if I ever wanted to use this bit I could still do it while using it for compression - I have a global variable that is XOR-ed with the attribute bytes when mazing a metasprite. It was normally meant for palette swapping enemies (without re-defining their metasprites of course !). But if I set this global variable to $20 I could still force objects to be behind BG. I don't think I'll want to do this, but I could, so it's not like this bit is lost. It's just that it will remove the feature to have sprites above and blow BG in the same metasprite, and I don't think this could ever be put to good use, at least not in a simple game like mine.

Drag
Posts: 1332
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: New efficient metasprite format

Post by Drag » Tue Jan 22, 2013 12:50 am

With the priority bit, I don't think it's common to have a metasprite where the individual tiles have seperate priorities, so you could probably throw out the priority bit, and apply the priority to the metasprite as a whole.

Edit: So yeah, exactly what you said. :P

User avatar
tokumaru
Posts: 11932
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: New efficient metasprite format

Post by tokumaru » Tue Jan 22, 2013 5:23 am

You guys have a valid point about the priority bit. It can be used for compression because the same priority can be applied to the whole metasprite.

User avatar
Dwedit
Posts: 4392
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: New efficient metasprite format

Post by Dwedit » Tue Jan 22, 2013 1:01 pm

I thought the point was to just copy the attributes byte into the OAM unchanged, so that's why you have the bits exactly matching up.
Anyway, when I was making metasprites, I had the option available to OR/XOR the attributes byte with something else, so you could easily make palette-swapped sprites. Maybe you could handle flipped versions of sprites and stuff that way, treat the flip flag in the attributes byte as a request for a flipped version of the metasprite, and change the X/Y advance depending on flip flags.
Last edited by Dwedit on Tue Jan 22, 2013 1:34 pm, edited 1 time in total.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

3gengames
Formerly 65024U
Posts: 2281
Joined: Sat Mar 27, 2010 12:57 pm

Re: New efficient metasprite format

Post by 3gengames » Tue Jan 22, 2013 1:20 pm

IMO, you could use a $08 or $FA value in RAM and add it to the sprite when the X location is changed and just add that, so if it's reverse, the engine will change 1 value and continue like normal. Same with vertical flips. When it puts the attribute for the sprite to the screen, it then just could OR with the RAM for the object and have everything set up correctly.

You could also have a "header" byte in the data to tell other stuff, like pallet used (4 bits, only use one bit of the pallet info in the sprite data to select which it is assigned). Then, you could have a RAM byte in the object to set global entity attributes like the flips and priority. For 1 byte of RAM and 1 of ROM, you get lots of more options for each sprite so it seems viable to me:

Code: Select all

RAM for object: VHP0.0000 ;VPH are in the object data for that character. All 0's can be used by other stuff.
Header byte: ****.ppPP ;Extra 4 bits are unused. PP means the most used pallet, pp is the secondary pallet.

yyyyyyyy --- Sprite Y coordinate (ommited if compression 1, 2, 3, 5, 6, 7) ;Same

ccccccpp --- Attribute byte (always)
||||||||
||||||++---- Sprite Colour
++++++------- Compression bits : ***000 - next sprite is not compressed (next has : Y, AT, Tile, X)
                                001 - next sprite has X coordinate = current X + 8, and Y = current Y (next has : AT, Tile)
                                010 - next sprite has Y coordinate = current Y + 8 (next has : AT, Tile, X)
                                011 - next sprite has Y coordinate = current Y + 8, and X = first sprite's X (next has : AT, Tile)
                                100 - this is the last sprite of the metasprite (no next sprite)
                                101 - same as 001, with tile # = current tile # + 1 (next has : AT)
                                110 - same as 010, with tile # = current tile # + 16 (next has : AT, X)
                                111 - same as 011, with tile # = current tile # + 1 (next has : AT)



tttttttt --- Tile number (ommited if compression 5, 6, 7)

xxxxxxxx --- Sprite X coordinate (ommited if compression 1, 3, 5, 7)
Don't wanna rewrite it, but I'll give you that idea to mess with and see if you would like to extend on that idea. Honestly, I'm writing an animation engine with metasprites (well, I have the loader done, the actual engine needs written) But I'll probably use something like I posted in this message.

ETA: If you flip a sprite any unused bits on the inner side will cause a (unusepixel*2) movement when flipped the other way. You could use the unused header bits as two 2-bit values for XUnused*(1,2,4 however many pixels best fits your sprites) and same for the Y. YUnused*(1 or 2 or 4) and then just add to the number when flipping.
Last edited by 3gengames on Mon Feb 25, 2013 7:41 pm, edited 2 times in total.

User avatar
tokumaru
Posts: 11932
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: New efficient metasprite format

Post by tokumaru » Tue Jan 22, 2013 3:25 pm

Dwedit wrote:I thought the point was to just copy the attributes byte into the OAM unchanged, so that's why you have the bits exactly matching up.
That is better, but even if you do some manipulation, having most bits in the correct places still helps.
I had the option available to OR/XOR the attributes byte with something else, so you could easily make palette-swapped sprites.
I do that too. The function that draws metasprites takes a byte that it XORs with the attributes of every sprite.
Maybe you could handle flipped versions of sprites and stuff that way, treat the flip flag in the attributes byte as a request for a flipped version of the metasprite
I do exactly that. The individual sprites of the metasprite can have different flipping configurations (think standing big Mario from SMB1, who has a mirrored body), but the flipping bits in the modifier byte (the one that's XORed) are treated as requests to flip the metasprite, and they conveniently toggle the default flipping bits of each sprite.
and change the X/Y advance depending on flip flags.
Yes, you could easily use those bits to define the increment values in RAM.

Bisqwit
Posts: 248
Joined: Fri Oct 14, 2011 1:09 am

Re: New efficient metasprite format

Post by Bisqwit » Mon Feb 25, 2013 5:15 pm

How would you suggest as for inter-metasprite compression?
For example, when an actor has two animation frames, and the lower portion in both frames is identical.
Or when you have an actor that is identical to another actor, except for a palette swap.

Sik
Posts: 1589
Joined: Thu Aug 12, 2010 3:43 am

Re: New efficient metasprite format

Post by Sik » Mon Feb 25, 2013 6:57 pm

Bisqwit wrote:Or when you have an actor that is identical to another actor, except for a palette swap.
You would most likely just pass it as a parameter to the subroutine and let it modify the palette on the fly. Then you reuse the same metasprite. You can even use it for stuff like e.g. the starman effect in Mario without much effort (Battle City also uses this for coloring enemies with more than 1HP left, those alternate between two palettes every frame).

User avatar
tokumaru
Posts: 11932
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: New efficient metasprite format

Post by tokumaru » Mon Feb 25, 2013 8:20 pm

Palette swap is easy: use a modifier byte that's EORed against the attribute byte of each sprite. This allows not only palette swaps, but also X/Y flipping and priority control.

Reusing parts of other metasprites is trickier... Maybe you could have a special code that acts like a JSR of sorts for metasprites, so you can "call" parts that are shared between metasprites. Or maybe you can allow animation frames to have more than 1 metasprite, so you can combine smaller metasprites as necessary. I don't think this is worth it though.

Sik
Posts: 1589
Joined: Thu Aug 12, 2010 3:43 am

Re: New efficient metasprite format

Post by Sik » Tue Feb 26, 2013 12:16 am

tokumaru wrote:Palette swap is easy: use a modifier byte that's EORed against the attribute byte of each sprite. This allows not only palette swaps, but also X/Y flipping and priority control.
Flipping is not as trivial since you also need to modify the coordinates of the sprites. It's a good starting point for that goal, though.

3gengames
Formerly 65024U
Posts: 2281
Joined: Sat Mar 27, 2010 12:57 pm

Re: New efficient metasprite format

Post by 3gengames » Tue Feb 26, 2013 12:26 am

For the multiple sprites, you can put the palette data with the CPU RAM attributes base byte for said sprite. Make the pallet 3 bites. If the 3rd new bit is modified, modify the attributes used to upload that one metasprite, and have everything else function as normal, and treat attributes with only 2 bits used as additions to the base 2 bits used for the global version. That wouldn't work too well using the same metasprite if you have palette 3 shared overlays and palette 1+2 the main colors for said characters as it would try to add and add to slot 4 not 3 like the base metasprite, but it's a beginning to an idea.

Post Reply