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: 456
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: 2507
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: 456
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: 507
  • 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: 2507
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: 507
  • 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: 2507
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: 2507
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: 507
  • 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: 456
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: 2507
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: 456
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: 2507
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
Reply to topic



Back to the top of this page

Back to SMS Power!