Unoptimal palette packing

[ISSOtm]

Here is a case where RGBGFX's palette packing is insufficient:

8pals.zip

% rgbgfx -c gbc:tileset.pal map.png
% rgbgfx map.png
FATAL: Generated 9 palettes, over the maximum of 8
Conversion aborted after 1 error

I wonder if any interesting patterns can be gleaned from this.

---

Additionally, if someone else has any such examples, please submit them!

[Rangi42]

The simple "greedy best-fit" algorithm from SuperFamiconv (also ported to Tilemap Studio) works for the 8pals.zip example.

[Rangi42]

Running with -vvvvv gives 17 proto-palettes:

Image colors: [ #000000ff, #e77300ff, #efd600ff, #634218ff, #316331ff, #5ad639ff, #00ef63ff, #39217bff, #ef9c8cff, #adadc6ff, #008cceff, #5ab5efff, ]
Image contains 17 proto-palettes
[ $0000, $035d, $1f4b, $3c87, ]
[ $0000, $01dc, $0d0c, $3c87, ]
[ $035d, $467d, $62b5, $76cb, ]
[ $035d, $467d, $76cb, ]
[ $035d, $467d, $6620, $76cb, ]
[ $6620, $76cb, ]
[ $035d, $1986, $33a0, $76cb, ]
[ $0000, $1f4b, $6620, ]
[ $0000, $01dc, $0d0c, $6620, ]
[ $0000, $1f4b, $3c87, ]
[ $0000, $035d, $1f4b, $6620, ]
[ $035d, $1f4b, ]
[ $0000, $01dc, $0d0c, ]
[ $0000, $0d0c, $6620, ]
[ $467d, $6620, $76cb, ]
[ $0000, $1986, $1f4b, $3c87, ]
[ $0000, $6620, ]

One can see that there are exactly 8 of them with 4 colors; and further inspection shows that all the smaller proto-palettes are subsets of those 8. An early step of "merge subset proto-palettes into larger ones" would have sufficed, and in fact this is what superfamiconv does.

The 9 palettes that rgbgfx ends up with are weird. 8 of them make sense, taken from the above list, but then there's an extra one:

{ 01dc, 0d0c, 3c87, 0000, }
{ 1f4b, 6620, 3c87, 0000, }  <-- why?
{ 035d, 467d, 76cb, 6620, }
{ 035d, 1f4b, 3c87, 0000, }
{ 035d, 62b5, 467d, 76cb, }
{ 01dc, 6620, 0d0c, 0000, }
{ 035d, 33a0, 76cb, 1986, }
{ 1f4b, 1986, 3c87, 0000, }
{ 035d, 1f4b, 6620, 0000, }

[ISSOtm]

Fixed by 0f1137c, it turns out.

[Rangi42]

Section 2.3 of the paper lists "Simplifying Assumptions". The first one is "Rule 1. No tile is included in another one." RGBGFX currently violates this assumption, as seen above. We need a preprocessing step like superfamiconv has, merging proper subsets together, to meet this rule.

We should also make sure all the other assumptions are being met.

[pinobatch]

For comparison, the converter in Border Crossing has such a preprocessing step that forms protopalettes, sorts them by length, and drops all that are subsets of a larger one. See borderconv.py lines 117 through 131.

[ISSOtm]

Looking more closely at the paper, it states:

The purpose of this subsection is to bring us closer to the core of the problem, by ruling out as many such degenerated cases as possible.
For each one, we prove that there is nothing lost for an offline algorithm to ignore the corresponding instances.

I read this as “our analysis will not care about these cases, because the algorithm will be adapted anyway”; this allows them to make assumptions simplifying their mathematical analysis without restricting the input space, AIUI.

Both subsets and max-size proto-pals are trivially taken care of, I believe, by reverse-sorting the proto-pals by size before packing: subsets will be found after their supersets and will have a “relative size” of zero, and thus be fitted there; likewise, “max-size” proto-pals will be found first and allocated into their own palettes (where only subsets thereof can enter).

All of the other simplifying assumptions appear not to affect us, except for Rule 4, “No [colour] is shared by all [proto-palettes]”. I'm less sure about it, but I think that we're still in the clear, because the proof essentially states that said common colour is a “freebie” for all palettes, not that this would worsen the algorithm's output (perhaps merely its performance? And even then, I'm not convinced that this wouldn't be offset by the additional code complexity.)

[ISSOtm]

Turns out that 0f1137c fixes at least this particular instance.