Something that practically every game that has ever been made uses is compression for the artwork.  The reasons for this are many.  For example: 

Save space on the distribution media:  This is obvious, but sometimes subtle.  If your game is 3 disks with uncompressed artwork, and 2 with compressed, it’s a cost savings.  It cost about $1 per disk (regardless of media) to produce.  If you’re planning on selling 50,000 units, then you just saved $50,000 that now goes to profit.  If you plan on selling 1,000,000 units, well…try and get it on one disk. 

Privacy: This one is a little more subtle, but still important.  If you don’t want your players to see what the full map, or the win screen, looks like, then don’t put it as a standard BMP file.  Because, the users will always look at their hard drives, and if they see files they recognize they’ll try and open them.  This may or may not be a concern.  If all you want to do is thwart the casual user, simply changing the filename extension can work wonders.  This trick however will not work on "power users". 

Speed: This is one of the most often overlooked issues of compression.  The slowest devices in a computer are it’s drives.  The hard drive is the fastest, then come CD’s, and floppies are the slowest.  If you want to improve the performance of a game that accesses the disk a lot (and what modern CD-ROM game doesn’t?), you can simply reduce the amount of data that has to be read.  Consider that a full screen (640x480x256 colors) bitmap is 307,200 bytes.  As a test I just drew a picture of a happy face and saved it as JPEG.  The result was a file that was 15,146 bytes, that’s approximately 20:1 compression.  I also tried the same image as PCX, the result was a file that was 13,399 bytes, that’s almost 23:1.  This test wasn’t fair, I knew that the image I drew would compress better with PCX than JPEG, usually JPEG is better.  But if you’re reading all of your data from a disk, and spending lots of time waiting for loads, that’s a theoretical 23 times speed increase in your game. 

There are many types of compression readily available.  The ones I mentioned above were JPEG (also known as JPG) and PCX.  These aren’t really compression algorithms, rather they are file formats.  They each use different compression algorithms.  JPEG uses a fairly complicated, but lossy algorithm.  Lossy means that if you compare the source image, and an image compressed with JPEG, they will not be identical.  The idea behind JPEG is to store things the same way the human eye and brain perceive them.  So you shouldn’t be able to tell the difference between the source image and the compressed image without having the computer do a compare.  This isn’t true for all pictures.  JPEG was specifically designed to be efficient with photographs of real things.  This is a good thing, because that’s where most other compression algorithm fall apart.  Most games will not use JPEG because of how processor intensive it is to decompress the images.  You may end up with a speed hit instead of increase if you go this way.  And besides, it’s not the algorithm I’m going to describe in detail anyway. 

PCX files use a compression algorithm known as Run Length Encoding (RLE).  RLE seems to be the compression algorithm of choice among game programmers.  This is because of several reasons:  it is easy to code, blazingly fast, works well on the type of artwork that is in traditional games, has great performance for images that have transparency, and it is lossless (meaning the compressed image will uncompress identical to the source image). 

The way RLE works is that instead of storing every pixel, it stores runs of pixels.  So if you have 20 pixels in a row of the same color (it happens a lot in game graphics), they’ll be stored as count & color.  So instead of using 20 bytes, you’ve used 2.  This isn’t to say the RLE works well for everything.  It has it’s pitfalls, just like everything else.  It is possible that your image won’t ever have two pixels of the same color next to each other (this happens in photographs a lot).  The result would be that instead of taking 1 byte to store each pixel, you’d have 2, the run (1 pixel) and the color.  Therefore your image would double in size.  A game like Myst would have suffered greatly from using this algorithm.  Another drawback to RLE is that it’s really optimized for 256 or less colors.  It was originally invented for 16 color graphics, but adapted to 256 colors.  So if your using 15, 16 or 24 bit artwork in your game, find another algorithm.  However, just because the game runs in 24 bit color, doesn’t mean the artwork needs to be.  You can display as many 256 color bitmaps on the screen as you want on a 24 bit screen and not worry about palette conflicts. 

The simplest implementation of RLE compression is to use two bytes for every group of pixels, and make the first byte the length and the second byte the color.  However, this tends to make the images larger than they need to be.  And if there are no runs in the image, the image will double in size.  Another implementation would be to only put a run byte in when there is a run of bytes, otherwise just store the color.  But you have to have some way of distinguishing between runs and colors.  If you only use 128 colors in your image, then you can specify the run bytes as always having the high bit set, and colors don’t (since 0-127 is only 7 bits).  That way only bytes with the high bit set are runs, and it is impossible for the image to grow in size.  But artists never want to be limited to 128 colors, they’re usually unhappy with 256.  So another algorithm was invented, it’s the best (and worst) of both worlds, and requires very little additional processing. 

The idea behind this algorithm is to use the top 2 bits as the identifier for a run.  Both bits have to be set in order to specify a run.  This does mean that the colors 192 (1100000 binary) through 255 (11111111 binary) can’t be stored as single bytes.  If there is a single pixel of one of these colors, it is stored as a run of 1.  If the source image has a normal distribution of random colors, and no two pixels in row are the same color, the image will grow in size by 25%.  Not as bad as doubling, but not as good as no growth.  But it does have 256 colors.  The drawback to this is that the runs are limited to being 6 bits, so your maximum run is 63 or 64 (depending on how you implement 0, since there will never be a run of 0 bytes).  This usually isn’t a problem, in my experience you usually have runs of 5 or 6, not 60’s.  The code to decompress a RLE looks something like this: 

void Uncompress(unsigned char *RLESource, unsigned char *UncompressedDest)
{
...
    if(*RLESource & 0xC0 == 0xC0) // 0xC0 = 11000000 in binary
    {    // It’s a run.
        memset(UncompressedDest,*(RLESource+1),(*RLESource)&0x3F);
        // set the number of bytes, after masking off the key.
        UncompressedDest+=(*RLESource)&0x3F;
        // Skip the number of pixels we just set.
        RLESource+=2;
        // Skip to the next run/pixel in source.
    }
    else
    {   // It’s not a run.
       *UncompressedDest=*RLESource;
       // Set the pixel in the dest.
       UncompressedDest++;
       // Go to the next pixel in dest.
       RLESource++;
       // Go to the next run/pixel in source.
    }
...
}

The above implementation doesn’t account for size of image, or getting to the end of the file. 

The other really advantageous thing about RLE is that if you’re using transparency, then all you have to add is to detect whether the color is your transparent key or not.  If it is, then simply skip the assignment step, and increase the pointers, and you have your transparency. 

It’s also possible to implement a scaling algorithm imbedded inside the decompression algorithm, so that you can decompress to an arbitrary size rather than having to decompress to another buffer and then scale blit.  You can also decompress directly to the draw surface if your implementation is fast enough to not have flicker, although usually it’s best to decompress to an off-screen buffer.