## Algorithm for splitting sprites

Moderator: BigEvilCorporation

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

### Re: Algorithm for splitting sprites

Sik wrote:
Wed Aug 23, 2017 6:27 pm
Try this one, then abandon all hope (I know why I'm saying this...)
You should have some benchmark and test cases first, and then decide, is algorithm bad, or not.
I don't have good one tool for this purpose atm.

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

### Re: Algorithm for splitting sprites

After looking more into it I found that the solution I proposed about searching bigger areas first has issues too, that simple example doesn't give you the optimal:
10101
11111
10101

After that I don't know if there is an algorithm that always gives you the optimum solution(s) other that trying every possibility.

And that's only fitting empty tiles in a single image. If you try to automate an animation things get MUCH more complex. For start you don't want repeated tiles in the whole animation.
Last edited by Miquel on Wed Aug 30, 2017 4:46 pm, edited 1 time in total.

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

### Re: Algorithm for splitting sprites

@Sik: you tell me how good/bad is:

Code: Select all

``````_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_
``````
Number of groups/sprites: 17
Group A 4x4: left=4 top=1 right=8 bottom=5
Group B 4x4: left=3 top=5 right=7 bottom=9
Group C 4x3: left=6 top=9 right=10 bottom=12
Group D 3x4: left=7 top=5 right=10 bottom=9
Group E 2x3: left=2 top=1 right=4 bottom=4
Group F 2x3: left=8 top=2 right=10 bottom=5
Group G 4x1: left=0 top=9 right=4 bottom=10
Group H 1x4: left=0 top=5 right=1 bottom=9
Group I 2x2: left=1 top=4 right=3 bottom=6
Group J 3x1: left=5 top=0 right=8 bottom=1
Group K 1x3: left=10 top=9 right=11 bottom=12
Group L 2x1: left=4 top=9 right=6 bottom=10
Group M 1x2: left=10 top=4 right=11 bottom=6
Group N 1x2: left=2 top=7 right=3 bottom=9
Group O 1x1: left=8 top=1 right=9 bottom=2
Group P 1x1: left=1 top=6 right=2 bottom=7
Group Q 1x1: left=5 top=10 right=6 bottom=11
Last edited by Miquel on Fri Aug 25, 2017 11:24 pm, edited 1 time in total.

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

### Re: Algorithm for splitting sprites

I had done it manually with a completely different arrangement but it seems in both cases we reached to 17 sprites (left = mine, right = yours):

Decided to put the algorithm I proposed to test (both left-to-right and right-to-left) and um, yeah I think this is going to need a different approach to merging spans vertically (probably will have to break down during merging instead of already imposing the 32px limit during the horizontal scan):

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

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

### Re: Algorithm for splitting sprites

I have gone as far as possible with the algorithm I provided and I have found that the solution I give you on last post is one of 47 alternatives solutions that minimize group count AND groups per line. Enjoy!

Code: Select all

``````New best solution found that minimizes group count:
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(1):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(2):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(3):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(4):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(5):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(6):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(7):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(8):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(9):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(10):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(11):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(12):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(13):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(14):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(15):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(16):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(17):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(18):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(19):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBDDDM_
IP_BBBBDDD__
I_NBBBBDDD__
I_NBBBBDDD__
GGGGLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(20):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(21):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
IIIILLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(22):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCK_
_____QCCCCK_
______CCCCK_

Alternative solution found(23):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBDDDM_
GP_BBBBDDD__
G_NBBBBDDD__
G_NBBBBDDD__
HHHHLLCCCCJ_
_____QCCCCJ_
______CCCCJ_

Alternative solution found(24):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(25):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(26):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(27):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(28):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(29):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(30):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(31):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(32):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(33):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(34):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(35):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(36):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(37):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(38):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(39):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
IGGBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(40):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(41):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
GHHBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(42):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(43):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_HH_AAAAFFM_
IHHBBBBCCCM_
IP_BBBBCCC__
I_NBBBBCCC__
I_NBBBBCCC__
GGGGLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(44):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(45):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_GG_AAAAFFM_
HGGBBBBCCCM_
HP_BBBBCCC__
H_NBBBBCCC__
H_NBBBBCCC__
IIIILLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Alternative solution found(46):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDK_
_____QDDDDK_
______DDDDK_

Alternative solution found(47):
Number of groups: 17, Groups per line density: 4.333333
_____KKK____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
GIIBBBBCCCM_
GP_BBBBCCC__
G_NBBBBCCC__
G_NBBBBCCC__
HHHHLLDDDDJ_
_____QDDDDJ_
______DDDDJ_

Best solution found (out of 47 alternatives):
Number of groups: 17, Groups per line density: 4.333333
_____JJJ____
__EEAAAAO___
__EEAAAAFF__
__EEAAAAFF__
_II_AAAAFFM_
HIIBBBBDDDM_
HP_BBBBDDD__
H_NBBBBDDD__
H_NBBBBDDD__
GGGGLLCCCCK_
_____QCCCCK_
______CCCCK_

Group A 4x4: left=4 top=1 right=8 bottom=5
Group B 4x4: left=3 top=5 right=7 bottom=9
Group C 4x3: left=6 top=9 right=10 bottom=12
Group D 3x4: left=7 top=5 right=10 bottom=9
Group E 2x3: left=2 top=1 right=4 bottom=4
Group F 2x3: left=8 top=2 right=10 bottom=5
Group G 4x1: left=0 top=9 right=4 bottom=10
Group H 1x4: left=0 top=5 right=1 bottom=9
Group I 2x2: left=1 top=4 right=3 bottom=6
Group J 3x1: left=5 top=0 right=8 bottom=1
Group K 1x3: left=10 top=9 right=11 bottom=12
Group L 2x1: left=4 top=9 right=6 bottom=10
Group M 1x2: left=10 top=4 right=11 bottom=6
Group N 1x2: left=2 top=7 right=3 bottom=9
Group O 1x1: left=8 top=1 right=9 bottom=2
Group P 1x1: left=1 top=6 right=2 bottom=7
Group Q 1x1: left=5 top=10 right=6 bottom=11
``````
edit: I now realize that could be repeated configurations. Anyway, the point is there are several alternatives but all them are equal for our proposes.

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

### Re: Algorithm for splitting sprites

Except it minimizes neither of those measures... if you are willing to sacrifice a few extra tiles in VRAM. For example:

Code: Select all

``````_____JJJ____
__AAAAFFFF__
__AAAAFFFF__
__AAAAFFFF__
iIIbBBBEEEE_
IIIBBBBEEEE_
IIiBBBBDDD__
HhHHGGGDDD__
HhHHGGGDDD__
HHHHGGGCCCC_
_____KKCCCC_
_____kKCCCC_``````
This sacrifices 6 tiles (marked as lowercase) to use 11 groups and a group density 31/12 < 3 per line.

With some cleverness, some of the wasted tiles can even be merged (by flipping some pieces and having the empty tile be shared as the last tile of one piece and the first time of the next); using this, 2 pairs of tiles can be merged in this case, resulting in 4 wasted tiles (merge k and one i, b and the other i, left with two h).

It all depends on what trade-offs you are willing to make.

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

### Re: Algorithm for splitting sprites

@flamewing, one of the preconditions was that empty tiles can't be used at all. That's a different problem: for some people wasting 6 empty tiles is not acceptable, for others is desirable, how you coupe with this decision? I mean, were is the limit? how to calculate it for a general case? are you sure, once you introduce this new rule, that you method will produce the optimal? May be there are other six tiles that reduce more group usage.

Also, I don't calculate density this way. My algorithm penalizes exponentially lines that are over the average, this way I try to give more importance solutions were density is more constant thought the all lines.
But in that concrete case results are very special, there are a lot of solutions were figures are identical (for our objectives).
Last edited by Miquel on Wed Aug 30, 2017 4:46 pm, edited 1 time in total.

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

### Re: Algorithm for splitting sprites

Anyone up to making testing of algorithm tool? If none, then I'm off.

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

### Re: Algorithm for splitting sprites

That's what i obtained using my (unfinished) algorithm on it :

I think the result isn't that bad on this example but in general it does not work that great :-/
Last edited by Stef on Thu Aug 31, 2017 11:46 am, edited 1 time in total.

BigEvilCorporation
Very interested
Posts: 202
Joined: Sat Sep 08, 2012 10:41 am
Contact:

### Re: Algorithm for splitting sprites

Funnily enough, I found myself needing this just yesterday.

I'm lazy and don't want to read the whole thread - which algo won?

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

### Re: Algorithm for splitting sprites

@flamewing:

Code: Select all

``````Number of groups: 8, using 22 empty tiles:
__AAAABBBB__
__AAAABBBB__
__AAAABBBB__
__AAAABBBB__
CCCCDDDDGGG_
CCCCDDDDGGG_
CCCCDDDDGGG_
CCCCDDDDGGG_
HHHEEEEFFFF_
HHHEEEEFFFF_
HHHEEEEFFFF_
___EEEEFFFF_
``````
The question is not which is best, but how you decide it.

And allow me to insist to you all if you want to create an animation, avoiding to produce repetitive tiles is much more important.
Last edited by Miquel on Thu Aug 31, 2017 4:19 pm, edited 2 times in total.

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

### Re: Algorithm for splitting sprites

BigEvilCorporation wrote:
Thu Aug 31, 2017 10:22 am
I'm lazy and don't want to read the whole thread - which algo won?
We need arrangement of competition first.

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

### Re: Algorithm for splitting sprites

Miquel wrote:
Wed Aug 30, 2017 3:45 pm
@flamewing, one of the preconditions was that empty tiles can't be used at all. That's a different problem: for some people wasting 6 empty tiles is not acceptable, for others is desirable, how you coupe with this decision? I mean, were is the limit? how to calculate it for a general case? are you sure, once you introduce this new rule, that you method will produce the optimal? May be there are other six tiles that reduce more group usage.
And to be more specific: if you allow empty tiles, how do you make it for starters even decide which empty tiles to look for? Assuming empty tiles can't be used makes things much easier as you don't have to go around trying whether each tile is worth including or not.
BigEvilCorporation wrote:
Thu Aug 31, 2017 10:22 am
I'm lazy and don't want to read the whole thread - which algo won?
None =/ Maybe try this one for now:
viewtopic.php?f=7&t=2687#p32134
Sik is pronounced as "seek", not as "sick".

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

### Re: Algorithm for splitting sprites

Gosh!, my implementation had a mistake. My two best shots are:

Best solution found (out of 47 alternatives), number of groups: 16, using 0 empty tiles:

Code: Select all

``````_____III____
__EEEAAAA___
__EEEAAAAJ__
__EEEAAAAJ__
_HH_NAAAAJM_
GHHFFFBBBBM_
GO_FFFBBBB__
G_CCCCBBBB__
G_CCCCBBBB__
LLCCCCKDDDD_
_____PKDDDD_
______KDDDD_
``````
Adding 2 tiles which have 4 contacts:
Best solution found (out of 15 alternatives), number of groups: 14, using 2 empty tiles:

Code: Select all

``````_____HHH____
__EEEAAAA___
__EEEAAAAJ__
__EEEAAAAJ__
_KEEEAAAAJM_
GKCCCCBBBBM_
GKCCCCBBBB__
G_CCCCBBBB__
G_CCCCBBBB__
IIIFFFFDDDD_
_____LLDDDD_
______NDDDD_
``````
That's for now... thinking of better ways...

What's the price?

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

### Re: Algorithm for splitting sprites

I tried to add empty tiles that are connected with 2 non-empty tiles, more o less as @flamewing suggested. It's recursive, exploring all possibilities. It took 5-10 minutes on an i5 to complete (Welcome to the dark side!). And only uses a 12x12 matrix!! imagine something bigger.

Can Anyone think of a method for that, instead of trying everything?

And still we need a formula which decides when is worth to expend empty tiles to minimize sprite utilization. Something like, you can use an extra empty tile is sprite usage is reduced by 10% (just an example).

A movie after...

Groups: 11, empty tiles used: 5, line groups density: 2.666667

Code: Select all

``````_____III____
__BBBBAAAA__
__BBBBAAAA__
__BBBBAAAA__
FFBBBBAAAAK_
FFDDDDCCCCK_
FFDDDDCCCC__
J_DDDDCCCC__
J_DDDDCCCC__
JHHHHGGEEEE_
_____GGEEEE_
_____GGEEEE_
``````
Applying the formula: 2 empty tiles for every sprite reduced max.

### Who is online

Users browsing this forum: No registered users and 3 guests