Action Arcade Adventure Set
Diana Gruber

Chapter 8
Color Considerations

Creative use of color will bring your game to life, but be beware! Matching colors can be more trouble than matching socks.

Just a few years ago, programmers had to write games to run on Hercules, CGA, and EGA systems. That meant our games had to support 2, 4, and 16 colors. We organized our code and artwork accordingly. Then one day, the marketing gurus decided the time had come to support 256 colors. The hardware changed, along with the buying habits of game players, and VGA became a viable option. It was wonderful. It was like Dorothy stepping out of her dull gray farm house into the land of Oz. Everything looked so much better in 256 colors!

Managing 256 colors is a bit more difficult than managing 16 colors, mainly because there is much more data to deal with. But the results are worth the extra work. In this chapter, we'll look at some of the tricks that make managing colors easier.

The Magic of Color Palettes

The game editor and the actual game that we'll be creating both make heavy use of color palettes. If you know how to use color palettes effectively, you can perform a number of amazing animation and visual effects, such as fade-ins, fade-outs, and palette scrolling. Fortunately, palettes are easy to work with in the VGA's 256-color mode. Let's take a look at how palettes are used without going into too much technical detail.

In the 256-color mode, the VGA provides you with 256 separate color registers, each of which can be assigned three color values to create a unique color. As shown in Figure 8.1, each color in a palette is made up of a red, green, and blue (RGB) component. In this respect, you get to choose which color is assigned to each of the 256 color registers by "mixing" the three base colors together.

Figure 8.1 How the 256-color palette is arranged.

Once color values have been assigned to the color palettes, you can use them in your programs. Fortunately, Fastgraph provides us with some powerful functions, such as fg_setdacs(), fg_palette(), fg_palettes(), fg_setrgb(), fg_getdacs() and fg_getrgb(), for working with palettes. Let's take a look at how color values are assigned to a palette and then used.

Assigning Colors to a Palette

Colors are assigned to a palette by modifying the video DAC register values, or DACs, that the VGA provides. As you might guess from our previous discussion, each DAC has a red, green, and blue component. The color components range from 0 to 63, with higher values representing more intense colors. The RGB values determine which color is displayed. Table 8.1 shows some examples of colors that can be set in the palette.

Table 8.1 Some Example Palette Colors Used in Tommy's Adventures

Color
Color registerRedGreenBlue
0000black
160063blue
226300red
25564447flesh tone
255636363white

When the video mode is initialized, Fastgraph sets the color registers to the default palette set as defined in the VGA video modes. We usually want to change the color registers to our own choice of colors. If you change the value of a color register, every pixel on the screen assigned to that color register will change color simultaneously. In general you don't want the user to see this happen, unless it's part of a special effect, such as a fade-in, fade-out, or a palette scroll.

Creating Color Effects

A palette fade-in is accomplished by setting all the DAC values to 0, then gradually incrementing them in sequence until they reach their target values. In this way, a screen will start out black, then gradually be colorized. A variation of this is a fade-out, in which you start with a color screen and have it gradually turn black as the DAC values are decremented to 0. These visual effects can be used nicely in games in transition areas such as when a title screen is displayed or when the player quits the game.

Palette Fading

< Note: Download fade.zip from the downloads page. Diana. >

The code to create palette fade effect is shown here. This code was donated by Eric Lund:

/******************************************************************\ 
*                                                                  * 
*  Fade.C -- palette fade program                                  * 
*                                                                  * 
*  Written by Eric W. Lund (CIS:74041,1147) with thanks to Ted     * 
*  Gruber and Randy Dryburgh. Copyright (C) 1994 by Eric "Please   * 
*  use and share this code" Lund.                                  * 
*                                                                  * 
\******************************************************************/ 
 
#include <fastgraf.h> 
#ifdef __TURBOC__ 
  #include <mem.h> 
#else 
  #include <memory.h> 
#endif 
 
#define FADE_COLORS   256 /* Number of screen colors    */ 
#define FADE_CHANNELS 768 /* Colors x 3 (for R, G, & B) */ 
 
/* global variables */ 
char fade_pal[FADE_CHANNELS]; 
char fade_keyhalt=0; 
int fade_steps=32; 
int fade_delay=0; 
void fade (int dir, int start, int count); 
void fade_blackout (void); 
 
