## Algorithm for splitting sprites

Moderator: BigEvilCorporation

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

### Re: Algorithm for splitting sprites

r57shell wrote:
Thu Aug 17, 2017 1:19 pm
Yours for me is not well defined. Also, I don't wanna dig into details.
The whole algorithm is literally just this (other stuff can be slapped on top if you want, but this is the core portion):
Sik wrote:
Tue Aug 15, 2017 1:50 am
• 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)
I didn't go into code-like pseudo-code because the exact approach depends a lot on how you're handling data internally (e.g. how bitmap data is stored in RAM, how you're storing the mappings, what kind of container are you using in your given language, etc.). But the steps are pretty much that. By "scan through" I meant looping through all of them, if that part was confusing.
r57shell wrote:
Thu Aug 17, 2017 1:19 pm
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.
Ready for use yet you didn't write how it's meant to be used =P (for one I can already spot this needs to be wrapped up in a function at the very least, and if there's a bug while trying to make it buildable, it's going to be awfully hard to figure out what's wrong) This is why you're meant to explain things.
Sik is pronounced as "seek", not as "sick".

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

### Re: Algorithm for splitting sprites

Sik wrote:
Thu Aug 17, 2017 9:00 pm
I didn't go into code-like pseudo-code because the exact approach depends a lot on how you're handling data internally (e.g. how bitmap data is stored in RAM, how you're storing the mappings, what kind of container are you using in your given language, etc.). But the steps are pretty much that. By "scan through" I meant looping through all of them, if that part was confusing.
It is enough to make pseudocode which returns array of sprites with position & size.
And let user to write his own postprocessing.
It isn't hard to write code that save sprites how you store them.
Sik wrote:
Thu Aug 17, 2017 9:00 pm
Ready for use yet you didn't write how it's meant to be used =P (for one I can already spot this needs to be wrapped up in a function at the very least, and if there's a bug while trying to make it buildable, it's going to be awfully hard to figure out what's wrong) This is why you're meant to explain things.
Well, if you can't solve things, why you making game?

All "simple" algorithms has two main flaws:
1) They assume some alignment.
2) Their result will not have empty tiles. (this can generate a lot of sprites)

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

### Re: Algorithm for splitting sprites

r57shell wrote:
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".
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.
1. Shift x/y the image to find the arrangement with less empty tiles
2. Label empty tiles
3. for every tile
- Try to "enlarge" a sprite as big as possible

If I understand it correctly, is the same idea Sik has but plus the shifting. The problem is it doesn't minimize sprite count. But in real life is better to have something up and running, than the perfect idea in you head.

That's the problem with such algorithms, (0 is empty tile, 1 is non-empty):
11111
01111
01111
01111
The optimal solution is one sprite of 4x4 and one of 1x1,
BAAAA
0AAAA
0AAAA
0AAAA
instead if we "enlarge" sprites, 3 sprites will be generated, for example 4x1, 1x4, 3x3:
AAAAB
0CCCB
0CCCB
0CCCB

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

### Re: Algorithm for splitting sprites

Don't drop shadow on my algo.
It indeed bruteforce shift, and count empty tiles.
But it's end of similarity.

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

### Re: Algorithm for splitting sprites

Miquel wrote:
Sun Aug 20, 2017 3:26 pm
That's the problem with such algorithms, (0 is empty tile, 1 is non-empty):
11111
01111
01111
01111
The optimal solution is one sprite of 4x4 and one of 1x1,
BAAAA
0AAAA
0AAAA
0AAAA
instead if we "enlarge" sprites, 3 sprites will be generated, for example 4x1, 1x4, 3x3:
AAAAB
0CCCB
0CCCB
0CCCB
Not if you scan right-to-left, or if you scan vertically (though that's not desirable since it'll usually generate 8px-wide spans, which you absolutely don't want). I suppose there's nothing preventing you from trying all four combinations and picking the best one, though (especially since the step of figuring out empty tiles can be shared between them).

The alternative would be to find the largest sprite that fits, cover those, then moving on to smaller sprites, but the problem with that technique is that for irregular shapes (especially large ones) it's bound to create fragmentation at awful places which will backfire hard.
r57shell wrote:
Sun Aug 20, 2017 11:49 pm
Don't drop shadow on my algo.
It indeed bruteforce shift, and count empty tiles.
But it's end of similarity.
Then explain it instead of leaving people trying to figure out what it's doing.
Sik is pronounced as "seek", not as "sick".

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

### Re: Algorithm for splitting sprites

Sik wrote:
Mon Aug 21, 2017 12:58 am
Then explain it instead of leaving people trying to figure out what it's doing.
Nope. At least I'm not lying.

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

### Re: Algorithm for splitting sprites

r57shell wrote:
Sun Aug 20, 2017 11:49 pm
Don't drop shadow on my algo.
It indeed bruteforce shift, and count empty tiles.
But it's end of similarity.
Correct, for every tile you try to generate all possible sprites, searching first on the positive quadrant, both width and height positive, and then on the negative quadrant, both width and height negative. Seems to me that you have forgotten two quadrants. And I don't understand how you store information (all I see is printf's), or how you decide which is the best configuration. Perhaps is another of those steeps you mentioned.

@Sik I put before you an easy example to comprehend, don't infer from that is the only case.

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

### Re: Algorithm for splitting sprites

Miquel wrote:
Mon Aug 21, 2017 12:00 pm
And I don't understand how you store information (all I see is printf's),
It generates instructions to be passed to another tool later on (which I think is this one, honestly I had never heard of it before r57shell brought it up in an earlier post).

EDIT: argh, caught by a ninja edit =P (...I think)
Miquel wrote:
Mon Aug 21, 2017 12:00 pm
@Sik I put before you an easy example to comprehend, don't infer from that is the only case.
Yeah, just wanted to take advantage of it to bring up the idea of scanning several times as a cheap way to reduce sprite count for cases like this =P (on top of other methods to bruteforce it like shifting the bitmap to come up with the best alignment - interesting how much can be stacked on top to try to improve results if you can afford the extra time spent)
Sik is pronounced as "seek", not as "sick".

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

### Re: Algorithm for splitting sprites

I have idea of algorithm that requires 800 MB of RAM usage, and solves this task at pixel precision for image size 128x128,
but it would not return "obvious" for us solution in following corner case:

Edit: Oh sh... It takes not 800MB but much more.
Ok, it requires 128 MB for 64x64 image. Bad.
And 800 MB for 100x100 image.

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

### Re: Algorithm for splitting sprites

Now you are lying, oh! wait: you are making it obvious to show us than you don't like I decoded you algorithm and found a "mistake" when it's precisely what you asked for.
You are the winner!, you have the only one running solution.
Sik wrote:
Mon Aug 21, 2017 12:55 pm
Yeah, just wanted to take advantage of it to bring up the idea of scanning several times as a cheap way to reduce sprite count for cases like this =P (on top of other methods to bruteforce it like shifting the bitmap to come up with the best alignment - interesting how much can be stacked on top to try to improve results if you can afford the extra time spent)
I'm convinced there are cases where no matter which direction are you scanning, if you try to "enlarge" sprites you can't be in the optimum case. Give me time to found an example.

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

### Re: Algorithm for splitting sprites

There is the example:
001000
111110
011110
011110
011111
000100

Optimal, 5 groups/sprites:
00B000
CAAAA0
0AAAA0
0AAAA0
000E00

Scanning from top-left to bottom-right, 7 groups/sprites:
00A000
BBACC0
0DACC0
0DACC0
0DECCF
000G00

Scanning from bottom-left to top-right, 7 groups/sprites:
00G000
EBBFC0
0BBAC0
0BBAC0
0BBACD
000A00

Scanning from top-right to bottom-left, 7 groups/sprites:
00A000
DCABB0
0CABB0
0CABB0
0CFBBE
000G00

Scanning from bottom-right to top-left, 7 groups/sprites:
00G000
FCCED0
0CCABB
000A00

Yet this case is more complex I fear that when there are more tiles the probability of encounter similar cases increases exponentially.

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

### Re: Algorithm for splitting sprites

Try this one, then abandon all hope (I know why I'm saying this...)

Sik is pronounced as "seek", not as "sick".

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

### Re: Algorithm for splitting sprites

Tried to do it manually i did that :
https://www.dropbox.com/s/2ui4xrcnj2dpk ... 1.jpg?dl=0

The red part are the ones i optimized afterward, sometime the choice of adding 1 sprite to spare 1 VRAM tile is questionable... I guess it depend of your priority. The part with many holes is not interesting to optimize, you need to waste too much sprite for that.

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

### Re: Algorithm for splitting sprites

Nitpick: for the top right one, instead of 3×3 and 1×2 you could have done 3×1 and 4×2 (same amount of sprites, but reduced risk of sprite overflow). I'd normally try to avoid 1 tile wide sprites where feasible.
Sik is pronounced as "seek", not as "sick".

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

### Re: Algorithm for splitting sprites

indeed, a bit better to split like that... I tried to quickly design algo for auto sprite splitting, definitely not trivial :-/

### Who is online

Users browsing this forum: SeregaZ and 1 guest