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