# Fades in older games. Need some help figuring out how the algorithm was derived

Sorry, this question is a bit esoteric, but I just can't get it out of my head!

I'm looking at the fade algorithm used in the arcade game DoDonPachi (as well as many other older games):

I wrote a python script to pick out a few pixels and track them for the duration of the fade. Here's a representative sample of the results. The first row of each group is the starting color value, while each subsequent row is the difference between the the color value of the current frame and the color value of the previous frame.

Starting Value: (132, 66, 189)
Frame 1:    [9, 9, 8]
Frame 2:    [8, 8, 8]
Frame 3:    [8, 8, 8]
Frame 4:    [8, 8, 9]
Frame 5:    [9, 9, 8]
Frame 6:    [8, 8, 8]
Frame 7:    [8, 8, 8]
Frame 8:    [8, 8, 9]
Frame 9:    [9, 0, 8]
Frame 10:   [8, 0, 8]
Frame 11:   [8, 0, 8]
Frame 12:   [8, 0, 9]
Frame 13:   [9, 0, 8]
Frame 14:   [8, 0, 8]
Frame 15:   [8, 0, 8]
Frame 16:   [8, 0, 9]
Frame 17:   [0, 0, 8]
Frame 18:   [0, 0, 8]
Frame 19:   [0, 0, 8]
Frame 20:   [0, 0, 9]
Frame 21:   [0, 0, 8]
Frame 22:   [0, 0, 8]
Frame 23:   [0, 0, 8]
Frame 24:   [0, 0, 0]
Frame 25:   [0, 0, 0]
Frame 26:   [0, 0, 0]
Frame 27:   [0, 0, 0]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

Starting Value: (132, 0, 0)
Frame 1:    [9, 0, 0]
Frame 2:    [8, 0, 0]
Frame 3:    [8, 0, 0]
Frame 4:    [8, 0, 0]
Frame 5:    [9, 0, 0]
Frame 6:    [8, 0, 0]
Frame 7:    [8, 0, 0]
Frame 8:    [8, 0, 0]
Frame 9:    [9, 0, 0]
Frame 10:   [8, 0, 0]
Frame 11:   [8, 0, 0]
Frame 12:   [8, 0, 0]
Frame 13:   [9, 0, 0]
Frame 14:   [8, 0, 0]
Frame 15:   [8, 0, 0]
Frame 16:   [8, 0, 0]
Frame 17:   [0, 0, 0]
Frame 18:   [0, 0, 0]
Frame 19:   [0, 0, 0]
Frame 20:   [0, 0, 0]
Frame 21:   [0, 0, 0]
Frame 22:   [0, 0, 0]
Frame 23:   [0, 0, 0]
Frame 24:   [0, 0, 0]
Frame 25:   [0, 0, 0]
Frame 26:   [0, 0, 0]
Frame 27:   [0, 0, 0]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

Starting Value: (165, 156, 222)
Frame 1:    [9, 8, 8]
Frame 2:    [8, 8, 8]
Frame 3:    [8, 8, 8]
Frame 4:    [8, 9, 9]
Frame 5:    [9, 8, 8]
Frame 6:    [8, 8, 8]
Frame 7:    [8, 8, 8]
Frame 8:    [8, 9, 9]
Frame 9:    [9, 8, 8]
Frame 10:   [8, 8, 8]
Frame 11:   [8, 8, 8]
Frame 12:   [8, 9, 9]
Frame 13:   [9, 8, 8]
Frame 14:   [8, 8, 8]
Frame 15:   [8, 8, 8]
Frame 16:   [8, 9, 9]
Frame 17:   [9, 8, 8]
Frame 18:   [8, 8, 8]
Frame 19:   [8, 8, 8]
Frame 20:   [8, 0, 9]
Frame 21:   [0, 0, 8]
Frame 22:   [0, 0, 8]
Frame 23:   [0, 0, 8]
Frame 24:   [0, 0, 9]
Frame 25:   [0, 0, 8]
Frame 26:   [0, 0, 8]
Frame 27:   [0, 0, 8]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

Starting Value: (156, 90, 206)
Frame 1:    [8, 8, 8]
Frame 2:    [8, 8, 9]
Frame 3:    [8, 8, 8]
Frame 4:    [9, 9, 8]
Frame 5:    [8, 8, 8]
Frame 6:    [8, 8, 9]
Frame 7:    [8, 8, 8]
Frame 8:    [9, 9, 8]
Frame 9:    [8, 8, 8]
Frame 10:   [8, 8, 9]
Frame 11:   [8, 8, 8]
Frame 12:   [9, 0, 8]
Frame 13:   [8, 0, 8]
Frame 14:   [8, 0, 9]
Frame 15:   [8, 0, 8]
Frame 16:   [9, 0, 8]
Frame 17:   [8, 0, 8]
Frame 18:   [8, 0, 9]
Frame 19:   [8, 0, 8]
Frame 20:   [0, 0, 8]
Frame 21:   [0, 0, 8]
Frame 22:   [0, 0, 9]
Frame 23:   [0, 0, 8]
Frame 24:   [0, 0, 8]
Frame 25:   [0, 0, 8]
Frame 26:   [0, 0, 0]
Frame 27:   [0, 0, 0]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]


