"Color Reduction for Windows Games"
Visual Developer, Vol. 7, No. 1
Apr/May 1996, page 88

What appears here is the original manuscript, as submitted to Jeff Duntemann. Any changes in the published version are due to Jeff's expert editing.

Game programming under Windows 3.1 and Windows 95 is, to say the least, a challenge. I have noticed many hard-core DOS game programmers are greeting the Windows phenomenon with about as much enthusiasm as hard-core rock music fans greeted disco. Fortunately, disco was a passing phase. Windows, on the other hand, is going to be with us for a while. By now most game developers have accepted the inevitable, and one way or another, they are moving into Windows game development.

Windows game programming presents us with several unique problems. One of the first hurdles you will encounter when porting a DOS game to Windows is what to do with all the colors. Unlike DOS, where all the colors available on the system could be completely controlled by the programmer, Windows programmers will find there are limits on what they can do with colors.

One limitation has to do with multiple programs running at the same time. When a program becomes topmost, its colors become dominant. Windows will try to map the colors in the other programs to the colors in the dominant program. It does this through the use of logical palettes. So it is possible for the colors of a program to change frequently as other programs are run. You may have noticed the colors in your Windows wallpaper change occasionally, or perhaps you have a screen saver that temporarily changes the colors in an application program. All this is caused by logical palettes.

However, there are some colors that usually do not change. These are called the system colors, and they are used for the menus, frames, boxes and buttons that make up the Windows user interface. Windows reserves these colors for its own use, and well-behaved Windows programs do not touch them.

For some probably arbitrary reason, in the 256-color graphics modes, Windows reserves 20 color indexes for its system colors. These are not the first 20 colors, or even 20 contiguous colors, but rather 10 colors at the beginning of the palette and 10 more at the end. These are the colors you want to avoid when you write your Windows game. Especially, you don't want to create a palette scroll effect that uses any of these colors. In fact, in general, you don't want to use these colors at all.

How Many Colors for Games?

If you eliminate the first 10 colors and the last 10 colors, that leaves the game developer with 236 colors to work with. These colors have to be used for everything, including sprite artwork and backgrounds. If you have a game with several levels, you may decide you need constant sprite colors and variable background colors. Let's say you want to have 32 sprite colors that remain constant throughout the game. That means your background artwork will need to be reduced to 204 colors.

Recall from earlier articles, preprocessing artwork is a time-consuming part of any game development project. In general, you have to accept the artwork in whatever form your artist gives it to you, and then you have to write utilities to rearrange the artwork into a format you can use. Most likely, your artist will give you artwork that uses all 256 colors available to him in his paint program. It is up to you to reduce this artwork to 236 colors, 204 colors, or 32 colors, depending on what you are planning to use it for. You will also need to make the colors contiguous and fill certain blocks of the palette. For example, you may want your sprite colors to use palette entries 10-41, and your background color will use palette entries 42-245. The ideas in this article will discuss how to do that using three different algorithms: the popularity algorithm, the elimination algorithm, and the multi-criteria elimination algorithm.

About the Pictures

To demonstrate these three algorithms, I started with a 256-color picture of myself (Figure 1). I then reduced it to 204 colors using the all the algorithms. The multi-criteria elimination algorithm produced the best result (Figure 2).

At 204 colors, the differences were not particularly dramatic, so I reduced the picture to 16 colors (Figures 3-6). The features of each reduction algorithm are most obvious at the 16-color level, but in general these algorithms are not designed to reduce a picture's colors that far. The three algorithms discussed below work well for higher color reductions. At the lower color resolutions, better results will be obtained using an error dispersion dithering algorithm, such as the one used by CompuShow 2000 (Figure 7). Since I am more interested in modest reductions for Windows display, I will stick to color mapping algorithms in this article, and leave the dithering algorithms for another article.

The Popularity Algorithm

A very common color reduction algorithm is called the "popularity algorithm". The logic behind this algorithm is quite simple. You identify the n most popular colors, and eliminate all the other colors. This algorithm can be implemented easily by sorting the colors by pixel count and mapping the bottom 256-n colors to the top n colors (see Dr. Dobbs Journal, July 1995, page 121). The problem with the popularity algorithm is the possibility of completely eliminating important colors. Consider the case of an albino bunny in a field. You have lots of shades of green for the grass, shades of blue for the sky, shades of white and gray for the clouds and the bunny fur, and only three pink pixels representing the bunny's eye. The popularity algorithm would eliminate the critical pink pixels, and you would be left with a generic white bunny -- not a desirable result. I tried applying the popularity algorithm to my picture. The results for a 16-color reduction are shown in Figure 3. As you can see, this is not the best result for a 16-color reduction.

The Elimination Algorithm

A better way to approach the problem is from the opposite direction. Instead of identifying the most popular colors, identify the least popular colors, then eliminate them by mapping them to other colors. Intuitively, you would think this would produce the same results as the popularity algorithm. In fact, the selection of colors generated by the elimination algorithm can be quite different from those generated by the popularity algorithm. Consider the color table shown in Table 1.

-	palette index	0	1	2	3	4	5	6	7	...
-	pixel count	10	20	30	40	50	60	70	80	...
color components:	R	0	1	1	3	1	1	2	3	...
-	G	0	1	1	3	1	1	1	1	...
-	B	0	1	2	3	4	3	1	1	...

Table 1

