Creating Fog of War in Games

fog-of-war

Update: It has been brought to my attention that what I have implemented below is essentially the Marching Squares algorithm. Still it might be useful for those who don’t want to deal with too much theory.

One of the core systems in Startup Freak is feature building. The player is presented with a grid which I call “Market Space”. At any given time only some parts of the market is visible and known to player, and this is the area he/she can build features on. In order to build more features the player needs to perform market research. Visually it’s not too dissimilar to an RTS map, hence the title “fog of war”.

Initially this visible area was simply one circle that increased in radius. Recently I made a change so that the player could explicitly pick an area they want to research. As such, the fog of war could have a lot more variations and non-symmetric shapes. I wanted to have a smooth transition into the dark areas, but this turned out to be non-trivial:

Approach 1

One potential approach would be to effectively render the map twice. First we render it to a texture and apply an image blur to it, then render it a second time to the screen and finally apply the blurred texture from the previous step on top. Besides having its own technical challenges, this seemed like a fairly expensive operation for something that I know even many old games on limited hardware implement.

Approach 2

The other way, of course, is to use transition textures. It struck me that given a square grid with an arbitrary set of visible and invisible squares, there are actually a huge number of possible transitions that would need to be accounted for. More importantly I dreaded having to write if blocks for hundreds of scenarios.

Permutations

In order to get a better feel for what I was dealing with, I decided to just sketch up some different scenarios. In these images, the center square represents the grid point for which I want to determine a transition texture. Dark squares represent invisible, and light squares represent visible grid points:

permutationsAt first it looked like a massive list. In fact given each square is surrounded by 8 others, there are 256 possible permutations of visibility for the surrounding squares. But quickly it became apparent that there are only 16 unique configurations and the rest are simply rotations of those:

mapbackground

Now if you have been paying attention, you’ll note that 16 configurations times 4 rotations is only 64. You might ask what happened to the rest of the 256 permutations? Well as it turns out, many configuration of the surrounding square yields the same transition texture. Consider the following 3 scenarios:

similar-permutations

As you can see in all 3 of these configuration, our target square displays the same texture. In a way the squares that are directly up, down, left and right, can be considered as being “dominant”. If they are visible, they override any visibility information coming from the adjacent corner squares.

Encoding

Great, so we have the textures, but how do we go from a set of visible/invisible flags on the squares to the right texture with the right rotation? The obvious choice would be a massive set of if blocks (again there would be 256) but that is far less than ideal. It then occurred to me that maybe I can encode a configuration as a key and use it to look up the right texture instead. So we assign each of the surrounding squares a “bit” in an 8 bit value:

encoding

That last example might seem a bit strange, as I have some bits turned on which are technically not visible. But remember the reason for this in the previous section: the squares immediately to the top, bottom, left and right are dominant so by setting the ALL the bits on that side we can reduce the number of keys we have to deal with.

Generating the key is fairly easy then. Assuming we have the visibility of all the surrounding squares, it looks something like this


byte key = 0;

if (visTopLeft)     key |= 0x1;  // 00000001
if (visTop)         key |= 0x7;  // 00000111
if (visTopRight)    key |= 0x4;  // 00000100
if (visRight)       key |= 0x1C; // 00011100
if (visBottomRight) key |= 0x10; // 00010000
if (visBottom)      key |= 0x70; // 01110000
if (visBottomLeft)  key |= 0x40; // 01000000
if (visLeft)        key |= 0xC1; // 11000001

Mapping to Texture

Now that we have the key, the rest is relatively straight forward. At load time we can setup a dictionary that maps the keys (as generated above) to the transition texture we created earlier with 16 configurations, plus a rotation value (one of possible 4). There is no magic in this part and I just need to sit down and write those mappings. I ended up with 47 mappings.  Here is what my code looks like:


readonly IDictionary<byte, VisibilityTextureRef> _textureRefs = new Dictionary<byte, VisibilityTextureRef>
{
{ ToBin("00000000"), new VisibilityTextureRef(0, 0, 0) },

{ ToBin("00000001"), new VisibilityTextureRef(1, 0, 0) },
{ ToBin("00000100"), new VisibilityTextureRef(1, 0, 1) },
{ ToBin("00010000"), new VisibilityTextureRef(1, 0, 2) },
{ ToBin("01000000"), new VisibilityTextureRef(1, 0, 3) },

{ ToBin("00000101"), new VisibilityTextureRef(2, 0, 0) },
{ ToBin("00010100"), new VisibilityTextureRef(2, 0, 1) },
{ ToBin("01010000"), new VisibilityTextureRef(2, 0, 2) },
{ ToBin("01000001"), new VisibilityTextureRef(2, 0, 3) },

{ ToBin("00010001"), new VisibilityTextureRef(3, 0, 0) },
{ ToBin("01000100"), new VisibilityTextureRef(3, 0, 1) },

{ ToBin("00010101"), new VisibilityTextureRef(0, 1, 0) },
{ ToBin("01010100"), new VisibilityTextureRef(0, 1, 1) },
{ ToBin("01010001"), new VisibilityTextureRef(0, 1, 2) },
{ ToBin("01000101"), new VisibilityTextureRef(0, 1, 3) },

{ ToBin("01010101"), new VisibilityTextureRef(1, 1, 0) },

{ ToBin("00000111"), new VisibilityTextureRef(2, 1, 0) },
{ ToBin("00011100"), new VisibilityTextureRef(2, 1, 1) },
{ ToBin("01110000"), new VisibilityTextureRef(2, 1, 2) },
{ ToBin("11000001"), new VisibilityTextureRef(2, 1, 3) },

{ ToBin("00010111"), new VisibilityTextureRef(3, 1, 0) },
{ ToBin("01011100"), new VisibilityTextureRef(3, 1, 1) },
{ ToBin("01110001"), new VisibilityTextureRef(3, 1, 2) },
{ ToBin("11000101"), new VisibilityTextureRef(3, 1, 3) },

{ ToBin("01000111"), new VisibilityTextureRef(0, 2, 0) },
{ ToBin("00011101"), new VisibilityTextureRef(0, 2, 1) },
{ ToBin("01110100"), new VisibilityTextureRef(0, 2, 2) },
{ ToBin("11010001"), new VisibilityTextureRef(0, 2, 3) },

{ ToBin("01010111"), new VisibilityTextureRef(1, 2, 0) },
{ ToBin("01011101"), new VisibilityTextureRef(1, 2, 1) },
{ ToBin("01110101"), new VisibilityTextureRef(1, 2, 2) },
{ ToBin("11010101"), new VisibilityTextureRef(1, 2, 3) },

{ ToBin("00011111"), new VisibilityTextureRef(2, 2, 0) },
{ ToBin("01111100"), new VisibilityTextureRef(2, 2, 1) },
{ ToBin("11110001"), new VisibilityTextureRef(2, 2, 2) },
{ ToBin("11000111"), new VisibilityTextureRef(2, 2, 3) },

{ ToBin("01011111"), new VisibilityTextureRef(3, 2, 0) },
{ ToBin("01111101"), new VisibilityTextureRef(3, 2, 1) },
{ ToBin("11110101"), new VisibilityTextureRef(3, 2, 2) },
{ ToBin("11010111"), new VisibilityTextureRef(3, 2, 3) },

{ ToBin("01110111"), new VisibilityTextureRef(0, 3, 0) },
{ ToBin("11011101"), new VisibilityTextureRef(0, 3, 1) },

{ ToBin("01111111"), new VisibilityTextureRef(1, 3, 0) },
{ ToBin("11111101"), new VisibilityTextureRef(1, 3, 1) },
{ ToBin("11110111"), new VisibilityTextureRef(1, 3, 2) },
{ ToBin("11011111"), new VisibilityTextureRef(1, 3, 3) },

{ ToBin("11111111"), new VisibilityTextureRef(2, 3, 0) }
};

For readability I’m converting binary strings to values rather than using hex (since C# does not support literal base 2 values). The VisibilityTextureRef simply holds the grid x and y of the texture (remember our texture is a 4×4 grid), and a rotation value between 0 and 3. That is enough information for us to generate the texture U,V values on the fly.

Other Thoughts

Depending on the type of game you are doing, you might also want to have multiple variations of each transition texture to get a bit more variety. The only thing that needs to considered is that the different transition textures need to seamlessly match up at the edges

So there you have it. I’m sure there are other approaches to this problem and I would be keen to hear about them!

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s