Algorithm for splitting sprites

Talk about development tools here

Moderator: BigEvilCorporation

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Algorithm for splitting sprites

Post by Sik » Tue Aug 15, 2017 1:50 am

Large sprites need to be split into smaller ones (since the hardware can't do over 32×32 pixels), but processing them manually can be tedious, especially for very large sprites (I just come from manually splitting a sprite into 17 smaller ones, ugh). The problem is coming up with a decent algorithm. After thinking for a while I've come up with the following idea, it's far from perfect but should give reasonable enough results (at least when it comes to avoiding wasting space in large transparent areas).

No implementation yet (I don't have time right now), I may add something like this to mdtiler later. Still, leaving this here in case somebody wants to give it a try in their own tools. Also point out if I overlooked anything! (・<・)

Downsides of the algorithm:
  • It assumes all sprites are aligned to a tile boundary (no pixel-level optimization, sorry)
  • The resulting arrangement isn't pretty (it's rarely worse than hand-optimizing though)
  • It doesn't take advantages of sprites that could be reused
Upsides of the algorithm:
  • Should still get rid of a lot of waste in empty spaces
Anyway, rough idea of how this would work:
  • Scan through the whole image looking for empty tiles (and mark them as such). From hereon we'll work at the tile level.
  • Scan through each row and make as many horizontal sprites spans as possible (i.e. from 1×1 to 4×1). If a span would be too large you'd need to break it down.
  • Scan through vertically looking for consecutive spans that have same width and line up and merge them. Again, make sure they can't be too large (i.e. larger than 4 tiles high)
Don't try to overthink that last step: just scan from top to bottom looking for consecutive spans. If there are multiple spans that could be merged, then they'll get merged in multiple steps as it keeps scanning down (i.e. 1+1→2, 2+1→3, 3+1→4).

As mentioned earlier it can't take advantage of repeated sprites. You could make it check for repeated spans and reuse them, but not only it'll be quite slower but also because span shapes are automatically generated it may decide to generate them in a way that prevents potential reuse. I suppose you could work around that by accounting for common patterns (e.g. if the bitmap is symmetric, you can make it process only half the bitmap). Also depends how badly you need to reuse tiles (vs how much of a big deal is sprite overflow).


The other big issue is in which format we'll spit out the sprite mappings. For assembly we could use the format I normally use these days, which is basically four words for each sprite entry, then one more word as a sentinel (to mark the end):

Code: Select all

SprMerlina_Idle1:
    ; x, y, tile, size
    dc.w    -$14, -$20, 0, %1000
    dc.w    -$1C, -$18, 3, %1110
    dc.w    -$14, $00, 15, %1001
    dc.w    $04, -$20, 21, %0101
    dc.w    $04, -$10, 25, %0000
    dc.w    $04, -$08, 26, %0110
    ; sentinel
    dc.w    $8000
If you want something to spit out to mdtiler, huh you can issue tiles commands:

Code: Select all

layout sprite
tiles 1 0 3 1
tiles 0 1 4 3
tiles 1 4 3 2
tiles 4 0 2 2
tiles 4 2 1 1
tiles 4 3 2 3
I have no idea what SGDK uses, or if it even has something like this. Time to consider =P (assuming you don't just make it an array with a bunch of words which is basically the same thing as my assembly format)
Last edited by Sik on Tue Aug 15, 2017 9:29 pm, edited 1 time in total.
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Tue Aug 15, 2017 10:41 am

Without knowing the working environment is hard to say, but I think there are two way to approach this:
- finding a generic solution for any sprite
- working with the knowledge that this sprite was designed for this type of hardware

In the first case you can't assume that the sprite will be aligned to a "good" tile grid, by "good" I mean that uses the less sprites possible. I makes more sense to me finding the most top, bottom, left, right pixels and from there how to fit in a tile grid, and probably finding the central point to begging looking for symmetries.
The general problem with this approach is you are going to waste a lot of precious vram space, unless you make the sprite in accordance with hardware limitations. For example most games subdivide the main character between head and body to reuse sprites.

So, if on the contrary you design this sprite on propose for this hardware, you already know how to subdivide in the most efficient way (you have spend several hours on it!), what you need then is a way to automate the process of defining the sprite, to make it easy and fast (to make new sprites AND editing previous ones).
HELP. Spanish TVs are brain washing people to be hostile to me.

gligli
Newbie
Posts: 8
Joined: Thu Jun 08, 2017 7:46 am
Location: Lyon / France
Contact:

Re: Algorithm for splitting sprites

Post by gligli » Tue Aug 15, 2017 11:28 am

I recently wrote an optimiser addition to SGDK rescomp to do something like this.

It may be less thorough than this method because it still starts by cutting sprites in 32x32 pixels blocks but then eliminates transparent blocks and truncates others to the smallest possible sprite that holds all non transparent pixels.

Still, it at least allowed for a substantial gain in ROM space with my current project while keeping SGDK compatibility!

Here's my repo with this addition: https://github.com/gligli/SGDK

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Algorithm for splitting sprites

Post by Sik » Tue Aug 15, 2017 10:31 pm

Miquel wrote:
Tue Aug 15, 2017 10:41 am
Without knowing the working environment is hard to say, but I think there are two way to approach this:
- finding a generic solution for any sprite
- working with the knowledge that this sprite was designed for this type of hardware

In the first case you can't assume that the sprite will be aligned to a "good" tile grid, by "good" I mean that uses the less sprites possible. I makes more sense to me finding the most top, bottom, left, right pixels and from there how to fit in a tile grid, and probably finding the central point to begging looking for symmetries.
The general problem with this approach is you are going to waste a lot of precious vram space, unless you make the sprite in accordance with hardware limitations. For example most games subdivide the main character between head and body to reuse sprites.

So, if on the contrary you design this sprite on propose for this hardware, you already know how to subdivide in the most efficient way (you have spend several hours on it!), what you need then is a way to automate the process of defining the sprite, to make it easy and fast (to make new sprites AND editing previous ones).
In my experience artists just want to give you a PNG for each sprite and not have to worry much about the tech stuff, just give them a rough idea of what to do and what not. Also splitting manually is a freaking pain in the ass, not only it's wasted time but if the sprite ever gets edited it may need to be split again (and if this isn't automated, you're wasting lots of time). Also honestly more often than not the amount of waste is not huge, reserve manual splitting only for when you're really tight on video memory.

I'm not aiming for 100% perfect, just good enough to avoid any obvious wasted space in large empty areas. I'm sure we can come up with more complex algorithms down the line later.
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Wed Aug 16, 2017 10:59 am

Have you considered creating a visual tool where you just select the sprite's rectangles with the mouse?
Imagine you have all your images in a single file, the you have next lists in list-boxes: animations, images and sprites; so you can edit sprite's characteristics and select it's file location.

With automation, if avoiding empty tiles is the important thing, just use brute force. Once you know width and height, try all permutations.
Then just do:

Code: Select all

For each tile:
	if is empty label it as '0'
	else label it as '1'

n=2
For MxN as: 4x4, 4x3, 3x4, 3x3, 3x2, 2x3, 4x1, 1x4, 2x2, 3x1, 1x3, 2x1, 1x2, 1x1 (*) do:
	For each tile:
		try to make a MxN matrix group, this is: all must be labelled '1'
		If group found: label all n. n=n+1. Store group/sprite somewhere.
END
Notice that we try first to make 4x4 groups for every tile before atempting littler structures, that's crucial.

(*) They are ordered from bigger to lesser area, but still there are other permutations that share same characteristics. If needed, use brute force to find the arrangement which minimizes groups by trying those other permutations.
HELP. Spanish TVs are brain washing people to be hostile to me.

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

Re: Algorithm for splitting sprites

Post by r57shell » Wed Aug 16, 2017 2:48 pm

Check this thread. viewtopic.php?f=2&t=2103
And make sure you check my algo in linked by me thread!

Actually I have new ideas about it, but describing them without implementation is useless
Image

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Wed Aug 16, 2017 5:07 pm

@r57shell do you refer to this: https://pastebin.com/1niRQx1C ?
Also code without explanation is hard. An explanation will be helpful :).
HELP. Spanish TVs are brain washing people to be hostile to me.

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Wed Aug 16, 2017 9:48 pm

Miquel wrote:
Wed Aug 16, 2017 10:59 am

Code: Select all

For each tile:
	if is empty label it as '0'
	else label it as '1'

n=2
For MxN as: 4x4, 4x3, 3x4, 3x3, 3x2, 2x3, 4x1, 1x4, 2x2, 3x1, 1x3, 2x1, 1x2, 1x1 (*) do:
	For each tile:
		try to make a MxN matrix group, this is: all must be labelled '1'
		If group found: label all n. n=n+1. Store group/sprite somewhere.
END
Example (underscores are empty, groups are letters):

Code: Select all

111111__11
111111111_
1_11111111
1_1_11111_
1111111111
1111111111
111__11111
111111_111
11_1_11111
_111111_11

DDDIII__GQ
DDDRAAAAG_
O_JJAAAAGS
O_T_AAAAG_
BBBUAAAAKK
BBBEEEECCC
BBB__HVCCC
BBBLLH_CCC
MM_W_HPCCC
_FFFFHP_NN
HELP. Spanish TVs are brain washing people to be hostile to me.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Algorithm for splitting sprites

Post by Sik » Wed Aug 16, 2017 11:42 pm

At this point maybe instead of discussing over which algorithm is better we should instead move into implementing them into the conversion tools. Will see what I can do with mdtiler.

For the record, all of the alternatives proposed here have the same exact flaw the algorithm I proposed has, i.e. they only seem to work at the tile boundary level. None of those algorithm seem to be able to work with sprites being positioned at arbitrary pixel positions (feel free to correct me if I overlooked something). Still not too worried about this, just removing empty tiles already brings in a decent amount of savings to be "good enough" in my opinion. If we want to go crazy microoptimizing, I noticed that in most games it's the backgrounds that eat up most memory (and probably the main reason why so many games have shit animation, since sprites get starved).
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 514
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Thu Aug 17, 2017 5:06 am

There is no magical algorithm that gives you tiles without searching for them, the act of arranging empty tiles into a grid is in the same order of cost of trying solutions by brute force.


Another example of the same algorithm but with more sparse tiles. Note that groups 'R', 'H' and 'r' are not optimal due to:
Miquel wrote:
Wed Aug 16, 2017 10:59 am
(*) They are ordered from bigger to lesser area, but still there are other permutations that share same characteristics. If needed, use brute force to find the arrangement which minimizes groups by trying those other permutations.
Example 2 (underscores are empty, groups are letters, case sensitive):

Code: Select all

__1_11_1_1____
___1_1_11__11_
1_11__11___1__
_11_____1_1_11
1_111111111111
1__1_111111_11
__1_111_111__1
_11_1_11_111_1
_11_1111111__1
1_111_1111_11_
1___1___111111
_11____1_111__
1___1___11_11_
____1__1111111



__b_NN_L_c____
___d_e_Lf__OO_
g_PP__hL___i__
_QQ_____j_k_EE
X_KKKBBBAAAlEE
X__m_BBBAAA_EE
__G_HRR_AAA__M
_YG_H_SS_IIn_M
_YG_HoCCCII__M
Z_GpH_CCCq_TT_
Z___r___sDDDUU
_VV____t_DDD__
u___a___WW_JJ_
____a__FFFFJJv



Number of groups/sprites: 48
Group B 3x3: left=8 top=4 right=11 bottom=7
Group C 3x2: left=5 top=4 right=8 bottom=6
Group D 3x2: left=6 top=8 right=9 bottom=10
Group E 3x2: left=9 top=10 right=12 bottom=12
Group F 2x3: left=12 top=3 right=14 bottom=6
Group G 4x1: left=7 top=13 right=11 bottom=14
Group H 1x4: left=2 top=6 right=3 bottom=10
Group I 1x4: left=4 top=6 right=5 bottom=10
Group J 2x2: left=9 top=7 right=11 bottom=9
Group K 2x2: left=11 top=12 right=13 bottom=14
Group L 3x1: left=2 top=4 right=5 bottom=5
Group M 1x3: left=7 top=0 right=8 bottom=3
Group N 1x3: left=13 top=6 right=14 bottom=9
Group O 2x1: left=4 top=0 right=6 bottom=1
Group P 2x1: left=11 top=1 right=13 bottom=2
Group Q 2x1: left=2 top=2 right=4 bottom=3
Group R 2x1: left=1 top=3 right=3 bottom=4
Group S 2x1: left=5 top=6 right=7 bottom=7
Group T 2x1: left=6 top=7 right=8 bottom=8
Group U 2x1: left=11 top=9 right=13 bottom=10
Group V 2x1: left=12 top=10 right=14 bottom=11
Group W 2x1: left=1 top=11 right=3 bottom=12
Group X 2x1: left=8 top=12 right=10 bottom=13
Group Y 1x2: left=0 top=4 right=1 bottom=6
Group Z 1x2: left=1 top=7 right=2 bottom=9
Group a 1x2: left=0 top=9 right=1 bottom=11
Group b 1x2: left=4 top=12 right=5 bottom=14
Group c 1x1: left=2 top=0 right=3 bottom=1
Group d 1x1: left=9 top=0 right=10 bottom=1
Group e 1x1: left=3 top=1 right=4 bottom=2
Group f 1x1: left=5 top=1 right=6 bottom=2
Group g 1x1: left=8 top=1 right=9 bottom=2
Group h 1x1: left=0 top=2 right=1 bottom=3
Group i 1x1: left=6 top=2 right=7 bottom=3
Group j 1x1: left=11 top=2 right=12 bottom=3
Group k 1x1: left=8 top=3 right=9 bottom=4
Group l 1x1: left=10 top=3 right=11 bottom=4
Group m 1x1: left=11 top=4 right=12 bottom=5
Group n 1x1: left=3 top=5 right=4 bottom=6
Group o 1x1: left=11 top=7 right=12 bottom=8
Group p 1x1: left=5 top=8 right=6 bottom=9
Group q 1x1: left=3 top=9 right=4 bottom=10
Group r 1x1: left=9 top=9 right=10 bottom=10
Group s 1x1: left=4 top=10 right=5 bottom=11
Group t 1x1: left=8 top=10 right=9 bottom=11
Group u 1x1: left=7 top=11 right=8 bottom=12
Group v 1x1: left=0 top=12 right=1 bottom=13
Group w 1x1: left=13 top=13 right=14 bottom=14
HELP. Spanish TVs are brain washing people to be hostile to me.

flamewing
Very interested
Posts: 56
Joined: Tue Sep 23, 2014 2:39 pm
Location: France

Re: Algorithm for splitting sprites

Post by flamewing » Thu Aug 17, 2017 7:40 am

One thing I often see people forget about when discussing optimization is the goal of said optimization. For the MD, there are several potential goals which are often at odds with one another:
  1. minimal amount of tiles
  2. minimal number of sprites
  3. minimal amount of sprites per scanline
  4. minimal amount of pixels per scanline (this is often the same as the above, but not always)
  5. strict maximum tile limit for each frame of animation (say, you have only 32 tiles in VRAM available for the main character)
  6. strict maximum tile limit for all art (say, your mappings and DMA formats limit you too $1000 tiles for all main character art)
If you also are doing DMAs for the sprite art, you will also want to minimize the amount of total art in the DMA, minimize the number of DMAs (due to the DMA setup overhead and any DMA queue processing overhead).

Any algorithm for sprite optimization needs to consider at least some of these factors; but which factors will depend on the specific needs of the game.

So ideally, an algorithm would allow priorization of these goals.

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

Re: Algorithm for splitting sprites

Post by r57shell » Thu Aug 17, 2017 9:12 am

Miquel wrote:
Wed Aug 16, 2017 5:07 pm
@r57shell do you refer to this: https://pastebin.com/1niRQx1C ?
Also code without explanation is hard. An explanation will be helpful :).
Yes. It's not supposed to have explanation.
1) Just copypaste this code.
2) Put "glpk\glpsol.exe".
3) Add into this code, reading of your sprite and which fills BMP array in code.
4) run "Algorithm" part.
5) check out res1 array as result.
Sprite class has .sx() .sy() methods that say size in tiles. And x, y position in pixels.
Image

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: Algorithm for splitting sprites

