It is currently Tue Nov 20, 2018 4:14 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 14 posts ] 
Author Message
PostPosted: Fri Sep 14, 2018 7:57 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2771
An algorithm for taking a large character, and finding what arrangement of sprites fit it within the least amount of sprites.


Top
 Profile  
 
PostPosted: Fri Sep 14, 2018 8:55 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20787
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Fri Sep 14, 2018 9:20 am 
Offline

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


Top
 Profile  
 
PostPosted: Fri Sep 14, 2018 9:37 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20787
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Fri Sep 14, 2018 10:07 am 
Offline
User avatar

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

_________________
https://kasumi.itch.io/indivisible


Last edited by Kasumi on Fri Sep 14, 2018 10:34 am, edited 2 times in total.

Top
 Profile  
 
PostPosted: Fri Sep 14, 2018 10:31 am 
Offline

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


Top
 Profile  
 
PostPosted: Fri Sep 14, 2018 12:10 pm 
Offline

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


Top
 Profile  
 
PostPosted: Sat Sep 15, 2018 2:59 am 
Offline

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


Top
 Profile  
 
PostPosted: Sat Sep 15, 2018 3:08 am 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Sun Sep 16, 2018 8:19 pm 
Offline
Formerly Espozo
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3381
Location: Richmond, Virginia
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:)


Top
 Profile  
 
PostPosted: Mon Sep 17, 2018 9:26 am 
Offline

Joined: Wed May 19, 2010 6:12 pm
Posts: 2771
Was that how they were done in the original arcade machine?


Top
 Profile  
 
PostPosted: Sun Sep 23, 2018 4:58 pm 
Offline
Formerly Espozo
User avatar

Joined: Mon Sep 15, 2014 4:35 pm
Posts: 3381
Location: Richmond, Virginia
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.


Top
 Profile  
 
PostPosted: Sun Sep 23, 2018 6:40 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20787
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Thu Sep 27, 2018 1:48 pm 
Offline

Joined: Wed Mar 09, 2005 9:08 am
Posts: 419
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group