Algorithm for splitting sprites
Posted: Tue Aug 15, 2017 1:50 am
Large sprites need to be split into smaller ones (since the hardware can't do over 32×32 pixels), but processing them manually can be tedious, especially for very large sprites (I just come from manually splitting a sprite into 17 smaller ones, ugh). The problem is coming up with a decent algorithm. After thinking for a while I've come up with the following idea, it's far from perfect but should give reasonable enough results (at least when it comes to avoiding wasting space in large transparent areas).
No implementation yet (I don't have time right now), I may add something like this to mdtiler later. Still, leaving this here in case somebody wants to give it a try in their own tools. Also point out if I overlooked anything! (・<・)
Downsides of the algorithm:
As mentioned earlier it can't take advantage of repeated sprites. You could make it check for repeated spans and reuse them, but not only it'll be quite slower but also because span shapes are automatically generated it may decide to generate them in a way that prevents potential reuse. I suppose you could work around that by accounting for common patterns (e.g. if the bitmap is symmetric, you can make it process only half the bitmap). Also depends how badly you need to reuse tiles (vs how much of a big deal is sprite overflow).
The other big issue is in which format we'll spit out the sprite mappings. For assembly we could use the format I normally use these days, which is basically four words for each sprite entry, then one more word as a sentinel (to mark the end):
If you want something to spit out to mdtiler, huh you can issue tiles commands:
I have no idea what SGDK uses, or if it even has something like this. Time to consider =P (assuming you don't just make it an array with a bunch of words which is basically the same thing as my assembly format)
No implementation yet (I don't have time right now), I may add something like this to mdtiler later. Still, leaving this here in case somebody wants to give it a try in their own tools. Also point out if I overlooked anything! (・<・)
Downsides of the algorithm:
- It assumes all sprites are aligned to a tile boundary (no pixel-level optimization, sorry)
- The resulting arrangement isn't pretty (it's rarely worse than hand-optimizing though)
- It doesn't take advantages of sprites that could be reused
- Should still get rid of a lot of waste in empty spaces
- Scan through the whole image looking for empty tiles (and mark them as such). From hereon we'll work at the tile level.
- Scan through each row and make as many horizontal sprites spans as possible (i.e. from 1×1 to 4×1). If a span would be too large you'd need to break it down.
- Scan through vertically looking for consecutive spans that have same width and line up and merge them. Again, make sure they can't be too large (i.e. larger than 4 tiles high)
As mentioned earlier it can't take advantage of repeated sprites. You could make it check for repeated spans and reuse them, but not only it'll be quite slower but also because span shapes are automatically generated it may decide to generate them in a way that prevents potential reuse. I suppose you could work around that by accounting for common patterns (e.g. if the bitmap is symmetric, you can make it process only half the bitmap). Also depends how badly you need to reuse tiles (vs how much of a big deal is sprite overflow).
The other big issue is in which format we'll spit out the sprite mappings. For assembly we could use the format I normally use these days, which is basically four words for each sprite entry, then one more word as a sentinel (to mark the end):
Code: Select all
SprMerlina_Idle1:
; x, y, tile, size
dc.w -$14, -$20, 0, %1000
dc.w -$1C, -$18, 3, %1110
dc.w -$14, $00, 15, %1001
dc.w $04, -$20, 21, %0101
dc.w $04, -$10, 25, %0000
dc.w $04, -$08, 26, %0110
; sentinel
dc.w $8000
Code: Select all
layout sprite
tiles 1 0 3 1
tiles 0 1 4 3
tiles 1 4 3 2
tiles 4 0 2 2
tiles 4 2 1 1
tiles 4 3 2 3