Post by Stef » Thu Aug 17, 2017 9:38 am

flamewing wrote:
Thu Aug 17, 2017 7:40 am
One thing I often see people forget about when discussing optimization is the goal of said optimization. For the MD, there are several potential goals which are often at odds with one another:
  1. minimal amount of tiles
  2. minimal number of sprites
  3. minimal amount of sprites per scanline
  4. minimal amount of pixels per scanline (this is often the same as the above, but not always)
  5. strict maximum tile limit for each frame of animation (say, you have only 32 tiles in VRAM available for the main character)
  6. strict maximum tile limit for all art (say, your mappings and DMA formats limit you too $1000 tiles for all main character art)
If you also are doing DMAs for the sprite art, you will also want to minimize the amount of total art in the DMA, minimize the number of DMAs (due to the DMA setup overhead and any DMA queue processing overhead).

Any algorithm for sprite optimization needs to consider at least some of these factors; but which factors will depend on the specific needs of the game.

So ideally, an algorithm would allow priorization of these goals.
That is.. you have several optimization strategies possibles depending what you want.
One of my idea was to use "cost" for :
- hardware sprite
- sprite per line
- pixel per line
- VRAM usage (~DMA bandwidth)
- ...

Then you can adjust the costs depending what you want to optimize more. Then you use a genetic algorithm fitting in the constraints to minimize the global cost.
The problem is that you need to do a fast algorithm so a good minimum value can be find in a small amount of time.

