Lode Storm – Implementing classic fog of war

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:

fogofwar

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:

Image

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.

marchingsquarescode

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.

Advertisements

Binding Tiny C Compiler

Years ago I found a interesting library called TinyCC, which provided a simple and small C compiler with one major twist…  it can be embedded inside another application.  Because of this, a program can compile new functions for itself at run time and call them using function pointers.  In a sense it can be used like an immensely powerful scripting language, with the benefit that there is no speed hit due to interpretation or emulation.  Its weakness as a scripting language is that you have to account for portability and security problems due to the execution of these ‘scripts’ running as native code on the host processor.

So far, I have used TinyCC for a few projects in the past and recently in a texture generator as well as my text adventure engine.  The reason for this post however, is that TinyCC is not the most intuitive thing to embed into a windows application, so I wanted to take a moment to explain one clean method to do so.

There is no static library for use with visual C++ so that option is out, however since a fully compiled DLL file is included in the download package, it seemed that it would be easiest to dynamically link the DLL through code at run time.  This requires loading the DLL and requesting all of the functions that are exported from it which is a fairly easy operation on any platform and generally differnt OS’s have much the same interface for doing so. The only tricky part is actually specifying all of the annoying function pointer casts correctly during binding.

Without farther talk, here is some straight forward code to load TinyCC and bind the interface for you. Which I hope it should all be fairly straight forward and easy to understand.

libtcc_bind.h

libtcc_bind.cpp

Stealth and Shadows

Shadows

My decision to follow a tile based map representation has led me to explore several things I like in games, and to see how they can be implemented in a tile based world, efficiently and robustly.

One of the things I have been experimenting with, and love seeing implemented, is a method for computing fast real time 2D shadows. Since I want to take Ninja Flare in a direction towards a ninja stealth game, shadows will be a very welcome addition to the game play.  The image above shows the state of my progress in this area. The large outlined grey rectangle represents a conceptual viewing area and thus the limit of the distance of the shadows.  In reality some shadow edges project beyond this area because I have not yet implemented any clipping.  The yellow circle in the middle of this area represents the light source. The darkening of the shadowed regions was added afterwards in Photoshop only to help give me an idea of the accuracy of my results.  In order to complete this method I will need to implement a fast triangle or quad filler to shade all the shadowed regions.  This could be done in software if I stick with SDL, or a perhaps easier strategy is to use Direct3D to do the filling for me.  One of the nice benefits of the method I came up with for computing these shadows is that it requires no pre-processing so it will react to any changes in the map structure.

Space Invader Generator

Image

I read about a very interesting technique some time ago. A method was proposed for generating a completely random set of low resolution space invader like creatures. The idea was extremely simple and elegant. The key to the technique is its use of symmetry, since the human mind likes to find form and meaning in symmetric things.

For my implementation I chose a size of 5×5 pixels for my invaders and a line of symmetry down the middle. More specifically, the first three pixels of each row are random, and the last two are mirrors of the first two. For this technique I implemented my own pseudo random number generator using a linear feedback shift register technique. The color of each of the invaders shown corresponds to the seed of the random number generator when it was formed. This seed could be used to re-generate any space invader, but this implementation does not support this currently since the seed is 32bits wide and a colour is clearly 3x8bits or 24bits.

The code can be found here:

http://pastebin.com/223eTMka

It would be great to add this to a game like geometry wars and have all of your enemies procedurally generated, from their visuals down to their abilities. The scope for using this in a retro computer game seem really endless.

Isometric Water

Image

Here is a video of a little demo I put together a few years back. For this demo, I decided to take a popular and very fast method for simulating water in 2D and project it isometrically over a typical game land mass. I had to create a software Z-Buffer using the alpha channel of the 32bit frame buffer. This is so that the water waves interact with and don’t penetrate the voxels of the landscape as well as rendering properly. I also implemented rudimentary diffraction and shadows on the water waves. Everything here is software rendered using fixed point arithmetic. I really love this effect and I would love to apply this technique to any game I made using an isometric terrain.

Watch it in motion here:

Art and animation practice

I have not just been working on Ninja Flare since the submission deadline of LD#26 however. I have been experimenting with lots of pixel art for game ideas I have had.

Image

Since my childhood have always loved the god games from Bullfrog, such at theme park and dungeon keeper. I have always wanted to make a god/simulation game involving a small group of people trying to gather resources to survive the natural elements. I made a mockup of what a game of this sort may look like visually. The little people could collect food by hunting and fishing, as well as collecting lumber for fires and for making cabins to shelter from the cold.

An alternative in the same vein as the above game is shown below.

Image

The game would take place on a small island, far out at sea. A man and his wife, live out there days in a small cabin on top of this island. It would be more of an interactive simulation then a game in my mind. Just something nice to look at. There would be a day and night cycle, rain, snow and sunshine. The plants and flowers could come into bloom and then die off. The man and his wife would collect resources and use them to survive, again fishing, collecting wood, rocks etc to maintain themselves and their cabin. The art style shown is not really what I was aiming for so I will still be playing around with this idea a lot.

There was a great entry into this LD#26 Game Jam that really resonated with me. It is called potato dungeon. The art and setting are just great and really inspired me to knock up a pixel style demake of it.

Image

The characters here are just great fun to animate. The dragon is my own design, but the horse, knight and pig are very true to the art of the original. I would love to program a mockup of this one day.