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.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Has anybody ever made an algorithm for metasprite optimizing

Post by psycopathicteen »

An algorithm for taking a large character, and finding what arrangement of sprites fit it within the least amount of sprites.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by tepples »

Do you want approximate or provably exact?

There was an approximate metasprite optimizer for GBA called Objective, but it appears to be a dead link now.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Oziphantom »

Yeah the "coding jesus" CodeHut mentions one I'm fairly sure, the devs for Evermore mention doing it in interviews. I'm sure every game company would have made one back in the day, for SNES, MD, Amiga etc then in 3D we use to make systems to make bounding boxes for 3D objects.

It depends if you treat it as strict bitmap, or if you want to find as much of matching sprites to cut down on the number of tiles, and then you have Z order so you hide parts. Starts getting into GA territory.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by tepples »

The sprite sheet build process for The Curse of Possum Hollow involves one of the devs using a text editor to make a "strips file" for each sprite sheet that lists rectangular nonblank areas of each cel and which of four palettes to use when converting each rectangular area. The rectangles can overlap, one for one palette and one for another, if you need more colors and don't care about flicker. Then the tool converts each rectangle to a regular grid of 8x16-pixel sprites and extracts tile data from that.

When I worked on that game, Greg Caldwell and I agreed that I could release some non-game-specific parts of the engine as open source. So far, this has included Popslide and an NES 2.0 header builder. I might end up packaging the metasprite builder as well if I can figure out how to make a simple tech demo out of it.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Kasumi »

I have. (Sort of.) It seems like it'll never get clean enough to release, though. Here's Elena from 3rd Strike on NES
Image
It doesn't exactly focus on the fewest number of sprites, though. It tries to find a balance between sprite tiles and sprites. It's definitely not as good as one can do manually in either area, but for stuff like this it's a benefit just not doing it manually.

The algorithm does guess palettes (even if sprite overlays are needed), but it's worse at that than other things.

tl;dr: Import a frame sequence for a large character, get exported data in an NES ROM. But there's not too much about the algorithm that's NES specific. It could work with palettes of 16 colors and different sprite sizes or whatever with some tweaks. I do have plans to make it focus harder on fewer sprites, but I'll probably never computer science it out enough to try lots of stuff to get the absolute lowest sprite count.

Edit: Here's its process for taking the tiles:
Image
It does one pass to guess palettes (if you don't provide a palette), then eats away the sprites from the corners.
Edit2: It also does "deep deduplication" to further reduce tile count. I don't remember if that's reflected in the tile count above.
The example I give is this image:
Image
All of those are the same tile, just offset or flipped differently. "Deep deduplication" would make all uses of all those tiles into one unique tile.
Last edited by Kasumi on Fri Sep 14, 2018 10:34 am, edited 2 times in total.
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by calima »

I don't remember if I've mentioned it here before, but I made a tool that lets you quickly do it yourself:
https://github.com/clbr/genmeta
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by psycopathicteen »

calima wrote:I don't remember if I've mentioned it here before, but I made a tool that lets you quickly do it yourself:
https://github.com/clbr/genmeta
Nice, can this tool be used for SNES sprites too?
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by calima »

Yes, though you have to only use the sizes you have configured, and need to post-process the generated metasprites. It takes up-to-16 color PNG as input and exports a C array source, so postprocessing for SNES would be pretty easy, write your converter in C and include the metasprites there.

edit: Actually, I remembered that big SNES sprites have some weird tile ordering in VRAM. So that's another thing you'd need to take care of.
User avatar
thefox
Posts: 3134
Joined: Mon Jan 03, 2005 10:36 am
Location: 🇫🇮
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by thefox »

calima wrote:I don't remember if I've mentioned it here before, but I made a tool that lets you quickly do it yourself:
https://github.com/clbr/genmeta
Hey, that's cool! I've thought about doing one like this too!

As for automatic algorithms, I did write one a long time ago. It was a genetic algorithm and gave decent results, although it was quite slow. I used it for most of the sprites in STREEMERZ. I wish there was something better, though.

Bananmos wrote a tool called Tilificator: viewtopic.php?f=21&t=8589
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
User avatar
Drew Sebastino
Formerly Espozo
Posts: 3496
Joined: Mon Sep 15, 2014 4:35 pm
Location: Richmond, Virginia

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Drew Sebastino »

Sorry for not contributing any to the discussion, but talking about algorithms for creating the most efficient metasprites, I thought everyone here would enjoy this:

Image

It starts to make sense as to why these games were so relatively huge... (And why arcade game companies created hardware with such high sprite per scanline limits. :lol:)
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by psycopathicteen »

Was that how they were done in the original arcade machine?
User avatar
Drew Sebastino
Formerly Espozo
Posts: 3496
Joined: Mon Sep 15, 2014 4:35 pm
Location: Richmond, Virginia

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Drew Sebastino »

This is a long time to answer something this small, but I checked it in MAME's tile viewer and yes, it actually is that wasteful.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by tepples »

Technically, it's not "waste" unless you're seeing dropout/flicker or you're on the boundary between ROM sizes. Otherwise, optimization is a "waste" of programmer time, which I imagine was of the essence in the coin-op market.
Bananmos
Posts: 552
Joined: Wed Mar 09, 2005 9:08 am
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Bananmos »

Tilificator (which TheFox mentioned, and I think was used for the title screen in Streemerz IIRC) was one I made a few years back, and source can be found here: https://sourceforge.net/p/tilificator/wiki/Home/

Annoyingly, the documentation wiki page I wrote no longer exists, as I think Sourceforge ditched that part of their hosting service :(

It allows you to choose whether you're optimising for sprites/scanlines, tiles or other things. It also allows you to use different algorithms, of which "TilingMethodDragQueen" was the most advanced. Though its complicated Python code to avoid having to test invalid combinations of deltas for adjacent sprites might very well be less efficient than say a brute-force method running on the GPU which does things in a "less clever" way.

All of the methods have a major drawback though: All the conversion is done sequentially, and tiles are only matched against previously converted images so making a poor choice for the first image affects all subsequent ones. Adding some pre-step which does image correlation could probably fix that.

But I've since only used the speedier, less optimal "ShiftedRows" tile conversion anyway, and lost interest in improving it further. Development followed the usual path of getting too obsessed with a specific problem, before finally realising I had gone beyond what I really needed for my own development. :)

Generally, the sprite coverage problem is likely to be NP-hard (though I never excelled enough in Computer Science to prove that mathematically). So it is an interesting problem to study in its own right, with loads of ways of defining your optimum depending on how you're prioritising minimising sprites/scanline, number of tiles or something else. It'd be fun to hear what other people have come up with... genetic algorithms do indeed sound like a good fit for this problem.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by psycopathicteen »

Anonimzwx from the SNESdev discord server said he is making a metasprite optimizer, using the A* algorithm. From what I can find, the A* algorithm is for finding the shortest route through a maze. I've been scratching my head trying to figure out how he is capable of using a path finding algorithm for to find the best fitting metasprite.

The only thing I can come up with is the possibility that he might be using a large decision tree of every possible out come, but that tree will accumulate fast.
Post Reply