I made a sprite cutter tools for the resource compiler in SGDK (so for the Sega Megadrive but it could be easily modified to SNES sprites).
Basically i have 2 methods :
 a fast method just trying to fit the sprite into the smallest number of 8x8 to 32x32 blocs then merging adjacent blocs when possible. This already give descent results but definitely not perfect.
 a slow method based on genetic algorithm to find better solutions than the fast solution.
The slow method can be really slow to optimize a single sprite ! But i guess it would work much faster for SNES sprites as it more constrained in possible combinations (only 2 sprites size).
Code is here (java code) :
https://github.com/StephaneD/SGDK/blob ... utter.java
Has anybody ever made an algorithm for metasprite optimizing

 Posts: 2951
 Joined: Wed May 19, 2010 6:12 pm
Re: Has anybody ever made an algorithm for metasprite optimizing
I don't know what happened to Anonimzwx from Discord, because I heard he was making one of these things. I decided to try to come up with (I know you're probably going to facepalm this) an algorithm that is doable on a 65816, because that's all I know. So I would have to divide this into 3 parts:
1) Calculate the smallest number of 16x16 sprite cells possible for the metasprite.
2) Calculate the smallest number of 32x32 and 16x16 sprites possible of the same number of 16x16 sprite cells found in step 1
3) Arrange sprites so they have the least amount of scanline overlapping
z = minimum number of 16x16 sprite cells
a = (# of solid pixels)/256 rounded up
b = (width/16 rounded up)*(height/16 rounded up)
a <= z <= b
if a = b, then z = a = b
Something I've discovered is, with arranging 16x16 sprites in a larger metasprite, there is at most 16 possible pixel positions the first sprite could be, if scanning from left to right, up to down. The first choice for the first 16x16 sprite cell would be the first position where there is at least one solid pixel on both the top row and left column of. The last choice would be the first position with a solid top left corner pixel. For every 1 of 16 or less first sprite positions, there are 16 or less positions for the 2nd sprite, and for every 2nd sprite position there is 16 or less 3rd sprite positions.
1) Calculate the smallest number of 16x16 sprite cells possible for the metasprite.
2) Calculate the smallest number of 32x32 and 16x16 sprites possible of the same number of 16x16 sprite cells found in step 1
3) Arrange sprites so they have the least amount of scanline overlapping
z = minimum number of 16x16 sprite cells
a = (# of solid pixels)/256 rounded up
b = (width/16 rounded up)*(height/16 rounded up)
a <= z <= b
if a = b, then z = a = b
Something I've discovered is, with arranging 16x16 sprites in a larger metasprite, there is at most 16 possible pixel positions the first sprite could be, if scanning from left to right, up to down. The first choice for the first 16x16 sprite cell would be the first position where there is at least one solid pixel on both the top row and left column of. The last choice would be the first position with a solid top left corner pixel. For every 1 of 16 or less first sprite positions, there are 16 or less positions for the 2nd sprite, and for every 2nd sprite position there is 16 or less 3rd sprite positions.
Re: Has anybody ever made an algorithm for metasprite optimizing
The GenMeta tool now has a SNES version. Right now it's just "SNES sprite sizes, and export SNEScompatible PNG"  there is no checking that you only use two sizes, and the sprite size info is not exported since it's not a part of the metasprite format.