Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

View topic - Optimising tile usage for irregular sprite shapes

Reply to topic
Author Message
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Optimising tile usage for irregular sprite shapes
Post Posted: Sat Jun 22, 2019 4:38 pm
I like to use quite a few frames of animation on the player avatar to make it as smooth as possible, as that's what you're looking at most of the time while playing the game. In all my games so far I have used a kind of matrix (3x3 tiles, 2x2 tiles, etc.) to draw the main player sprite. I stream in the tile graphics when needed, and the matrix entries for each frame state which of the tiles go where.

In my new project I'm going to have a rather large player character, which naturally isn't as boxy as the previous ones, so I'm facing problems. I fear that streaming in such a large number of tiles each frame might exceed the vblank time, so the obvious solution to me seems to not arrange the sprites in a fixed grid and instead use a more flexible system that uses as few tiles for each frame as possible.

However, piecing them together for each of the many frames manually seems like a huge task, so I wonder if anyone has ever tried to automatize the process.

I seem to remember a post by sverx concerning this very issue, but I can't find it right now.
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Sun Jun 23, 2019 1:10 pm
I started investigating that thing too for a project I then had to put aside, but I found some help through twitter, and somebody even provided a working algorithm. Now I hope I can find it again... will post here the details ASAP

edit: found that faster than expected.

two options:
1] https://github.com/kamyu2x/smssc
(demo: https://drive.google.com/file/d/1XygcNAran15PYVxmcSkEDXJJooCwp1M7/view )
Quote
compilation with gcc:
gcc -lgd -lpng -lz -lm -o demo demo.c smssc.o

use:
./demo <input.png >output.png

input.png need to be a palette-based png file.
I use Gimp to convert a truecolor image to a palette-based image:
Image > Mode > Indexed...

The color for transparency is rgb = (255, 0, 255).


2] https://github.com/SavagePencil/tile_optimizer/tree/master/tile_optimizer
  View user's profile Send private message Visit poster's website
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Sun Jun 23, 2019 3:40 pm
Thanks, I‘ll have a look at those. Have you tried them already?
  View user's profile Send private message
  • Joined: 29 Mar 2012
  • Posts: 879
  • Location: Spain
Reply with quote
Post Posted: Sun Jun 23, 2019 4:47 pm
I developed that for a project that I started some time ago...

https://github.com/kusfo/mastersystembrawler/blob/master/tools/spriter-tiles.py
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Mon Jun 24, 2019 9:40 am
@Kagesan: no, couldn't find the time they deserved.

@kusfo: Is it minimizing sprite count by using some best fit algorithm? If so, can we see that in action? :)
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 879
  • Location: Spain
Reply with quote
Post Posted: Mon Jun 24, 2019 2:26 pm
@sverx: No, it's quite simple, it just adjust laterally the frame, and then only stores 8x8 squares that had "some content" (any non transparent pixel). You can try if you clone the repository.


We had a more complex version for Antarex, I can share the algorithm, if you want, but it's taylored to megadrive sprites (using from 8x8 to 32x32)
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Mon Jun 24, 2019 5:27 pm
kusfo wrote
@sverx: No, it's quite simple, it just adjust laterally the frame, and then only stores 8x8 squares that had "some content" (any non transparent pixel).