/* macros */ 
#define fade_init()           fg_getdacs (0, FADE_COLORS, fade_pal); 
#define fade_in_all()         fade(1,0,FADE_COLORS) 
#define fade_out_all()        fade(0,0,FADE_COLORS) 
#define fade_in(start,count)  fade(1,start,count); 
#define fade_out(start,count) fade(0,start,count); 
/******************************************************************/ 
void main (void) 
{ 
   int x; 
   char pal[768]; 
 
   fg_setmode(20);           /* Set mode to 320x200 Mode X */ 
   fg_setvpage(1);           /* Look at a blank screen */ 
 
   /* adjust the palettes */ 
   for (x=0; x<256; x++) 
   { 
       pal[x*3]  =x/16;      /* Set reds */ 
       pal[x*3+1]=x%64;      /* Set greens */ 
       pal[x*3+2]=(255-x)/4; /* Set blues */ 
   } 
   pal[0]=0; pal[1]=0; pal[2]=0; /* Color 0 is background, keep it black */ 
   fg_setdacs (0,256,pal); 
 
   /* Draw colorful shapes on hidden page */ 
   for (x=0; x<256; x++) 
   { 
       fg_setcolor(x); 
       fg_move(319-x,199); 
       fg_draw (x,0); 
   } 
 
   /* Illustrate fading routines: */ 
   fade_keyhalt=1;     /* Allow a keyhit to abort fading */ 
   fade_init();        /* Make copy of screen palette to RAM */ 
   fade_blackout();    /* Blackout screen palette */ 
   fg_setvpage(0);     /* Look at page with graphic (now blacked out) */ 
 
   fade_steps=128;     /* Very smooth, slow fade */ 
   fade_in_all();      /* Fade in screen palette to match RAM copy */ 
   fade_out_all();     /* Fade out screen palette to blackout */ 
 
   fade_steps=64;      /* Slow fade */ 
   fade_in_all();      /* Fade in screen palette to match RAM copy */ 
   fade_out_all();     /* Fade out screen palette to blackout */ 
 
   fade_steps=32;      /* Restore normal fading speed */ 
   fade_in(64,64);     /* Fade in selected portion of palette */ 
   fade_in(128,64);    /* Fade in selected portion of palette */ 
   fade_in(0,64);      /* Fade in selected portion of palette */ 
   fade_in(192,64);    /* Fade in selected portion of palette */ 
 
   fade_steps=16;      /* Very fast fade */ 
   fade_out(128,64);   /* Fade out selected portion of palette */ 
   fade_out(64,64);    /* Fade out selected portion of palette */ 
   fade_out(192,64);   /* Fade out selected portion of palette */ 
   fade_out(0,64);     /* Fade out selected portion of palette */ 
 
   fg_setmode(3);       /* Back to our regular DOS video mode! */ 
   fg_reset();         /* Reset any ANSI attributes */ 
} 
/******************************************************************/ 
void fade (int dir,int start,int count) 
{ 
   register int k,n; 
   int i,j;                           /* loop variables */ 
   char fade_pal_new [FADE_CHANNELS]; /* modified (faded) palette */ 
   unsigned char key1,key2;           /* used for for keycheck */ 
 
   /* loop through all gradations of the fade */ 
   for (i=dir?1:fade_steps-1; dir?i<=fade_steps:i>=0; dir?i++:i--) 
   { 
      if (fade_keyhalt) /* default is do not halt on keyhit */ 
      { 
         fg_intkey (&key1, &key2); 
         if (key1+key2>0) 
         { 
             fade_keyhalt++; /* let user detect aborted fade */ 
             break;          /* halt fade on keyhit */ 
         } 
      } 
      /* create new (faded) palette */ 
      for (k=0, n=start*3, j=0; j<count; j++) 
      { 
         fade_pal_new[k++] = (char)(((int)fade_pal[n++] * i)/fade_steps); 
         fade_pal_new[k++] = (char)(((int)fade_pal[n++] * i)/fade_steps); 
         fade_pal_new[k++] = (char)(((int)fade_pal[n++] * i)/fade_steps); 
      } 
      fg_setdacs(start,count,fade_pal_new); /* install new palette */ 
      if (fade_delay)
         fg_waitfor (fade_delay);           /* pause if needed */ 
   } 
} 
/******************************************************************/ 
void fade_blackout(void) 
{ 
   /* empty palette for quick clearing */ 
   char empty_palette[FADE_CHANNELS];   /* set all palette entries to 0 */ 
   memset (empty_palette,0,FADE_CHANNELS); 
 
   /* set dacs to zero */ 
   fg_setdacs(0,FADE_COLORS,empty_palette);
} 

