Algorithm for splitting sprites

Talk about development tools here

Moderator: BigEvilCorporation

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

Re: Algorithm for splitting sprites

Post by r57shell » Thu Aug 24, 2017 7:52 pm

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

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

Re: Algorithm for splitting sprites

Post by Miquel » Fri Aug 25, 2017 7:11 pm

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.
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

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

Re: Algorithm for splitting sprites

Post by Miquel » Fri Aug 25, 2017 7:39 pm

@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.
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

User avatar
Sik
Very interested
Posts: 684
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Algorithm for splitting sprites

Post by Sik » Fri Aug 25, 2017 10:25 pm

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

Image

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

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

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

Re: Algorithm for splitting sprites

Post by Miquel » Wed Aug 30, 2017 4:38 am

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! :P

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.
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

User avatar
flamewing
Interested
Posts: 41
Joined: Tue Sep 23, 2014 2:39 pm
Location: France

Re: Algorithm for splitting sprites

Post by flamewing » Wed Aug 30, 2017 8:25 am

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: 291
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » 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.

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.
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

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

Re: Algorithm for splitting sprites

Post by r57shell » Wed Aug 30, 2017 4:21 pm

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

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

Re: Algorithm for splitting sprites

Post by Stef » Thu Aug 31, 2017 8:24 am

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

Image

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.

User avatar
BigEvilCorporation
Very interested
Posts: 200
Joined: Sat Sep 08, 2012 10:41 am
Contact:

Re: Algorithm for splitting sprites

Post by BigEvilCorporation » Thu Aug 31, 2017 10:22 am

Funnily enough, I found myself needing this just yesterday.

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

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

Re: Algorithm for splitting sprites

Post by Miquel » Thu Aug 31, 2017 3:45 pm

@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.
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

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

Re: Algorithm for splitting sprites

Post by r57shell » Thu Aug 31, 2017 3:46 pm

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

User avatar
Sik
Very interested
Posts: 684
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: Algorithm for splitting sprites

Post by Sik » Thu Aug 31, 2017 4:16 pm

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: 291
Joined: Sat Jul 30, 2016 12:33 am

Re: Algorithm for splitting sprites

Post by Miquel » Thu Aug 31, 2017 6:07 pm

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?
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

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

Re: Algorithm for splitting sprites

Post by Miquel » Thu Aug 31, 2017 11:32 pm

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.
To my knowledge it was 14 "spiders" of different sizes.
By the way, at high speeds stars truly become lines like in the movies, do there are a couple of differences. Can you guess which are?

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest