Has anybody ever made an algorithm for metasprite optimizing
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
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.
-
- Posts: 1565
- Joined: Tue Feb 07, 2017 2:03 am
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.
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.
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.
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.
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
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:
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:
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.
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:
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:
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.
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
https://github.com/clbr/genmeta
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Has anybody ever made an algorithm for metasprite optimi
Nice, can this tool be used for SNES sprites too?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
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.
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.
Re: Has anybody ever made an algorithm for metasprite optimi
Hey, that's cool! I've thought about doing one like this too!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
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
- 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
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:
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. )
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. )
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
Re: Has anybody ever made an algorithm for metasprite optimi
Was that how they were done in the original arcade machine?
- 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
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.
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.
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.
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.
-
- Posts: 3140
- Joined: Wed May 19, 2010 6:12 pm
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.
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.