You will find this program in the file FADE.C in your \FG\UTIL\ subdirectory. I suggest you run the program to see how it works. First it draws an attractive rectangular pattern, then it gradually fades the colors in and out several times. This is accomplished by repeated calls to fg_setdacs(). The result is an attractive, smooth fade.

Palette Scrolling

The palette scrolling technique is often used with streams and waterfalls. Palette colors representing the water are assigned several shades of blue, which constantly change to give the impression of moving water. When using the palette scrolling technique, you need to be careful to reserve those palettes for use in the water only. If you use the same blue pixels somewhere else on the screen, they'll change color, too. For example, you don't want the pupils of Tommy's eyes changing shades of blue as he jumps over a waterfall.

The Quickfire launch chute uses the palette scrolling effect to create the illusion of motion. This effect was suggested by Les Pardew of Cygnus Multimedia, who also drew the launch chute and the rest of the beautiful Quickfire artwork.

Choosing Colors

Palettes can present us with some problems. We have 256 palette entries, and each one can be assigned to our choice of 262,144 colors (64x64x64 = 262,144). We could simplify our code by using the same colors throughout an entire game, but I don't recommend that approach. Games are best when they have rich and beautiful artwork, and that means the extravagant use of color. Since most side scrollers will have many levels, we can change colors between levels for dramatic effect. For example, a desert background will require earth tones, a jungle background will require tropical colors, and a space ship background will need dramatic, metallic colors.

There are some colors, such as sprite colors, that we will not want to change. We'll see the same sprites on many levels, and we want them to look the same each time. This especially applies to our main sprite Tommy. While it may be acceptable for him to have a green shirt on level one and a blue shirt on level two, for example, we most certainly do not want him to have a purple face on level three. So we need to have certain color registers that are constant throughout the game.

In my case, I found it convenient to have 33 fixed colors and 223 variable colors. As shown in Table 8.2, I assigned colors 1 through 31 to the sprite color values; color registers 32 through 254 are changeable; and color 0 is a transparent sprite color, which can be used in background tiles, and is usually set to black. Color 255 is usually set to white for reasons we will see in a minute.

Table 8.2 Use of Color Registers in Tommy's Adventures

Color RegisterUsage
0Transparent sprite color (usually black)
1-31Sprite colors
32-254Background colors
255Background color (usually white)

Once you have designed your color strategy, you can give instructions to your artist to change some colors and keep other colors consistent. Your artist will probably have trouble understanding this. If your artist modifies the wrong palette set, don't panic. Just write code to fix the artwork so you can use it.

Remapping Colors

If your artist gives you artwork with the colors set up improperly, you will need to change them. Since this is such a common problem, I have written a program to handle palette reduction, merging, and matching, which we will explore in a minute. I've also included a function in the Fastgraph game editor that will reassign the sprite colors and find the closest match to the menu colors. We're going to look at that function first because it's a little simpler. You will find the fix_palettes() function, shown next, in the COMMON.C source code file:

void fix_palettes(int status) 
{ 
   static char sprite_palette[] = {
       0, 0, 0, 18, 7, 0, 27,13, 3, 36,21,10, 45,31,19, 54,42,32, 
      63,55,47,  0, 0, 0, 14,14,14, 21,21,21, 28,28,28, 35,35,35, 
      42,42,42, 49,49,49, 56,56,56, 63,63,63,  0, 0,42,  8, 8,52, 
      21,21,63, 21,37,61, 21,53,60, 36, 0, 0, 45, 0, 0, 54, 0, 0, 
      63, 0, 0, 56,44,47,  0,35, 0,  0,57, 0, 21,63, 0, 63,63, 0, 
      63, 0,63, 63, 0,63}; 
 
   register int i; 
   int color; 
   int white_value, black_value; 
   int blue_value, gray_value; 
   int distance; 
   static char game_palette[768]; 
 
   /* set the palettes for the first 32 colors (sprite colors) */ 
   if (status == 1) 
      fg_setdacs(0,32,sprite_palette); 
 
   /* get the current palette values */ 
   fg_getdacs(0,256,game_palette); 
 
   /* find the closest colors to white, black, blue and gray for menus */ 
   white_value = 0; 
   black_value = 189; 
   white = 15; 
   black = 0; 
   blue_value = 63*63*3; 
   gray_value = 63*63*3; 
 
   for (i = 0; i < 255*3; i+=3) 
   { 
      color = game_palette[i]+game_palette[i+1]+game_palette[i+2]; 
 
      /* biggest total color value is closest to white */ 
      if (color > white_value) 
      { 
         white = i/3; 
         white_value = color; 
      } 
 
      /* black color is closest to 0 */ 
      if (color < black_value) 
      { 
         black = i/3; 
         black_value = color; 
      } 
 
      /* find closest blue color using least squares method */ 
      distance = (63 - game_palette[i+2]) * (63 - game_palette[i+2]) + 
         (21 - game_palette[i+1]) * (21 - game_palette[i+1]) + 
         (21 - game_palette[i]) * (21 - game_palette[i]); 
 
      if (distance < blue_value) 
      { 
         blue = i/3; 
         blue_value = distance; 
      } 
 
      /* find closest gray color using least squares method */ 
      distance = (42 - game_palette[i+2]) * (42 - game_palette[i+2]) + 
         (42 - game_palette[i+1]) * (42 - game_palette[i+1]) + 
         (42 - game_palette[i]) * (42 - game_palette[i]); 
 
      if (distance < gray_value) 
      { 
         gray = i/3; 
         gray_value = distance; 
      } 
   } 
} 
This code does two things: First, it sets the first 32 colors to the RGB values defined in the game_palette array, using Fastgraph's fg_setdacs() function:

   fg_setdacs(0,32,game_palette); 