As you can see, either an 8 or a 9 is subtracted from each color component in each frame. Furthermore, a 9 always appears three frames after an 8, even though the starting subtracted value is different for each color component. Note also that each color component reaches 0 (that is, black) with a difference of either 8 or 9, not some arbitrary remainder. This means that the subtracted value cycle of 8,8,8,9 is never broken! (This algorithm was probably written to ensure that the last frame of the fade was as smooth as the others.)

Now, this puzzles me. According to my calculations, if you reverse the process -- that is, take the 8,8,8,9 cycle and sum it up to find all the possible combinations in 29 frames -- you only get 52 unique numbers. But as it so happens, each color component is a member of this set! This means that either the colors were picked specifically for this fade algorithm (unlikely), or that the fade algorithm was designed around the color palette of the game. But how on earth could somebody have figured out that if you take 8,8,8,9, shift the cycle appropriately, and keep subtracting the numbers from each color component in your palette, you'll eventually reach 0 for every single color?! There's gotta be some mathematical trick that I'm missing. What is it?

• Why not just play with the alpha? That's how I do for fade-in/out animations. – DogDog Aug 21 '12 at 18:48
• I'm not trying to replicate the algorithm in my own code, just trying to figure out how it was derived. – Archagon Aug 21 '12 at 18:52
• I feel like it is what you said, the colors were picked based on the sequence 8,8,8,9. Given that sequence they were able choose from 52*52*52 colors. An interesting note, if you start at 0 and add the sequence 8,8,8,9 you will get to 255. Which allows them to use black and white. – Luis Estrada Aug 21 '12 at 19:15
• @Apoc: The style of fade-out is visibly different from alpha fade. See how each colour value goes down by a fixed number (number pattern) rather than a percentage of it's initial value? This means that there are circumstances in which you may prefer to use it over more common methods. Retro style, for example. – AlbeyAmakiir Aug 21 '12 at 22:25

Actually, there's a simple logic behind the 8-8-8-9 pattern. It arises naturally if you use only 32 intensity levels (5 bits per component), but want to render that on an 8-bit-per-component display.

Consider if you have a 5-bit intensity level and want to extend it to 8 bits. The simplest thing to do would be to just shift-left and leave the low three bits zero. The trouble is, then it doesn't go all the way to pure white. The highest intensity level you can reach is 11111000, or 248. So you're not using the full intensity range of the 8-bit display.

Really, what you'd want to do is a calculation like intensity8 = round(intensity5 * 255.0 / 31.0), to rescale the [0, 31] range to [0, 255]. However, there's a neat trick to accomplish this without any floating-point math or divides: set the low three bits equal to the high three bits. That is, to convert intensity from 5-bit to 8-bit you'd do

intensity8 = (intensity5 << 3) | (intensity5 >> 2);


Then an intensity of 11111 will map to 11111111 (31 maps to 255), and intermediate results will do something sane as well, e.g. 10000 -> 10000100 (16 -> 132).

This set of numbers is exactly what you have. Taking the red component of your first example, you have:

132    10000100
123    01111011
115    01110011
107    01101011
99    01100011
90    01011010
82    01010010
74    01001010


Note how the low three bits are always equal to the top three bits. The difference of 9 occurs when both bit 0 and bit 3 flip at the same time.

I'm uncertain why 5-bit intensity levels would have been used in this situation; perhaps that was the limit of the hardware of the arcade machine? It's notable that a 5-bit RGB value is 15 bits, which fits nicely into a 16-bit word. In any case, that explains the odd 8-8-8-9 pattern.

• 16 bits per pixel was called 'High Color'. (That's about all I remember about it) en.wikipedia.org/wiki/High_color – tugs Aug 21 '12 at 19:30
• After a quick trip through wikipedia, Sega Saturn (en.wikipedia.org/wiki/Sega_Saturn#Video) mentions 15-bit color display mode, as well as GameBoy Advance (en.wikipedia.org/wiki/Game_Boy_Advance) – tugs Aug 21 '12 at 19:52
• That's brilliant! It all makes sense now. Thank you! – Archagon Aug 21 '12 at 20:29
• The game must have had 16-bit color, and the artists probably wanted to squeeze more color out of their game at the expense of transparency, giving an RGBA 5551 color scheme. – Archagon Aug 21 '12 at 20:37

You should look into mode 13h, or 256 color palette fading. Back then, you had that many colors and what you did, was messing around with the whole palette, since you couldn't calculate new colors that weren't in it.