| | ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Unrestricted hires colour mode! (albeit just a *tiny* bit letterboxed..)
I've been spending a few weeks on and off experimenting with how sequences of hires pixels behave, and as something of a side effect I've reached a startling conclusion.
If you layer seven hires sprites over a multicolour sprite over a multicolour bitmap, with the just that final sprite set to a lower priority than the bitmap foreground colours, I'm pretty sure you can have a 24x1 pixel area of any pixel any colour.
It's easily done for a palette of 11 colours as so:
BBbbbbbbbbbbbbbbbbbbBBbb # background layer: two pixels from $d800 & $d802, rest from $d021
00112233445566778899 # MCM sprite layer. Note odd x-position -> half pixels peek out from under fg
ff ff ff ff ff ff # bitmap fg layer
s s s s s s # hires sprite layer. 's' where layer's always opaque, space where it is optional
So, any of the pixels whose x%4 is 0 or 1 can be any of the 7 hires colours or any of the three MCM sprite colours, or $d021
any pixels where x%4==2 can be any one of the 7 hires sprite colours (so ensure those 7 include the up to six represented here)
any pixels where x%4==3 are unrestricted
For 16 colours it's more complex. I have a algorithm that will deal with any sequence for which all sixteen colours are present in the first 16 pixels (ie the first 16 are just a permutation), which chooses from about 50 different layouts depending on the last 8 colours and where they can be found in the first 16.
I've yet to generalise to all 16^24 possibilities, but have also yet to find a sequence that cannot be represented. lp_solve and gprolog have both failed me, as they grind to a halt if I try to describe the general problem.
Would anyone care to prove me right or wrong about the general case being solvable (preferably with either an algorithm or a counter example)? I'm having trouble concentrating on anything else while this is still an open question.
Not sure whether this belongs in Coding or Pixeling; posting here because it's pretty impractical for artwork. Still, it's trivially stretchable to full screen height, so perhaps it would be good for a narrow area of vertical 'raster bars' :D |
|
... 25 posts hidden. Click here to view all posts....
|
| | Monte Carlos
Registered: Jun 2004
Posts: 359 |
Counting gives:
7 hires sprites = 7 colors
1 MC Srpite = 3 colors
1 MC bitmap = 3 colors
1 background = 1 color
gives total:
14 colors not 16 |
| | AmiDog
Registered: Mar 2003
Posts: 97 |
Quoting Monte CarlosCounting gives:
7 hires sprites = 7 colors
1 MC Srpite = 3 colors
1 MC bitmap = 3 colors
1 background = 1 color
gives total:
14 colors not 16
Yes, but you can have three new bitmap colors for each char (8 pixels), which is what makes this problem interesting. Thus for a 16 pixel wide area, you could use 17 colors (if there were that many available). The question is thus how wide you can make the area by carefully positioning the sprites, taking advantage of masking etc. |
| | Isildur
Registered: Sep 2006
Posts: 275 |
As a gfx man I dream of 5 colors unrestricted hires mode.
16 col isn't necessary. Give me 5 but 320x200 with decent editor or converter :) |
| | Oswald
Registered: Apr 2002
Posts: 5094 |
Quote: As a gfx man I dream of 5 colors unrestricted hires mode.
16 col isn't necessary. Give me 5 but 320x200 with decent editor or converter :)
nufli will do 5 for you... but there's even ufli.. |
| | Monte Carlos
Registered: Jun 2004
Posts: 359 |
@AmiDog:
Yes, but the thread started with
"I'm pretty sure you can have a 24x1 pixel area of any pixel any colour"
and i do not see this from the preconditions. |
| | ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Think I've got it, thanks to Copyfault's input, and some poking round graph theory papers (relevant concept is vertex covers - each pixel pair is the edge in a graph, foreground colours must be found to cover that graph).
The layout is pretty much fixed - might have to special case the instance where the first pixel requires an MCM multicolour, or alternately we can place a pair of black foreground pixels just to the left of the display area.
, , | , , , | , ,i i, | , , d021
,a a, |c c, , , |g g, , , |k k, , cell backgrounds
, , | , e,e e,e | , , , | , , MCM sprite 7, first colour
, ,b b| ,d d, ,f f| ,h h, ,j j| ,l l, cell foregrounds
, , | , , , | , , , | , , hires sprites 0-6
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ even pairs (hires or MCM sprite over bitmap BG or MCM sprite)
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ odd pairs (hires sprite over bitmap FG)
Assume all 12 cells contain 12 distinct pairs of colours (if there are fewer, then a similar proof
to this will result in a FG colour list no larger than that concluded below)
We now have 12 pixel-pairs that contain between them at most 16 colours
As we have fewer than 24 colours, at least one colour must appear in more than one pair.
Initialise the FG colour list to just that colour, and remove all pairs that contain it.
We now have at most ten pixel-pairs, that contain between them at most 15 colours
As we have fewer than 20 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.
We now have at most eight pixel-pairs, that contain between them at most 14 colours
As we have fewer than 16 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.
The FG colour list should now contain three colours
We now have at most six pixel-pairs left to cover. Take one colour from each of those
six, and add them to the FG colour list
The FG colour list now contains at most nine colours.
Now,
foreground pixels in odd pairs have free choice from seven colours (we just overlay them with a pixel from a hires sprite)
foreground pixels in even pairs have free choice from nine colours (we can either overlay with a hires sprite pixel, or set/modify an
MCM sprite 7 pixel)
Only six foreground pixels overlay odd pairs, so at most six of the foreground colours need to be allocated to hires sprites.
The remaining foreground colours can be distributed between any remaining hires sprites and the two remaining sprite multicolours.
Done!
(Not quite as "pure" as aligning the sprites with the character boundaries, but at this point I'm out. Thanks Copyfault, and Ninja for pointing him this way!) |
| | Dane
Registered: May 2002
Posts: 423 |
There is still some good stuff left to do with gfx and sprite priority. And though this particular idea doesn't seem that useful it got me thinking.
Iopop and I made a gfx format with 15 chars of 4-colour hires that didn't involve FLI. Apart from some gfx I made ages ago I don't know if it's ever been used again.
I've also had in mind to experiment a little with mcol bmp combined with mcol sprites shifted 1 pixel to create the illusion of hires using the right combinations. That has probably been done before.
And finally, some day it's time to make an XFLI picture where I make constant use of the option to move sprites in X-position, creating the illusion of a wider image area than 192 pixels. |
| | Joe
Registered: Apr 2002
Posts: 229 |
"I've also had in mind to experiment a little with mcol bmp combined with mcol sprites shifted 1 pixel to create the illusion of hires using the right combinations. That has probably been done before."
Dane: Yup, that's one way! I encourage you to try it for real, pinching Crimson in the side... |
| | Copyfault
Registered: Dec 2001
Posts: 478 |
Quoting ChristopherJam...
We now have at most ten pixel-pairs, that contain between them at most 15 colours
As we have fewer than 20 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.
We now have at most eight pixel-pairs, that contain between them at most 14 colours
As we have fewer than 16 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.
The FG colour list should now contain three colours
We now have at most six pixel-pairs left to cover. Take one colour from each of those
six, and add them to the FG colour list
The FG colour list now contains at most nine colours.
This proves that there is no pixel sequence worse than the one you gave as example (modulo transpositions of 2x1-pixel-cells) and it proves that the maximum no.of colours in l1 (or in the FG colour list if you want to stick to this phrase) is nine. Using the 4-pixel-shifting of the sprite layers this fully completes the "weak form" of the proof; by "weak" I mean it's still unclear wether this upper bound for no.of colours in l1 is sharp or not.
The difficult version of the initial proposition would be as follows: find the minimal upper bound for the number of colours in l1.
Upon deeper thinking your FG-list-argument (taking into account the rigid definition of l1) already states that this minimal upper bound of the abstract layer 1 is indeed nine. So this leads us to the following more technical question: what is the minimal upper bound for the number of hires sprites that are necessary for constructing the abstract layer 1.
Quoting ChristopherJamNow, foreground pixels in odd pairs have free choice from seven colours (we just overlay them with a pixel from a hires sprite)
foreground pixels in even pairs have free choice from nine colours (we can either overlay with a hires sprite pixel, or set/modify an
MCM sprite 7 pixel)
Only six foreground pixels overlay odd pairs, so at most six of the foreground colours need to be allocated to hires sprites.
The remaining foreground colours can be distributed between any remaining hires sprites and the two remaining sprite multicolours.
Done!
Great! Hope you can think of something else now ;)) But I'll try to keep you busy by sharing my thoughts on how to find an answer to the "technical strong version" of the initial question.
Quoting ChristopherJam(Not quite as "pure" as aligning the sprites with the character boundaries, but at this point I'm out. Thanks Copyfault, and Ninja for pointing him this way!)
Thank you for entertaining!!
Speaking of aligning the sprites with the char boundaries, I think I have an idea how to argue why 6 hires sprites are enough even if you align the abstract layer 1 with the char boundaries.
First, assign the colours to l0 and l1 by the rules I gave in my former post.
Now do the following to optimize the colour distribution between l0 and l1:
4. if there are colours in l0 that are also in l1, move the pixels from l0 to l1
5. choose (one of) the most often occuring colour in l0 as bg colour; if possible, pick one of a char that still holds four different colours
I think this "frees" l0 from some colours that forced us to have four distinct colours in every char when constructing l0 by gfx- and spr0-pixels. Unfortunately I don't have a formal proof for that yet.
As an example, let's process the following pixel sequence (which is a transposition of your "worst case" sequence):
c d 8 9 2 0 3 4 1 2 6 5 a b 7 3 4 5 6 7 0 1 e f
No double pixel exists, so we continue with sorting colours by amount of occurance:
colours 0, 1, 2, 3, 4, 5, 6, 7 occur twice, the others 8, 9, a, b, c, d, e, f only once. The colours occuring twice are processed first, by the loop given as Rule 2:
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
, , 0,3 | , 5, , 3| 5, ,0 , |l1
, ,2 , 4| ,6 , ,7 |4 , , 1, |l0
c d,8 9, , |1 2, ,a b, | ,6 7, ,e f|rem. cells
Now the loop quits because there is no colour to be found more than once among the remaing cells. So the remaining colours will be assigned arbitrarily to the layers.
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
c ,8 , 0,3 |1 , 5,a , 3| 5,6 ,0 ,e |l1
d, 9,2 , 4| 2,6 , b,7 |4 , 7, 1, f|l0
In l1 we find exactly nine colours: c, 8, 0, 3, 1, 5, a, 6, e. Now let's see how the new rule 4 affects the layer's contents: in l0 we have the colours d, 9, 2, 4, 6, b, 7, 1, f. Thus, 6 and 1 can be moved to l1:
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
c ,8 , 0,3 |1 ,6 5,a , 3| 5,6 ,0 1,e |l1
d, 9,2 , 4| 2, , b,7 |4 , 7, , f|l0
Last but not least, there are three colours occuring twice in l0: 2, 4, 7. As there are still four l0-colours in char1, we choose e.g. colour 2 as bg-colour. This gives:
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
c ,8 , 0,3 |1 ,6 5,a , 3| 5,6 ,0 1,e |l1
d, 9,2 , 4| 2, , b,7 |4 , 7, , f|l0
vr1,vr2,bgr,d8x|bgr,---,vr1,vr2|vr1,vr2,---,d8x|gfx data
Now the normal mc-gfx-mode suffices to construct l0 (for '---' it doesn't matter what gfx data is used as these pixels are fully covered by sprites)!!! For l1, the number of colours needed hasn't changed, it's still nine. Thus we can use one shifted mc-sprite together with the priority trick to create three hires pixels plus another six sprites for the remaining colours.
I think this kind of layer optimization will work in general but a full proof would be full of case distinctions.
Now that there is one sprite "left", we can go a step further and use this for the next line of gfx. With FLI and by wisely counting colours that can occur in y-direction it _could_ be possible to make some 24x200-pixel-window with unrestricted hires, but a proof or an algorithm for that is out of grasp atm. |
| | ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Excellent, that works.
The seven l0 colours would have to have at least one duplicate across any pair of characters, but my one concern would be that it might be a different duplicate shared between a different pair. Perhaps this could be worked around by swapping a colour between l1 and l0? Six hires sprites certainly fits with my experimental results with a brute force allocator, but I've yet to prove it covers all bases.
And yes, the more flexibility there is in the colouring of any given line, the more likely it is that at least most of the palette can be kept the same between one 24x1 slice and another. Image coherency would help too; adjacent lines are likely to mostly use the same colours.. |
| Previous - 1 | 2 | 3 | 4 - Next | |