Second, the code scans the palettes to find the closest colors to black, white, blue, and gray. The reason I chose these colors is because my game editor menu uses them for the menus. When a new PCX file is loaded and the palettes are changed, I "fix" the menu colors by finding the closest match to black, white, blue, and gray. Of course, since the first 32 palettes are fixed, I don't really need to keep calculating the black, white, blue, and gray values, because they will be the same the next time. But in the development process, the first 32 palettes are not fixed. Sometimes we change our mind about a sprite. Perhaps the sprite started with a blue shirt, but ended up with a red shirt. Instead of hard-coding the value for blue into our code, we calculate it on the fly, which speeds up our development process and saves us the aggravation of recalculating blue, changing it in the header file, and then recompiling all the modules.

You'll find this color-matching algorithm useful in other places in your game as well. You may decide at some point that you must have a dark magenta for a menu item, for example. Instead of manually editing your artwork to find the closest color to magenta, which will change every time your artwork changes (as it constantly does), just write code to find the color you want.

Using the Least Squares Method

To actually perform the work of color matching, we use a system called the least squares method. Here is how it works: Think of a color as a point in space. The RGB coordinates represent distances on three axes. The problem is then reduced to finding the shortest distance between two points in three-dimensional space, as shown in Figure 8.2.

Figure 8.2 Colors represented as points in space.

In the fix_palettes() function, we are interested in matching the following four colors:

RGB
white636363
black000
gray424242
blue212163

There are lots of points in color space, and we want to find the ones closest to our desired points. We find them by calculating the distance between all the points and choosing the point with the shortest distance.

The distance between two points is determined by taking the square root of the sum of the squares of the distances in three directions, corresponding to the three axes in Cartesian coordinates. (If you need a brush up on this, check your high school geometry book). The formula is shown here:

*(x2-x1)2 + (y2-y1)2 + (z2-z1)2 

Similarly, the distance between two points in color space is:

*(R2-R1)2 + (G2-G1)2 + (B2-B1)2 

< Note: That's supposed to be "squared". Superscript the 2's. Diana. >

All we need to do is find the distance between our desired color and all the other colors, then choose the shortest distance. We do this by looping from i = 0 to i < 255*3, in groups of three. This gives us an index for traversing the game_palette[] array. The game_palette[] array stores the red, green, and blue components of the color, so we must increment by three bytes for each color:

 
/* find closest blue color using least squares method */ 
distance =   (63 - game_palette[i+2]) * (63 - game_palette[i+2]) + 
   (21 - game_palette[i+1]) * (21 - game_palette[i+1]) + 
   (21 - game_palette[i]) * (21 - game_palette[i]); 

For simplicity (and efficiency), we don't take the square root. We are not concerned with the actual distance between points, just the relative distances, which will be consistent in the squares. We compare the distance to the previous value for blue (which was initialized to a high value):

 
if (distance < blue_value) 
{ 
   blue = i/3; 
   blue_value = distance; 
} 

If the distance is the lowest, the color blue is assigned to the current palette, and the blue_value variable is assigned the shortest distance. This continues in a loop until all 255 colors are examined.

It is possible to have no blue value in the selected palettes. When this happens, the algorithm will choose a shade of gray or cyan, or whatever color is closest to blue. If you need a shade of blue that isn't in the palette, then you will need to adjust your palettes manually. To do this, I recommend a good paint program such as Deluxe Paint, NeoPaint, or Improces.

Changing a Single Color

Occasionally you will want to change a single color instead of a whole range of colors. In particular, I notice I often want palette 255 to be white. That is especially true in programs that use the mouse, such as a game editor. Fastgraph's default mouse cursor uses palette 255 for the white arrow, and palette 0 for the black outline. Once again, you have to tell your artist to keep his or her hands off of that palette, and once again there is a good likelihood he or she will ignore you. To change color 255 back to white, use Fastgraph's fg_setrgb() function:

 
fg_setrgb(255,63,63,63); 
This function call sets the red, blue, and green components of the DAC register to the highest intensity (in other words, white).

Fixing Palettes with PALETTE.EXE

During the process of writing this book, I had several people beta test my code by trying to import their artwork into my game. I discovered they always had problems with palettes. Common problems included a sprite file changing a background palette, two sprite files using different palettes, and background files using too many colors and overflowing into the sprite palette set. All of these problems are fixable, but the fix was time consuming and is difficult to explain. In an effort to remedy this situation, I wrote a quick- and-dirty palette-management program called PALETTE.EXE, which is included on the disk. The purpose of this program is to give you control over the colors in your artwork so that it can be easily imported into the game. The PALETTE.EXE program allows you to reduce a file to either 32 sprite colors or 224 background colors, match a file to 32 sprite colors or 224 background colors, or merge the color palettes from two files, combining the first 32 colors from one file with the last 224 colors of another file. Here's how it works.

Running PALETTE.EXE

< Note: Download palette.zip from the downloads page. Diana. >

If you installed the software properly with the default directories, you will find the palette program in the subdirectory \FG\UTIL\. When you launch the program by typing PALETTE, you will see the screen in Figure 8.3.

Figure 8.3 The input screen for PALETTE.EXE.

The palette program has a simple interface. You may move between the fields using the arrow keys. You can enter the filenames and choose file types, match files, and operations, and you will get an output file with the new colors. The possible combinations are listed in Table 8.3.

Table 8.3 Palette Operations

Input File TypeOperationMatch FileResult
BackgroundReduceNoneOutput file contains 224 colors that are the closest match to the original 256 colors
BackgroundMatchBackgroundOutput file contains 224 colors that match the last 224 colors in the match file
BackgroundMergeSpriteOutput file contains 256 colors that match the last 224 colors in the background file and the first 32 colors in the sprite file
SpriteReduceNoneOutput file contains 32 colors that are the closest match to the original 256 colors
SpriteMatchSpriteOutput file contains 32 colors that match the 32 colors in the match file
SpriteMergeBackgroundOutput file contains 256 colors that match the first 32 colors in the sprite file and the last 224 colors in the background file

Reducing Background Colors

Background files contain tiles. The colors are assumed to be different than the sprite colors. The reason for this assumption is that sprite colors are consistent throughout the game, but background colors may be different on different levels. If your background file was drawn using more than 224 colors, you will want to reduce it to 224:

<< Project:>>

Load the file TOMMY.PCX. Specify the file type as background. Select the choose best colors operation. Enter TEMP.PCX as the output filename. The screen should look like Figure 8.4. Press F10 to begin the reduction. The Palette program will reduce the file to 224 colors. It will set the first 32 colors to black and redraw the picture so that only the last 224 colors are used. The modified picture will be written to the file TEMP.PCX. If you want to view the TEMP.PCX file, you may use any paint program or file viewer, or for convenience I have included a simple file viewer on the disk called PCX.EXE. To view the output file, exit the palette manager program and type this:

PCX TEMP.PCX

<<end project>>

Figure 8.4 Reducing background colors.

Reducing Sprite Colors

Sprite files are assumed to have 31 visible colors and one transparent color (color 0). Often your artist will goof this up and give you an art file using many random palettes. To reduce this to 31 palettes, let the Palette program choose the best colors for you.

<< Project >>

Load the file SCORPION.PCX. Specify the file type as sprite. Select the choose best colors operation. Enter TEMP.PCX as the output filename. The program will reduce the number of colors in SCORPION.PCX to 31 and put them in palettes 1-31. Palette 0 and palettes 32-255 will be set to black.

<< end project >>

Matching Background Colors

