Last night I couldn’t sleep, and one of the reasons was that my mind was busy trying to explore the problem of how to implement FOW in my game Lode Storm for this months 7 day mini Ludum Dare.  I got up again and at 1:30am set about solving this problem in a nice manner.  After about two hours, the results looked suitably retro and I had some fun designing a neat algorithm in the process.  Here is the result:

Any RTS game aspiring to the classics of the genre would not be complete without some Fog of war (FOW) effect.  Warcraft Orks and Humans is a game that very much rely on FOW, and has a great rendering style for it too.  I took this as my basis and set out to mimic the visual effect.

It is immediately obvious that in this case, the FOW is just another tile map, as an overlay to the main game map.  While each tile is either in fog or not (binary), some extra processing has occurred to make a visually smooth transition around the hard boarder.

The stages seem evident:

1. Within the game logic update the binary FOW map
2. Process the binary FOW map to derive a visual FOW map
3. Render using the same process as a regular tile map

Stages 1 and 3 are quite clear and shouldn’t require much discussion.  Stage 2 is however much more illusive and I will show you how I solved that in just a moment.

For stage 3 we require a visual overlay that will be rendered with a transparency mask to provide a pixel dissolve effect for the transition.  I spent some time in Photoshop and knocked up the following map:

All of the tiles needed for a complete FOW effect are there, and in fact there is a little duplication in the corner tiles, but that is not important.  In stage two we need to take the binary FOW map and through analysis of each game time, produce and index corresponding to a tile in this image.

For stage 2, a few ideas to explore came to my mind.  I remember coding up a demo that performed terrain analysis using a Sobel filter, a very similar operation, however that code was written long ago and is on an eternal hard drive I don’t have access to at the moment.  Browsing over the Wikipedia page, it wasn’t immediately clear to me how to approach the problem with a Sobel filter.  The second option that came to mind is to employ a variation of the Marching Squares algorithm.  I haven’t programmed anything using this technique before, however it has always been something I have kept in mind to try one day.

As I understood it Marching squares assigns a unique code to each tile based on the tile values sampled at each corner.  To clarify this point, for each corner of the a tile we set it to true if it touches any other tile that is in FOW, otherwise false.  The image below shows that if any of the yellow squares have their bit set in the FOW map, then the corresponding code will be set to true.  This can be done by summing each tile around the corners using a bit wise OR operation.

Once these four Boolean values for the quadrants A, B, C and D have been found, we can proceed to produce the marching squares code.  This can simple be done by shifting and summing each of the bits, to produce 16 possible values.  Therefore the output value would be:

int out = (A<<3) | (B<<2) | (C<<1) | D;

The last step is to take the marching square code and use a translation table, mapping each marching squares code to a FOW image index.

In the end here is the code I came up with.  Please note that, ‘conv’ is the conversion table for the marching squares code to the image map.  In the current version of Lode Storm I used a modified version of the above FOW image, so it does not correspond to that.  You will notice that I perform a binary AND with 0x8, in the final step of my marching squares code computation, and this is because my FOW map is stored in one bit of a larger array of flags for each tile, so the 0x8 isolates only the FOW bit.

//
// tile byte flags layout
// 
//    0xF                  0x0
//    Z  L  0  0  H  C  W  E
//
//  0x80 - Z - tile locked for units    (unit on tile)
//  0x40 - L - lode locked              (lode on tile)
//  0x08 - H - human fog of war         (binary, not the aesthetic map)
//  0x04 - C - computer fog of war        " "
//  0x02 - W - water                    (block move not LOS)
//  0x01 - E - elevation                (block move and LOS)
//
//
//
inline int fog_getIndex( int x, int y )
{
    // marching squares conversion table
    uint8 conv[] =
    {
        13,  1,  0,  8,
         2, 13, 10,  4,
         3,  9, 13,  5,
        11,  7,  6, 12
    };
    // convenience
    uint8 *t = tile_flags + (x + y * 32) - 33;
    // surrounding squares
    uint8 q[ 8 ] =
    {
        t[00], t[01], t[02],
        t[32],        t[34],
        t[64], t[65], t[66]
    };
    // sum to find out quadrant values
    int a  = q[0] | q[1] | q[3];
    int b  = q[2] | q[4] | q[1];
    int c  = q[7] | q[6] | q[4];
    int d  = q[5] | q[3] | q[6];
    // turn into marching square code
    int v  = (a & 0x8) >> 0;
        v |= (b & 0x8) >> 1;
        v |= (c & 0x8) >> 2;
        v |= (d & 0x8) >> 3;
    // index conversion table
    return conv[ v ];
}

Additionally, there is one small omission from the code above.  If a tile has its FOW bit set in the FOW map, then it should immediately skip this processing and be set to straight black.  Tiles should only be processed using the above method if they are not part of the hard FOW.