Has anybody ever made an algorithm for metasprite optimizing

Discussion of development of software for any "obsolete" computer or video game system.
psycopathicteen
Posts: 2935
Joined: Wed May 19, 2010 6:12 pm

Has anybody ever made an algorithm for metasprite optimizing

Post by psycopathicteen » Fri Sep 14, 2018 7:57 am

An algorithm for taking a large character, and finding what arrangement of sprites fit it within the least amount of sprites.

tepples
Posts: 21985
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 » Fri Sep 14, 2018 8:55 am

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: 827
Joined: Tue Feb 07, 2017 2:03 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Oziphantom » Fri Sep 14, 2018 9:20 am

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: 21985
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 » Fri Sep 14, 2018 9:37 am

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: 1292
Joined: Wed Apr 02, 2008 2:09 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Kasumi » Fri Sep 14, 2018 10:07 am

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: 1131
Joined: Tue Oct 06, 2015 10:16 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by calima » Fri Sep 14, 2018 10:31 am

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: 2935
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by psycopathicteen » Fri Sep 14, 2018 12:10 pm

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: 1131
Joined: Tue Oct 06, 2015 10:16 am

Re: Has anybody ever made an algorithm for metasprite optimi

Post by calima » Sat Sep 15, 2018 2:59 am

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: 3141
Joined: Mon Jan 03, 2005 10:36 am
Location: Tampere, Finland
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by thefox » Sat Sep 15, 2018 3:08 am

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: 3503
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 » Sun Sep 16, 2018 8:19 pm

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: 2935
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by psycopathicteen » Mon Sep 17, 2018 9:26 am

Was that how they were done in the original arcade machine?

User avatar
Drew Sebastino
Formerly Espozo
Posts: 3503
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 » Sun Sep 23, 2018 4:58 pm

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: 21985
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 » Sun Sep 23, 2018 6:40 pm

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: 516
Joined: Wed Mar 09, 2005 9:08 am
Contact:

Re: Has anybody ever made an algorithm for metasprite optimi

Post by Bananmos » Thu Sep 27, 2018 1:48 pm

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: 2935
Joined: Wed May 19, 2010 6:12 pm

Re: Has anybody ever made an algorithm for metasprite optimi

Post by psycopathicteen » Fri Aug 09, 2019 5:11 pm

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