Occasionally an artist may draw two backgrounds, or two parts of the same background, that are intended to be used together in the same level. If the palettes don't match, you can make them match. This option will match all the colors in the input file to the last 224 colors in the output file.

<< project >>

Load the file JUNGLE.PCX on the first line. Specify the file is a background file. Select the match operation. Enter TOMMY.PCX in the match file field. Enter TEMP.PCX in the output file field. The program will match all the colors in JUNGLE.PCX to the last 224 colors in TOMMY.PCX.

Now reverse the process. Enter TOMMY.PCX as the input file and match all the colors in JUNGLE.PCX. Notice that you get better results matching colors in this direction. The reason is that some files have better color selection than other files. The JUNGLE.PCX file has a nice spectrum of colors. The TOMMY.PCX file is a product of a ray-trace program, and has too many pastel colors. It is easier to map a pastel palette to a general purpose palette than vice versa.

<< end project >>

Matching Sprite Colors

Most often, you will want to match a sprite file to a file you already have. For example, if your artist draws a scorpion in the colors of his choice, you will want to modify the picture to match Tommy's colors.

<< project >>

Load the file SCORPION.PCX. Specify the file type as sprite. Select the match operation. Enter TOMRUN.PCX in the match file field. Enter TEMP.PCX in the output file field. The palette program will reduce the scorpion art to the 31 colors that match Tommy's colors. Color 0, the transparent color, will be set to black.

<< end project >>

Merging Colors

After your sprite files and background files have been reduced, you may want to merge them together. The reason is that if you display a background file and the first 32 colors are all 0, you will wipe out your foreground palettes. Similarly, when you display your sprites you will wipe out your background colors. The easiest way to solve this is to include the sprite palette information in the background files.

<<project>>

Load the file JUNGLE.PCX. Specify this is a background. file Select the merge operation. Merge with the file TOMRUN.PCX. Call the output file TEMP.PCX. The result will be a file containing background art and both background and foreground colors.

Be sure to specify JUNGLE.PCX as a background file; otherwise, the program will match the first 32 colors from JUNGLE.PCX and the last 224 colors from TOMRUN.PCX. This results in all the colors being set to bright magenta--definitely not the desired result!

To reverse the process and merge the sprite colors and background colors in the sprite file, enter TOMRUN.PCX as the input file and specify that is of file type sprite . Select the merge operation and enter JUNGLE.PCX as the match file. The output will be the sprite file artwork with the first 32 colors the same, and the last 224 colors set to the colors in JUNGLE.PCX.

<< end project >>

Examining the Palette Source Code

The source code for the palette program is found in the \FG\UTIL\ subdirectory. the files required to build PALETTE are listed in Table 8.4.

Table 8.4 Source Code Files Required to Rebuild PALETTE

FilenameDescription
PALDEFS.HDefinitions and global declarations
CHAR.CCharacter string functions
PALETTE.CPalette merging, matching, and reduction; controlling functions

We'll discuss the CHAR.C file in Chapter 9. The functions of interest are in the PALETTE.C file and are listed in table 8.5.

Table 8.5 Functions in PALETTE.C

Function nameDescription
main()Main function
activate_screen()Activates the user interface
do_reduction()Selects type of palette reduction/matching
error_message()Displays an error message
file_exists()Checks for an existing file
fix_suffix()Adds ".PCX" to a filename
match()Palette matching function
merge()Palette merging function
quit_graphics()Resets the video mode and return to DOS
redraw_screen()Draws the user-interface screen
reduce()Palette reduction function
show_match_string()Displays the match string

The source code to manage the user interface is long and boring, and I am not going to list it here. The three functions that do the work of managing palettes are match(), merge(), and reduce(). Let's take a closer look at those, beginning with match().

 
void match(int ncolors) 
{ 
    unsigned long target,distance; 
    int color,match; 
    unsigned int i,j; 
    unsigned int start,end; 
 
    fg_setpage(1); 
    fg_showpcx(matchfile,0); 
    fg_setpage(0); 
    fg_move(0,199); 
    fg_getimage(buffer1,320,200); 
 
    if (ncolors == 32) 
    { 
       start = 0; 
       end = 32*3; 
    } 
    else 
    { 
       start = 32*3; 
       end = 256*3; 
    } 
 
    fg_getdacs(0,256,match_colors); 
    for (i = 0; i < 256*3; i+= 3) 
    { 
      target = 63L*63L*63L; 
      for (j = start; j < end; j+= 3) 
      { 
         distance =         (input_colors[i+2] - match_colors[j+2]) * 
         (input_colors[i+2] - match_colors[j+2])         + 
         (input_colors[i+1] - match_colors[j+1]) * 
         (input_colors[i+1] - match_colors[j+1])         + 
         (input_colors[i] - match_colors[j]) * 
         (input_colors[i] - match_colors[j]);         if (distance < target) 
         { 
            match = j/3; 
            target = distance; 
         } 
      } 
      match_palette[i/3] = (unsigned char)match; 
   } 
   for (i = 0; i < 320*200; i++) 
      buffer2[i] = match_palette[buffer1[i]]; 
 
   fg_move(0,199); 
   fg_putimage(buffer2,320,200); 
   return; 
} 

