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.

**Moderator:** BigEvilCorporation

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.

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.

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.

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

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

Code: Select all

```
_____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

Last edited by Miquel on Fri Aug 25, 2017 11:24 pm, edited 1 time in total.

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

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

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!

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.

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

Except it minimizes neither of those measures... if you are willing to sacrifice a few extra tiles in VRAM. For example:
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.

Code: Select all

```
_____JJJ____
__AAAAFFFF__
__AAAAFFFF__
__AAAAFFFF__
iIIbBBBEEEE_
IIIBBBBEEEE_
IIiBBBBDDD__
HhHHGGGDDD__
HhHHGGGDDD__
HHHHGGGCCCC_
_____KKCCCC_
_____kKCCCC_
```

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.

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

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.

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:**

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 :-/

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:**

Funnily enough, I found myself needing this just yesterday.

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

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

A blog of my Megadrive programming adventures: http://www.bigevilcorporation.co.uk

@flamewing:
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.

Code: Select all

```
Number of groups: 8, using 22 empty tiles:
__AAAABBBB__
__AAAABBBB__
__AAAABBBB__
__AAAABBBB__
CCCCDDDDGGG_
CCCCDDDDGGG_
CCCCDDDDGGG_
CCCCDDDDGGG_
HHHEEEEFFFF_
HHHEEEEFFFF_
HHHEEEEFFFF_
___EEEEFFFF_
```

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.

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

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

None =/ Maybe try this one for now:BigEvilCorporation wrote: ↑Thu Aug 31, 2017 10:22 amI'm lazy and don't want to read the whole thread - which algo won?

viewtopic.php?f=7&t=2687#p32134

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

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:
Adding 2 tiles which have 4 contacts:

Best solution found (out of 15 alternatives), number of groups: 14, using 2 empty tiles:
That's for now... thinking of better ways...

What's the price?

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_
```

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_
```

What's the price?

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
Applying the formula: 2 empty tiles for every sprite reduced max.

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_
```

Users browsing this forum: No registered users and 3 guests