nesdev.com
http://forums.nesdev.com/

Has anybody ever made an algorithm for metasprite optimizing
http://forums.nesdev.com/viewtopic.php?f=23&t=17801
Page 1 of 2

Author:  psycopathicteen [ Fri Sep 14, 2018 7:57 am ]
Post subject:  Has anybody ever made an algorithm for metasprite optimizing

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

Author:  tepples [ Fri Sep 14, 2018 8:55 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  Oziphantom [ Fri Sep 14, 2018 9:20 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  tepples [ Fri Sep 14, 2018 9:37 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  Kasumi [ Fri Sep 14, 2018 10:07 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  calima [ Fri Sep 14, 2018 10:31 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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

Author:  psycopathicteen [ Fri Sep 14, 2018 12:10 pm ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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?

Author:  calima [ Sat Sep 15, 2018 2:59 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  thefox [ Sat Sep 15, 2018 3:08 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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

Author:  Drew Sebastino [ Sun Sep 16, 2018 8:19 pm ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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:)

Author:  psycopathicteen [ Mon Sep 17, 2018 9:26 am ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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

Author:  Drew Sebastino [ Sun Sep 23, 2018 4:58 pm ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  tepples [ Sun Sep 23, 2018 6:40 pm ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  Bananmos [ Thu Sep 27, 2018 1:48 pm ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Author:  psycopathicteen [ Fri Aug 09, 2019 5:11 pm ]
Post subject:  Re: Has anybody ever made an algorithm for metasprite optimi

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.

Page 1 of 2 All times are UTC - 7 hours
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/