The match() function uses the same least squares method we saw earlier in the fix_palette() function. A variable called ncolors, containing a value of either 32 or 224 is passed to match(), indicating whether we want to match the first 32 colors or the last 224 colors. Similarly, ncolors is passed to the merge() function, indicating which type of merge we need to do:

 
int merge(int ncolors) 
{ 
   register int i; 
 
   if (!file_exists(matchfile)) 
      return(ERR); 
 
   fg_setpage(1); 
   fg_showpcx(matchfile,0); 
   fg_setpage(0); 
   fg_getdacs(0,256,match_colors); 
 
   if (ncolors == 32) 
   { 
      for (i = 0; i < 32*3; i+=3) 
      { 
        output_colors[i] =   match_colors[i];
        output_colors[i+1] = match_colors[i+1]; 
        output_colors[i+2] = match_colors[i+2]; 
      } 
      for (i = 32*3; i < 256*3; i+=3) 
      { 
        output_colors[i] =   input_colors[i]; 
        output_colors[i+1] = input_colors[i+1]; 
        output_colors[i+2] = input_colors[i+2]; 
      } 
   } 
   else 
   { 
      for (i = 0; i < 32*3; i+=3) 
      { 
        output_colors[i] =   input_colors[i];
        output_colors[i+1] = input_colors[i+1]; 
        output_colors[i+2] = input_colors[i+2]; 
      } 
      for (i = 32*3; i < 256*3; i+=3) 
      { 
        output_colors[i] =   match_colors[i];
        output_colors[i+1] = match_colors[i+1]; 
        output_colors[i+2] = match_colors[i+2]; 
      } 
   } 
   fg_setdacs(0,256,output_colors); 
   return(OK); 
} 

