This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

New efficient metasprite format

New efficient metasprite format
by on (#106565)
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:
** 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)
Re: New efficient metasprite format
by on (#106566)
Interesting idea, metasprites will probably compress very well with this. There's a trade-off though, interpreting the metasprite definitions will take significantly longer.
Re: New efficient metasprite format
by on (#106567)
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)
Re: New efficient metasprite format
by on (#106568)
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.

Quote:
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.

Quote:
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.
Re: New efficient metasprite format
by on (#106569)
Quote:
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.

Quote:
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.

Quote:
"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.
Re: New efficient metasprite format
by on (#106620)
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
Re: New efficient metasprite format
by on (#106624)
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.
Re: New efficient metasprite format
by on (#106629)
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.
Re: New efficient metasprite format
by on (#106630)
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:
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.
Re: New efficient metasprite format
by on (#106644)
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.

Quote:
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.

Quote:
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.

Quote:
and change the X/Y advance depending on flip flags.

Yes, you could easily use those bits to define the increment values in RAM.
Re: New efficient metasprite format
by on (#108325)
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.
Re: New efficient metasprite format
by on (#108329)
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).
Re: New efficient metasprite format
by on (#108335)
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.
Re: New efficient metasprite format
by on (#108339)
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.
Re: New efficient metasprite format
by on (#108340)
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.
Re: New efficient metasprite format
by on (#108342)
Sik wrote:
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.

Yes, but in my case at least, besides being used to flip the bits in the attribute bytes, the modifier byte is checked at the beginning of the metasprite function and used to adjust the sprite coordinates and increments.

EDIT: I also should point out that EORing palette bits wouldn't work so well if you use more than one palette in the same metasprite... for example, say that an enemy is green and wears a white shirt, so it uses different palettes for the green and white parts. If you want to recolor that enemy so that it's blue but still wears a white shirt, that wouldn't work, since the palette of the shirt would be changed as well. One solution would be to use OR or AND instead of XOR, so that you can use palette 0 (%00) or 3 (%11) for the one you don't want to change. That would require more careful planning of the palettes.
Re: New efficient metasprite format
by on (#108358)
I think I got a better idea, that optimises the usage of all 4 unused bits (counting the priority bit as unused).
I forgot the idea to predict the attribute byte, as it would be very easy to screw up and end in an infinite loop.

Just remember, as I said in my 1st post :
- Attribute byte is always present
- X, Y and tile # bytes are either predicted from the previous sprite, or present
- Prediction data for sprite N+1 is stored in the data of sprite N
- The first sprite is never compressed (always 4 bytes)

Code:
Code:
yyyyyyyy --- Sprite Y coordinate (if required)

vhtyxxpp --- Attribute byte (always)
||||||||
||||||++---- Sprite Colour
||||++------ X position of next sprite (00 : required, 01 : X pos of this sprite + 8,
||||                                    10 : X pos of the fist sprite, 11 : Escape code for last sprite)
|||+-------- Y position of next sprite (0 : required, 1 : Y pos of this sprite + 8)
||+--------- Tile number of next sprite (0: required, 1 : Tile number of this sprite + 1)
|+---------- Horizontal flipping
+----------- Vertical flipping

tttttttt --- Tile number (if required)

xxxxxxxx --- Sprite X coordinate (if required)


The enthropy of the 4 unused bits are not fully used, as 4 of the 16 possible shemes have the same effect (finishing the meta sprite), but there is still 12 predictions available.
As opposed to my first idea for the codec, it makes it possible for tiles which are gird aligned in a direction but not the other to be still compressed efficiently. Those are pretty common, every time an enemy has a tail I use this, so the tail is in the middle of the sprite but still takes only 1 tile of width/height, so I move it 4 pixels apart the "gird".

Again, this is fully compatible with uncompressed sprites, except that you have to OR the attributes of the last sprite with $0c for it to work.

Quote:
I also should point out that EORing palette bits wouldn't work so well if you use more than one palette in the same metasprite... for example, say that an enemy is green and wears a white shirt, so it uses different palettes for the green and white parts. If you want to recolor that enemy so that it's blue but still wears a white shirt, that wouldn't work, since the palette of the shirt would be changed as well. One solution would be to use OR or AND instead of XOR, so that you can use palette 0 (%00) or 3 (%11) for the one you don't want to change. That would require more careful planning of the palettes.

Mmh, you got a point !
The problem with the AND/OR approach is that it's then impossible to access all 4 palettes by the means of palette swapping unless you use palette 3/0 (respectively). However it will fix the problem you issused, which is a good thing.

Quote:
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.

Yes, usually you also need to negate (XOR with $ff) the X coordinate.
You could also do that vertically, but unless you have a level like Gravity Man's, I doubt it will be very useful.
Re: New efficient metasprite format
by on (#108364)
Bregalad wrote:
Quote:
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.

Yes, usually you also need to negate (XOR with $ff) the X coordinate.

XOR $FF and then add 1 to it. (two's complement)

You can easily add the 1 to it by setting carry before you ADC the metasprite's x coordinate to the tile's x coordinate.
Re: New efficient metasprite format
by on (#108370)
tokumaru wrote:
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.

I do something like this, and the savings I get are pretty decent, with the compressed size being about 70% of uncompressed size. Also I find specifying the metasprites is a lot easier being able to reuse subparts. This probably depends on the game though.

That said, I'm beginning to question if metasprite compression is really worth it. They don't take up a lot of space compared to other things, and a significant amount of time per frame is spent drawing metasprites. Having them uncompressed would speed that up, and I could probably get a lot more objects on screen before lagging.
Re: New efficient metasprite format
by on (#108371)
To really flip sprites, you need to do a lot more than modify the X coord by 2's complement. You need to add (tilewidth-1)*8 to it, and then store a variable in RAM that's either 8 or -8, and then just use a CLC+ADC with it each time you move either a X or Y coord. Not that hard, but still, it's something to know before hand.

(I'm writing a metasprite engine at this very moment....or at least am deep in to planning and am about to start writing the code very soon, so whatever I do I'll probably input here for ideas on how to make it better.)
Re: New efficient metasprite format
by on (#108472)
@Bregalad: Just curious, how many metasprite frames do you have and how much data is there? Are you finding trading time for space savings to be a win? It almost seems to be worth encoding the mirrored versions of the metasprites rather than doing the mirroring in code?

What I ended up doing was having a separate page for static data like metasprites. Each sprite in the metasprite takes up 4 bytes that match the OAM layout (delta y, palette mask, index, delta x) in order to trade size for speed.
Mirrors are encoded instead of computed. Each frame of body animation has socket locations for arms and head so the character can aim in any directions for any frame of animation. I need to take a second pass over the main character to get a smoother run sequence so I'm revisiting my scheme. I think I'll need to make a tool for metasprite layout (so far I've been doing it by hand.)
Re: New efficient metasprite format
by on (#108570)
3gengames wrote:
To really flip sprites, you need to do a lot more than modify the X coord by 2's complement. You need to add (tilewidth-1)*8 to it, and then store a variable in RAM that's either 8 or -8, and then just use a CLC+ADC with it each time you move either a X or Y coord. Not that hard, but still, it's something to know before hand.

(I'm writing a metasprite engine at this very moment....or at least am deep in to planning and am about to start writing the code very soon, so whatever I do I'll probably input here for ideas on how to make it better.)


I actually made a separate sprite drawing routine that does SBC instead of ADC for flipping entire metasprites. It seems like a tacky solution, but it actually saves a lot of cycles in the end. This way you don't have to include another variable into the calculation of every sprite position in a metasprite.