Efficient Fog of War

Keep in mind that you only have to draw the fog on tiles which are visible in the current screen. The rest of the map is irrelevant, so you don't need to worry about storing massive numbers of quads that will just get culled anyways.

What are the real constraints here? Is memory usage a significant factor? Obviously CPU time should be minimal but how much can you do in terms of precalculation or amortized calculation across graphics frames?

What kind of hardware are you using for rendering? Ancient, fixed-function pipeline? Vertex/pixel shaders? If you have shaders it should be possible to represent the fog of war as a texture, where each pixel corresponds to a map tile. You can render into this texture to generate a sort of "visibility mask", and then use a second shader to adjust the lighting value on visible tiles so they look nice and "known" versus unknown tiles.

Anyways, that's just spitballing off the top of my head, so... [smile]

Just to clarify, there are two flavors of fog-of-war, the kind you see in modern RTS games which render unobserved terrain and neutral objects slightly darkened but completely hide everything else, and shroud, which is an old-school technique you'd see in the early C&C-esqe games which completely blackens areas that you haven't explored yet. And then there's a combination of the two, where areas you haven't explored yet are in shroud, and areas that you have explored at one point but haven't been observed recently get fog-of-war (i.e. Warcraft II).

The most important thing to keep in mind is that whether or not something is behind shroud, fog-of-war, or neither can have major implications on gameplay, regardless of how you render it. As a matter of fact, I'd say that compared to all the time you'll spend figuring out all your gameplay rules with regards to shoud/FOW and then implementing those and fixing bugs, that how you actually render all of it will be an afterthought. Plus, it tends to fall out naturally from your logical representation. While you may only be interested in the current screen when rendering the FOW, you certainly need to know the FOW state for the entire map at all times so that your objects (and the enemy's) follow the rules even when you can't see them.

Since many gameplay rules tend to be heavily tied to your fog-of-war state, it's hard to offload a lot of work to the GPU, since the CPU needs ready access to that data very frequently. Plus read-back is almost certainly out of the question for older hardware. I think this is part of the reason why you don't see shroud in a lot of newer RTS games (IMO). With only two states, FOW or lack thereof, you can turn your FOW state into a bit vector and perform Boolean operations on it with other bit vectors quite easily on the CPU. When you add the shroud state, the math gets a lot more complicated. And from a visual standpoint, solid black tends to be pretty ugly and once you've played a map long enough, you're already familiar with the terrain and layout so shroud really doesn't serve much purpose. But I'm getting ahead of myself :)

As I mentioned above, you can use a bit vector to represent fog-of-war, where a '1' means foggy and a '0' means clear. It doesn't have to be very high-resolution either, since a fuzzy filtered look on the edges between foggy and not-foggy when rendered can actually improve visual quality. If you're using a polygonal mesh generated from a heightmap, then you can probably get away with half-resolution. So for a 2048x2048 heightmap, you can use a 1024x1024 bit vector, which is 128KB. Each object type then has it's own bit vector it uses as a "mask" for when it needs to update the FOW state (using '0' for clear and '1' for no change). It's also square, however you can precompute which bits are '1' and which bits are '0' using a radius check beforehand. When objects need to "blit" their FOW state to the bit vector, you simply AND the FOW bit vector against the object's mask, and the result is the updated state. AND'ing against a '1' in the mask produces to no change to the existing state (which is what you want), while AND'ing against a '0' produces a clear bit. The reason I use the term "blit" is because this operation needs to be aware of the width, pitch, and height of both bit vectors, since it isn't just a straight bit vector mask. If you want to amortize the cost of this operation across multiple frames, you can only perform some of the blitting each frame and update the final state once it's all finished. It's easy to get away with as well since FOW state doesn't really need to update more than a couple of times per second anyway (at least in the games I've seen). However this requires you double-buffer the FOW state and swap it when the "back buffer" is done blitting.

When it comes time you render, you plug that data directly into a texture that overlays the entire map, at the same resolution as the bit vector (either a monochrome texture, if supported, or the smallest size you can get away with). Terrain, props, and other objects that need to be darkened when underneath FOW can simply sample from the texture in their shaders and multiply their color output by the sampled value, where that sampled value is remapped to a range like [0.5, 1] so areas under FOW (which have a sampled value of 0) aren't completely black. Alternatively, if you don't want all your terrain and prop shaders to be "FOW-aware", you make FOW a separate screen-space pass. Both approaches have their pros and cons.