Suppose you want to keep half the colors. Using the popularity algorithm, the surviving colors would be 4, 5, 6, and 7. Using the elimination algorithm, color 0 would be mapped to color color 1, and then color 1 would be mapped to color 2. At this point color 2 would will represent 60 pixels, and so it will become a surviving color. Colors 3 and 4 will be eliminated, and the final picture will contain colors 2, 5, 6 and 7. Figure 4 shows a 16-color example of the elimination algorithm. As you can see, this picture is not bad, but colors have been lost. My lips came out brown, not red, and I have one blue eye and one brown eye.

The Multi-Criteria Elimination Algorithm

While the elimination algorithm generates a better result than the popularity algorithm, it does not solve the problem of the albino bunny. Critical colors will still likely be lost. An improvement on the elimination algorithm involves eliminating colors based on two criteria. The first criterion, as in the popularity algorithm, is the number of pixels of that color. The second criterion is the distance from another color. Thus, the first colors to be eliminated are those that are both very similar to another color, and have very few pixels. Here is how it works. Suppose you have a color table with the first 8 entries as in Table 2

-	palette index	0	1	2	3	4	5	6	7	...
-	color map	0	1	2	3	4	5	6	7	...
-	pixel count	10	20	150	40	50	60	10	50	...
color components:	R	0	1	2	3	1	1	2	3	...
-	G	0	1	2	3	1	1	1	1	...
-	B	0	1	2	3	2	3	1	1	...

Table 2

At the beginning of the program, the color map array matches the palette index array. On each pass through the code, you want to eliminate one color, and modify the color map array and the pixel count.

Based on color distance alone, you have 8 choices on the first pass. You can choose to map from 1 to 4, from 1 to 6, from 4 to 6 or from 6 to 7, or the reverse (4 to 1, etc.). All these possibilities are equal in terms of color distance. We choose to map from 6 to 1 because 6 has the fewest pixels. We designate the color map value of 6 to be 1, and we add the pixel count from color 6 to the pixel count of color 1, and set the pixel count of color 6 to 0. This pass generates the color table in Table 3.

-	palette index	0	1	2	3	4	5	6	7	...
-	color map	0	1	2	3	4	5	1	7	...
-	pixel count	10	30	150	40	50	60	0	50	...
color components:	R	0	1	2	3	1	1	2	3	...
-	G	0	1	2	3	1	1	1	1	...
-	B	0	1	2	3	2	3	1	1	...

Table 3

On the next pass, we choose to map color 1, which has the fewest pixels, to color 4, which is its closest match. This generates the color table in Table 4, and a problem becomes apparent. The pixels in color 6 that were mapped to color 1 are now mapped to color 4. But the RGB values in color 6 are not really that close to those in color 4, in fact they are much closer to color 7. This is called the "leapfrog effect", when colors are remapped and then remapped again, and it causes severe color degradation, especially when the reduction is drastic, as in the 16-color reduction in Figure 5.

-	palette index	0	1	2	3	4	5	6	7	...
-	color map	0	4	2	3	4	5	1	7	...
-	pixel count	10	0	150	40	80	60	0	50	...
color components:	R	0	1	2	3	1	1	2	3	...
-	G	0	1	2	3	1	1	1	1	...
-	B	0	1	2	3	2	3	1	1	...

Table 4

The solution to the leapfrog effect is to find all the colors that are mapped to the current color, and once again search for the nearest color match among the colors that are still active. (An inactive color is denoted by a 0 pixel count.) This slows down the algorithm somewhat, but vastly improves the final results.

Figure 6 shows the 16-color output from the multi-criteria elimination algorithm. In this picture, the colors are more authentic. My lips are red and my eyes are blue. But the contrasts are stark and unnatural looking compared to the simple elimination method in figure 4.

About the Code

The program COREDUCE.C reduces a 256-color PCX picture to any lesser number of colors using either the elimination algorithm or the multi-criteria elimination algorithm. It begins by displaying the PCX file on the screen. Then it counts all the pictures of each color. Then it loops, eliminating one color on each pass, until reaching the target number of colors. Each time a color is eliminated, the color map array is updated to show the new color the palette index is mapped to.

After all the colors are mapped and the target number is reached, the pixels are reassigned to their new palette indexes, and the colors are "condensed", that is, they are made into a contiguous block within the palette set. For Windows, you would want these colors to start at palette index 10, so the first 10 colors can be reserved for Windows use.

The COREDUCE code was written in C, and for convenience Fastgraph was used for the low-level graphics manipulations. This code may be compiled and re-linked with Fastgraph or Fastgraph/Light, or the low-level functionality may be replaced with the graphics library of your choice.

The REDUCE program, as written, is not terribly fast. Grabbing each pixel from the screen one at a time is time-consuming. A trivial change that would speed up the program would be to load the PCX file in a virtual buffer rather than display it on the screen. While that method would be much faster, it would be RAM intensive and for larger PCX files would require protected mode programming.

Conclusion

The algorithms described here are most suitable when color reduction is small, that is, when the target number of colors is relatively large. For a Windows program, that means a reduction from 256 to 236 colors. In the case of a game, a further reduction, such as a reduction to 204 colors, may be desired. The multi-criteria elimination algorithm will provide the best results for this level of reduction.

If you're an experienced Windows programmer, you probably think my struggles with this new environment are humorous. If you are a reluctant DOS recruit like myself, however, take heart. Windows programming offers exciting possibilities. Learn Windows techniques now, and it will be years before your programming skills are obsolete again. Sure it's hard, the vernacular is obtuse, and parts of it are just plain strange, but that's why game programmers get paid the big bucks, right?