Forums

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.

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

Thanks, I‘ll have a look at those. Have you tried them already?

I developed that for a project that I started some time ago...

https://github.com/kusfo/mastersystembrawler/blob/master/tools/spriter-tiles.py

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

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

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?

This is kamyu sms_covering algorithm output (using some Cimmerian's frame, as those were wonderful examples)
https://twitter.com/kamyu2x/status/1070769569210486785

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..

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!

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

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.

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? ;)

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.

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.

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.

Did you find any examples where it out-performed mine?

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.

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...

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

I’ve actually got an example of a multiframe solver floating around that I should revisit...

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.

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.

has Tilificator development been abandoned?

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.

Some email providers don't work so well with nesdev.com's email server.

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)

Very cool stuff!

I will definitely need something like that in the future! I've bookmarked both SavagePencil's repository and Tilificator.

Author	Message
Kagesan Joined: 01 Feb 2014 Posts: 895	Optimising tile usage for irregular sprite shapes Posted: Sat Jun 22, 2019 4:38 pm
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Sun Jun 23, 2019 3:40 pm
Kagesan Joined: 01 Feb 2014 Posts: 895	Thanks, I‘ll have a look at those. Have you tried them already?

kusfo Joined: 29 Mar 2012 Posts: 900 Location: Spain	Posted: Sun Jun 23, 2019 4:47 pm
kusfo Joined: 29 Mar 2012 Posts: 900 Location: Spain	I developed that for a project that I started some time ago... https://github.com/kusfo/mastersystembrawler/blob/master/tools/spriter-tiles.py

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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? :)

kusfo Joined: 29 Mar 2012 Posts: 900 Location: Spain	Posted: Mon Jun 24, 2019 2:26 pm
kusfo Joined: 29 Mar 2012 Posts: 900 Location: Spain	@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)

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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?

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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

kusfo Joined: 29 Mar 2012 Posts: 900 Location: Spain	Posted: Mon Jun 24, 2019 8:27 pm
kusfo Joined: 29 Mar 2012 Posts: 900 Location: Spain	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..

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Tue Jun 25, 2019 11:43 am
Kagesan Joined: 01 Feb 2014 Posts: 895	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!

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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...)

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Wed Jun 26, 2019 11:40 am
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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? ;)

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Mon Sep 21, 2020 12:18 pm
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

SavagePencil Joined: 23 Aug 2009 Posts: 223 Location: Seattle, WA	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.

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Tue Sep 22, 2020 6:05 pm
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

SavagePencil Joined: 23 Aug 2009 Posts: 223 Location: Seattle, WA	Posted: Tue Sep 22, 2020 6:10 pm
	Did you find any examples where it out-performed mine?

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Wed Sep 23, 2020 6:34 am
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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...

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Wed Sep 23, 2020 12:55 pm
Kagesan Joined: 01 Feb 2014 Posts: 895	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

SavagePencil Joined: 23 Aug 2009 Posts: 223 Location: Seattle, WA	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...

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Thu Sep 24, 2020 11:22 am
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Mon May 10, 2021 9:26 am
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	Posted: Mon May 10, 2021 2:46 pm
	has Tilificator development been abandoned?

Kagesan Joined: 01 Feb 2014 Posts: 895	Posted: Mon May 10, 2021 3:30 pm
Kagesan Joined: 01 Feb 2014 Posts: 895	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.

PinoBatch Joined: 05 Dec 2019 Posts: 66 Location: USA	Posted: Mon May 10, 2021 7:17 pm
PinoBatch Joined: 05 Dec 2019 Posts: 66 Location: USA	Some email providers don't work so well with nesdev.com's email server.

sverx Joined: 05 Sep 2013 Posts: 3941 Location: Stockholm, Sweden	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)

Zipper Joined: 06 Apr 2011 Posts: 250 Location: Netherlands	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.

Forums

View topic - Optimising tile usage for irregular sprite shapes