If you have any questions let us know, I would post a few more details however I'm in a bit of a rush at the moment [smile]

PS. I just realized that I might be suggesting you can't do a lot of this work on the GPU. I'm not saying you can't (as a matter of fact it's probably perfect for a lot of the blitting operations), I'm honestly just more familiar with the CPU techniques for doing it and am adamantly opposed to reading back data from the GPU ;) Perhaps in my next post I'll try to speculate on some GPU methods for FOW.

To follow up on my previous post, there are two somewhat important things I forgot to mention. The first of course is how you might be able to perform a lot of this on the GPU, and how you efficiently return cleared bits to a state of fogginess after a certain delay, once the object has moved away.

The more I think about, the more I start to like doing a lot of the heavy lifting on the GPU, and accepting the cost of reading back the data. Bit vectors are much better for shrouds, where the state only goes one way and stays there, but once you start introducing delays for FOW to return, the bit vector approach turns into a lot of brute force work that is more suitable for the GPU.

Just like we had a big bit vector for the entire level, we now have a big texture (hopefully monochrome, i.e. D3DFMT_A1, or D3DFMT_A8 if that's unavailable). And just like we had a bit vector mask for each object (type) before, we now have a single texture for all objects (same format as the level texture). Fully opaque (Alpha = 1.0) represents area that can be revealed, and fully transparent (Alpha = 0.0) for areas that are unaffected. The trick here is that every object can reuse the same texture as long as they apply it to a quad that's the appropriate size. So an object that can reveal a 20 cell radius will simply use a quad with side lengths twice as long as an object that reveals a 10 cell radius, and the texture scales according. As long as all objects reveal within a radius (i.e. the shape is circular), you can simply create a texture of a giant alpha circle. Make its dimensions equal to the largest reveal radius of all your units, and it will work wonderfully for all objects.

Every frame (or every time you want to update the FOW), you take all the objects that will reveal, and put their position, reveal radius, and reveal delay (how long before the reveal wears off) into an associative container, keyed by position and reveal radius (treated as a 3D coordinate). Note that these values aren't in world coordinates, but rather FOW texture coordinates. So if you have a 1024x1024 FOW texture covering a level of size 2048x2048, and an object that is at [678,1387,10] in world coordinates with a reveal radius of 10 cells, their FOW texture coordinates would be [339,693] and the reveal radius would be 5 pixels. It boils down to something like this, in my horrible pseudocode:

for(each object 'O' belonging to allies)   Key.X = (int)(O.GetX()*LevelFOWTextureWidth/HeightmapWidth)   Key.Y = (int)(O.GetY()*LevelFOWTextureHeight/HeightmapHeight)   Key.Z = (int)(O.GetRevealRadius()*LevelFOWTextureWidth/HeightmapWidth)   FOWRevealers[Key] = FOWSystem.GetRevealDelay()end

It assumes that the level and texture are square, so you'll have to modify that a bit for rectangular levels/textures. However I recommend that you make your FOW texture square regardless of the heightmap dimensions, if you can. Makes a lot of things easier :) Finally, in addition to updating new objects, you also want to decay old objects, by iterating over all the entries already in the container and subtracting the time elapsed since the last update. If any entry has a value less than or equal to zero after the update, remove it from the container. Do this before you add new entries, so that the new entries don't decay on the same frame they're added.

At any rate, once you have the above container and it's been updated, you can iterate it and generate a quad for each entry using the given position and size. These are the reveal quads that use the circle texture you generated above. Rendering is straightforward. Clear the level texture to zero. Enable alpha writes and alpha testing, and only pass alpha values equal to 1.0. Render all the quads using the circle texture. What you end up with is a texture representing the current FOW state, with Alpha = 1.0 for revealed areas and Alpha = 0.0 for fogged areas. You then need to read this back to the CPU, either in one frame, or amortized across several frames by only reading back a small piece each frame.

In the end, you end up with a texture representing the FOW state, hopefully the same one you would have gotten with a CPU approach. Only it was a lot less painful. The only issue is the readback, which again you can spread across multiple frames if you have to.