You are talking way over my head. If you are capable of computer sciencing the heck out of this I will probably just end up using what you come up with! I'm not a Computer Science major, I don't think I even know many CS or advanced mathematical concepts.
Minimum sprites per scanline alone is (probably) simplish to solve. Start at the top left, grab that 8x8 section. Keep doing it. As simple as it is, it's not easy to beat in many respects. I did the corner thing because I thought it'd come out similar to how I did it manually. But it didn't really, in the end. I bet that simple algorithm would beat my current algorithm total tiles wise AND sprites per metasprite wise. My manual work had a really nice balance. I doubt I can beat it algorithmically. But I can get closer than I am currently.
There might also be some heuristic we could apply before the optimization stage to significantly reduce the number of variables (or candidate locations).
I think I only ever have 8 candidate locations max at this point. It's corners * 2 because top left and left top value slightly different things.
Think about the case of a tile with a single pixel.
Right. Any sprite ever can be drawn with exactly 3 unique sprite tiles and I'm not concerned about this. My personal priorities values fewer sprites per metasprite above tile re-use. So in the example, it'd grab either the left OR the right, then in the next iteration it would find the other side as a candidate see if it could draw the
small thing with something
larger. (Which it could.) I'm not too interested in trying to draw larger things with small things, so the single pixel ends up a non factor for my approach.
Basically for any candidate location I can check if any tile already in the set with greater or equal coverage in both dimensions can be placed over the opaque pixels in the candidate tile such that the other pixels in the metasprite would also not change color. It's not so much that I don't have an idea how to do it, it's that I haven't done it because it's not-so-fun a programming task for me. Perhaps constraint programming makes it easy, but I'm pretty unfamiliar.
Also, the example was just an example. The situation can come up when the two won't be found as candidates together at the same time. They can be in different frames, or in the same frame after a few iterations, or in different frames in different iterations.
If what you're suggesting is a one step thing (do all candidates for a frame at once, or all frames at once) you end up with weird cases like... a black 24x24 metasprite with a white outline. There's lots of solid black tiles in the middle, that can all be eaten out of the middle with the same 8x8 tile, but then the outline makes way more sprites in that frame than are needed. The reason my algorithm is corner focused is because it's actively attempting to eat away the boundaries of a metasprite to avoid cases where a match in the middle looks good, but really just makes more sprites.
And that
is how I did all the sprites in Indivisible, but with... more awareness about certain things that I am not sure how to teach a program.