Sik
Very interested
Posts: 939
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Algorithm for splitting sprites

Post by Sik » Thu Aug 17, 2017 11:28 am

( ゚-゚)

You're all hung up on trying to argue about what's the most optimal thing down to the pixel without ever going anywhere. Reminds me of certain person who has spent years trying to start his game because he keeps changing his algorithm to load sprites into video memory (and he's still at it...).

My biggest concern was just coming up with an easy algorithm that does a good enough job with large sprites (where even loose optimization brings in big gains... even for medium-sized sprites, in my experience, it's uncommon for a silhouette to cover most of the rectangle). For small sprites it's honestly not worth it usually. One of my biggest hurdles with sprites (besides just taking a lot to draw) is wasting time splitting them manually. Automating this would save lots of time and make it more feasible to have larger sprites in games more often.

For the record, one of the quirks in my algorithm is that it actually tries to reduce how many sprites are in a row (at the expense of the splits not looking "pretty"). This is kind of intentional: I noticed that most of the time aiming for horizontal spans tends to result in the same amount of sprites total anyway, while still reducing the amount of sprites in a given row (especially important for 8px wide sprites, as those reduce the potential pixel coverage per line). So that's a not-so-obvious optimization it has.
r57shell wrote:
Thu Aug 17, 2017 9:12 am
Yes. It's not supposed to have explanation.
1) Just copypaste this code.
2) Put "glpk\glpsol.exe".
3) Add into this code, reading of your sprite and which fills BMP array in code.
4) run "Algorithm" part.
5) check out res1 array as result.
Sprite class has .sx() .sy() methods that say size in tiles. And x, y position in pixels.
We have several people trying to argue why my algorithm is trash and you intend people to just use yours without even a rough explanation of why it's better? (・~・)
Sik is pronounced as "seek", not as "sick".

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

Re: Algorithm for splitting sprites

Post by r57shell » Thu Aug 17, 2017 1:19 pm

Sik wrote:
Thu Aug 17, 2017 11:28 am
We have several people trying to argue why my algorithm is trash and you intend people to just use yours without even a rough explanation of why it's better? (・~・)
I don't wanna argue about your algorithm nor about mine.
Yours for me is not well defined. Also, I don't wanna dig into details.
More important: I don't wanna claim that my algorightm is better.
And, I don't intend people to use my algorithm without thinking.
I just wanna share ready for use algorithm with its results as is.
Your option to decide, use it or not.
Also I don't wanna describe it, it will take too long.

For yours algorithm, would be nice to have ready to run code, or at least pseudocode.
Image

Post Reply