The merge() function is quite simple. It generates values for the output_colors[] array based on what it finds in two other arrays: input colors[] and match colors[]. By comparison, the reduce() function is quite complicated:

 
void reduce(int ncolors) 
{ 
   unsigned long target,distance; 
   unsigned long max_target; 
   int color,match; 
   unsigned int i,j,k; 
   int empty; 
   int nmatches; 
   int nzeros; 
 
   if (ncolors == 224) 
      nmatches = 32; 
   else 
      nmatches = 225; 
 
   fg_move(0,199); 
   fg_getimage(buffer1,320,200); 
 
   for (i = 0; i < 256; i++) 
   { 
      pixel_count[i] = 0L; 
 
      /* start with everything matching itself */ 
      match_palette[i] = (unsigned char)i; 
   } 
 
   /* count how many of each color */ 
   for (i = 0; i < 320*200; i++) 
      pixel_count[buffer1[i]]++; 
 
   empty = 0; 
   for (i = 0; i < 256; i++) 
      if (pixel_count[i] == 0L) empty++; 
 
   /* find two colors that are close to each other */ 
   for (max_target = 1; max_target < 63L*63L*63L; max_target*=2) 
   { 
      /* compare every color to every color greater than it */ 
      for (i = 0; i < 256*3; i+=3) 
      { 
         if (pixel_count[i/3] != 0) 
         { 
            target = 63L*63L*63L; 
            for (j = i+3; j < 256*3; j+= 3) 
            { 
               if (pixel_count[j/3] != 0L) 
               { 
                  distance = 
                  (input_colors[i+2] - input_colors[j+2]) * 
                  (input_colors[i+2] - input_colors[j+2])                  
+ 
                  (input_colors[i+1] - input_colors[j+1]) * 
                  (input_colors[i+1] - input_colors[j+1])                  
+ 
                  (input_colors[i] - input_colors[j]) * 
                  (input_colors[i] - input_colors[j]);
                  if (distance < target)  /* closest match so far */ 
                  { 
                     match = j/3;
                     target = distance;      /* how close is it? */ 
                  } 
               } 
            } 
            if (target < max_target)      /* within tolerance */ 
            { 
 
               /* set all i colors to whichever j color matched */ 
               pixel_count[i/3] = 0L;
               match_palette[i/3] = (unsigned char)match; 
 
               /* if any colors matched i, match them to j */ 
               for (k = 0; k < j/3; k++) 
               { 
                  if (match_palette[k] == (unsigned char)(i/3)) 
                     match_palette[k] = (unsigned char)match; 
               } 
               empty++; 
               if (empty >= nmatches) break; 
            } 
         } 
      } 
 
      /* update the image for this pass */ 
      for (i = 0; i < 64000; i++) 
         buffer2[i] = match_palette[buffer1[i]]; 
      memcpy (buffer1,buffer2,(unsigned int)64000); 
      fg_move(0,199); 
      fg_putimage(buffer1,320,200); 
 
      /* tally the pixels again */ 
      for (i = 0; i < 256; i++) 
      { 
         pixel_count[i] = 0L; 
 
         /* each color matches itself again */ 
         match_palette[i] = (unsigned char)i; 
      } 
 
      /* count how many of each color */ 
      for (i = 0; i < 320*200; i++) 
         pixel_count[buffer1[i]]++; 
 
      /* we have reached our target -- enough empty palettes */ 
      if (empty >= nmatches) break; 
   } 
 
   if (ncolors == 224) 
   { 
      /* move all the colors to the last 224 */ 
      j = 32; 
      for (i = 0; i < 256; i++) 
      { 
         if (pixel_count[i] > 0L) 
         { 
            match_palette[i] = (unsigned char)j; 
            fg_setrgb(j,input_colors[i*3], 
                        input_colors[i*3+1], 
                     input_colors[i*3+2]); 
            j++; 
         } 
      } 
      /* set the first 32 colors to 0 */ 
      for (i = 0; i < 32; i++) 
          fg_setrgb(i,0,0,0); 
   } 
   else 
   { 
      /* move all the colors to the first 32 */ 
      j = 1; 
      for (i = 0; i < 256; i++) 
      { 
         if (pixel_count[i] > 0L) 
         { 
            match_palette[i] = (unsigned char)j; 
 
            fg_setrgb(j,input_colors[i*3], 
                        input_colors[i*3+1], 
                        input_colors[i*3+2]); 
            j++; 
         } 
      } 
      /* set the first 224 colors to 0 */ 
      for (i = 32; i < 256; i++) 
          fg_setrgb(i,0,0,0); 
   } 
 
   /* update the image one last time */ 
   for (i = 0; i < 64000; i++) 
      buffer2[i] = match_palette[buffer1[i]]; 
   memcpy (buffer1,buffer2,(unsigned int)64000); 
   fg_move(0,199); 
 
   /* display the new image */ 
   fg_putimage(buffer1,320,200); 
   return; 
} 

The reduce() function reduces colors in a picture by moving pixels from one color register to another color register. When it is determined two colors are close (within a given tolerance), the function assigns pixels of both colors to just one of the color registers. It does this by updating an array called match_palette[]. Each pass through the reduction loop, pixels are assigned to either their original color or their match color. The number of empty colors is then counted. Eventually, the number of colors has been reduced to the target value, either 224 or 32.

This function is a bit complicated, and understanding it is not really necessary to understanding the rest of the game-engine code. If you are having trouble with it, I suggest you skip it and move on to the next chapter.

Good Advice

That covers the palette problems we face while constructing our game and game editor. We will close this chapter with a bit of good advice from Tommy:

Planning Your Palettes

Plan your palettes carefully and try to choose your colors early in the development cycle. Last minute changes in your colors can cause expensive and time-consuming changes in your code and artwork.

Next Chapter

So you want to be a Computer Game Developer?

_______________________________________________

Cover | Contents | Downloads
Awards | Acknowledgements | Introduction
Chapter 1 | Chapter 2 | Chapter 3 | Chapter 4 | Chapter 5 | Chapter 6
Chapter 7 | Chapter 8 | Chapter 9 | Chapter 10 | Chapter 11 | Chapter 12
Chapter 13 | Chapter 14 | Chapter 15 | Chapter 16 | Chapter 17 | Chapter 18
Appendix | License Agreement | Glossary | Installation Notes | Home Page

Fastgraph Home Page | books | Magazine Reprints
So you want to be a Computer Game Developer

Copyright © 1998 Ted Gruber Software Inc. All Rights Reserved.