I see. It does that for any vertical/horizontal offset pair to find the smaller count or just 'skips' the empty pixels on top / on the left?
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Mon Jun 24, 2019 5:42 pm
This is kamyu sms_covering algorithm output (using some Cimmerian's frame, as those were wonderful examples)
https://twitter.com/kamyu2x/status/1070769569210486785
  View user's profile Send private message Visit poster's website
  • Joined: 29 Mar 2012
  • Posts: 879
  • Location: Spain
Reply with quote
Post Posted: Mon Jun 24, 2019 8:27 pm
sverx wrote
kusfo wrote
@sverx: No, it's quite simple, it just adjust laterally the frame, and then only stores 8x8 squares that had "some content" (any non transparent pixel).


I see. It does that for any vertical/horizontal offset pair to find the smaller count or just 'skips' the empty pixels on top / on the left?


I have to review it, but I think it was only horizontal, although it could be done in order to have the character in the bottom of the frame..
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Tue Jun 25, 2019 11:43 am
sverx wrote
This is kamyu sms_covering algorithm output (using some Cimmerian's frame, as those were wonderful examples)
https://twitter.com/kamyu2x/status/1070769569210486785

Holy cow! That looks like it‘s exactly the thing I‘m looking for. Can‘t wait to give it a spin. Thank you!
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Tue Jun 25, 2019 12:55 pm
see if we can come out with a simple meta-sprite format that we can reuse, I could add devkitSMS support for that format (and we should probably support sprite removal too if meta-sprite is partially out of screen...)
  View user's profile Send private message Visit poster's website
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Wed Jun 26, 2019 11:40 am
I think it would be sufficient to have a tool where you input a frame and it outputs both a new mini-tileset png with the calculated sprite tiles and an array of relative x and y coordinates interleaved with the sprite numbers. You could convert the tileset via BMP2Tile and OUTI both outputs to VRAM when needed.

One problem I see with this approach are animations where individual frames are similar. (Say, for example, an idle animation for a platformer character tapping his foot.) If the frames are converted individually, you‘ll end up with a lot of identical tiles, and while ROM space is hardly an issue in this day and age, it still feels wrong to waste it.

On the other hand, if you go for whole sprite sheets instead of individual frames, you effectively need the added functionality of BMP2Tile combined with the slicing algorithm, which seems complicated to implement.
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Wed Jun 26, 2019 1:47 pm
so probably one should create a program that takes a whole sprite sheet where there is a given HxW rectangle for each meta-sprite, create a list of optimum tiles for each one, remove duplicates if any, generate an output image for BMP2Tile and one other file with x and y offsets (positive, from top-left corner) and tile number.

funny.

any taker? ;)
  View user's profile Send private message Visit poster's website
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Mon Sep 21, 2020 12:18 pm
While the sprite tile optimizer from SavagePencils RetroGraphicsToolkit has been a huge help to me already, I just stumbled upon another solution, a little tool called Tilificator.
Here's a tutorial.

I need to experiment with it a bit to find out if it really does what it says on the box, but it looks like a very promising solution for cutting full sprite sheets into sprite tiles. The only thing it seems to be missing is a way of exporting the relative positions of the tiles within an individual frame. I'm not sure how to extract them yet.
  View user's profile Send private message
  • Joined: 23 Aug 2009
  • Posts: 213
  • Location: Seattle, WA
Reply with quote
Post Posted: Mon Sep 21, 2020 4:19 pm
Super interested to hear your results, especially vs. the constraint solver approach I built. If I get some more time, I'll poke around and see the algorithm they're using.
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Tue Sep 22, 2020 6:05 pm
I dabbled around a bit with Tilificator, and the results are actually surprisingly good. I could bring down the tile count for a full sheet from 158 (manually cut) to 154 or even 147, depending on the algorithm used. The 154 tiles solution would be the better one in my case, as it would mean more tiles overall, but less tiles per metasprite.

The program is unstable and crashes a lot, but it finds good solutions, and I did find a way of exporting the data now. If you save your "project", you get a text file that has all the needed information.

I think this might actually revolutionize my creation process for metasprites. I'm duly impressed.
  View user's profile Send private message
  • Joined: 23 Aug 2009
  • Posts: 213
  • Location: Seattle, WA
Reply with quote
Post Posted: Tue Sep 22, 2020 6:10 pm
Did you find any examples where it out-performed mine?
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Wed Sep 23, 2020 6:34 am
SavagePencil wrote
Did you find any examples where it out-performed mine?

I don't think so. In fact, regarding tile count per frame, Tilificator actually seems to perform slightly worse than yours. Its charm mostly lies in the treatment of whole sprite sheets. It's fairly fast, too. It took just slightly over 2 minutes to slice up a spritesheet with 22 frames of 48x48 pixels.

It's certainly not perfect, though. Apart from the frequent crashes, the interface is clunky, there isn't any discernable difference when changing priorities, and I really wish there was a better way of exporting a list of tile numbers and coordinates other than extracting the data manually from the project file.
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Wed Sep 23, 2020 10:09 am
if sprite sheet is organized so that there's only one image for each W×H pixels, it shouldn't be too hard to create a batch process that takes the sheet and breaks it into chunks and feed each one into SavagePencil's program...
  View user's profile Send private message Visit poster's website
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Wed Sep 23, 2020 12:55 pm
Sure, but it wouldn't be aware of the other frames it's not currently processing, would it? Automatically identifying/creating tiles that are used across frames is a huge advantage of Tilificator. That, and the speed.

Try it, it's really quite capable. I would be perfectly happy with only a few minor changes, such as

- no crashes
- better data export
- an option to manually modify the tile distribution within a frame
  View user's profile Send private message
  • Joined: 23 Aug 2009
  • Posts: 213
  • Location: Seattle, WA
Reply with quote
Post Posted: Wed Sep 23, 2020 1:28 pm
Last edited by SavagePencil on Thu Sep 24, 2020 2:20 pm; edited 1 time in total
I’ve actually got an example of a multiframe solver floating around that I should revisit...
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Thu Sep 24, 2020 11:22 am
Apparently, I rejoyced a bit too early. Extracting data from Tilificator is a major pain.

While you can export the raw data of a newly created tileset, it's stored in the wrong order (= not interlaced). Oh well, that should be easily rectified with a simple custom program. Extracting the relative x/y-positions of the tiles within a frame doesn't seem quite as trivial, though. I think some manual copying and pasting might still be required after all.

Worse yet, the tool automatically crops each frame to the visible pixels alone. This has two disadvantages: 1. The x/y-positions of the tiles are all off, and don't reference the same origin across frames. 2. If a frame contains more than one object completely surrounded by transparent pixels, the tool treats them as seperate metasprites.

It's really really good when it comes to slicing the frames into tile data, though. By tweaking a few parameters, I was able to bring down the tile count of one spritesheet from 158 to 145. That's quite impressive.
  View user's profile Send private message
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Mon May 10, 2021 9:26 am
Following up from my last post, I've since settled on Tilificator as my go-to solution for slicing meta sprites. It's just too powerful to bypass.

However, I've written a couple of very small tools to make it more convenient to use it for SMS development. While they can't adress all of the issues, they still do help a fair bit.

In the current state, they're very much tailored to my current project, but it should be easy enough to adjust them to your needs. Hopefully, they are of some use to someone.

I've put them up on my GitHub. If you'd like to improve on them, be my guest.
  View user's profile Send private message
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Mon May 10, 2021 2:46 pm
has Tilificator development been abandoned?
  View user's profile Send private message Visit poster's website
  • Joined: 01 Feb 2014
  • Posts: 844
Reply with quote
Post Posted: Mon May 10, 2021 3:30 pm
sverx wrote
has Tilificator development been abandoned?


I think so. The last update has been years ago.

I did, in fact, try to contact the original author to ask him the same thing, but somehow the nesdev forum never managed to send me its registration email, so I haven't actually managed to get in touch.
  View user's profile Send private message
  • Joined: 05 Dec 2019
  • Posts: 56
  • Location: USA
Reply with quote
Post Posted: Mon May 10, 2021 7:17 pm
Some email providers don't work so well with nesdev.com's email server.
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 3756
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Tue May 11, 2021 11:28 am
Kagesan wrote
I think so. The last update has been years ago.


seems to be under GPL licence, so you can likely fork your version as long as you fully release it (and keep it GPL)
  View user's profile Send private message Visit poster's website
  • Joined: 06 Apr 2011
  • Posts: 250
  • Location: Netherlands
Reply with quote
Post Posted: Tue May 11, 2021 12:30 pm
Very cool stuff!

I will definitely need something like that in the future! I've bookmarked both SavagePencil's repository and Tilificator.
  View user's profile Send private message
Reply to topic



Back to the top of this page

Back to SMS Power!