Has anybody ever made an algorithm for metasprite optimizing

Discussion of development of software for any "obsolete" computer or video game system. See the WSdev wiki and ObscureDev wiki for more information on certain platforms.
Stef
Posts: 263
Joined: Mon Jul 01, 2013 11:25 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Stef »

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/Stephane-D/SGDK/blob ... utter.java
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimizing

Post by psycopathicteen »

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.
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Has anybody ever made an algorithm for metasprite optimizing

Post by calima »

The GenMeta tool now has a SNES version. Right now it's just "SNES sprite sizes, and export SNES-compatible 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.
Post Reply