# bitmap to or-sprites

Here's one question for the bit/byte wizkids:

Imagine I have this row of pixels (could be any colours of course) :

0 0 2 4 8 8 8 8 9 7 8 8 4 2 2 0

What would be the formula/pseudocode to find out:
- how many or-layered sprites you'd need to represent these pixels with sprites (all at the same coordinate)
- what these sprite colours would have to be?

So, for example:

0 0 0 0 15 0 0 0 0 0 0 15 0 0 0 0
can be represented by one sprite (color 15)

0 0 0 0 4 4 4 4 1 1 1 1 5 5 5 5
can be represented by two sprites (color 1, color 4)

0 0 0 0 13 13 13 13 14 14 14 14 15 15 15 15
can be represented by two sprites (color 13, color 14)

0 1 2 3 4 5 6 7 7 6 5 4 3 2 1 0
can be represented by three sprites (color 1, color 2, color 4)

and:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
can be represented by four sprites (color 1, color 2, color 4, color 8)

If your sprite is limited to 16x16 pixels, the problem is relatively simple assuming 3 color sprite:
If you want to support a larger width than 16px or more color the situation. Get more Complex.
Can you elaborate a bit. more?

Just assume 16x16 for now. Also: assume the minimum amount of sprites that should be used.

Probably not the most efficient alternative, but considering the (small) size of the problem, a brute-force attack seems suitable:

1. Remove the repeated values: 0,15 (first example), 0,1,4,5 (second ex.). The amount of distinct colors is Cn and the colos are C[0]..[Cn-1]
2. If Cn = 1, then use one sprite of C[0] color, then end.
3. With a number of sprites (Sn) of 2:
4. For every colour of sprite 0 (Sc[0]) from 1 to 15...
5. For every colour of sprite 1 (Sc[1]) from Sc[0] + 1 to 15...
6. If any Cn can be represented with Sc[0] and Sc[1], then you have found one solution. Print it and continue (there may be more than one)
7. After checking all the combinations:
8. If you have found a solution, end.
9. If you have not found any solution, increase Sn and go back to 4 (obviously, there will be an additional step 5 for Sc[2], and step 6 should consider Sc[0], Sc[1] and Sc[2] and so on)

Not exactly the same problem, but I succesfully used this approach in PNG2SPR+ to parse multicolored sprites bigger than 16x16.

With only 3 color sprites that is the more realistic situation, giving the sprite/scanline limit, it is easy:
1) Create a 128 x 3 items table where you have c1, c2, c3 = c1 or c2
2)l for each row find three color codes of the sprite line, named c1, c2, c3 and scan the table (if you have only one or two colors/rows you do not need to to this)
3)if you can find a item in the table where your first. Color is c1 your second is c2 and the third is c3, you can set the corrisponding bits on the sprite layer 1 or 2. The combination would give c3.
4)the table is only 128 entries instead of 256 because the combinations of c1, c2 give the same c3 of the combination of c2, c1, so you need to check even swapping c1 and c2.
Of course there are also some meaningless conbinactions like c1=10 c2=10 and c3=10 but you do not need to bother of these
I think should work