Hello!
I am experimenting with fog of war and line of sight for a real-time strategy game I plan to develop. The game will support a (practical) maximum of 100 units per player. Each player only needs to compute the line of sight of his/her own units. The map consists of a grid with each tile being either a wall or open space. A unit's vision range is 3-10 tiles. It is very important that tiles behind walls are hidden, i.e. the vision circle has "shadows". My main problem is performance vs. quality. It feels a like too much processing power is put into something so "trivial" as fog of war...
I have found many interesting articles about line of sight in Rogue-like games using line algorithms to ray-trace from the unit (the player) and out. I believe this to be to slow for 100 units. The goal is to make the game playable on somewhat old Intel integrated cards, usually paired with single-core CPUs or low-end dual-cores.
I haven't been able to find any information about how today's RTS games do fog of war and line of sight. I'm interested in the solutions used by games like Warcraft 3, League of Legends and similar games that have vision occluders (trees, walls, etc).
I'm developing the game in Java using LWJGL/OpenGL, so I suppose most libraries e.t.c. won't be usable...
Thanks!

Hey!
You could pre-calculate the LOS for each tile using the max LOS distance for any unit. This could increase the loading time of your level "dramatically" depending on the size, but may be worth it. Then, just lookup the list of tiles which can be seen for each unit according to the tile it's standing on.

As long as you don't build LOS blocking walls during the game, you should be fine; although, even this can be handled efficiently given you have already computed the lookup table.

Hope this helps.

Precalculating is a good idea but really 100 raycasts against static geometry is not a big deal. 1000 probably isn't if you're targeting PC only. To get things going I'd just do a bounding sphere test and if raycast towards any units that pass the bounding sphere test. If you notice it is too slow (and you have profiled to be sure it's the raycasts) then try alternating doing odd units one frame and even units another frame.

I can see the point of pre-calculating the values, but that would produce very blocky fog of war. I also realized that I obviously don't need to recompute the FOW and LOS each frame, a few times per second should be enough. I'm onto an idea I got yesterday, I'll report back here when I have tested it a bit more.

Hello again. I have found a solution for now. I don't know how it'll look when I implement it on 3D terrain, but it looks okay for now.
This is the fog of war and line of sight overlay attached as a texture to the world when drawn:
[attachment=1468:FOW.png]

and this is the map used to test the visibility of units. It's the same map as before, but intensity based on a threshold. The blue dots represent enemy units that are inside the fog of war.
[attachment=1469:FOW2.png]

The idea is that each tile's light intensity is dependent on the 2 tiles in the direction of the light.
[attachment=1470:sketch.png]
This means that once a tile's intensity has been calculated it can be reused.

The calculation is done using a recursive function that checks the two closer tiles and blends them together depending on the angle. This means that there are 8 cases, one for each "pizza slice". This also produces a soft "shadow", which I think looks great. To check the visibility of an enemy unit, I just check if the intensity of the tile the unit is standing on is over a certain threshold. I also increase the contrast, as it looked too blurry before. I can post code if anybody wants it (Java).
When I have computed my lightmap, I just send it as a texture to OpenGL.

Pros:
Fast enough, performance depending on light size and number of lights. My game will use <=10 tiles vision range.
Looks great (so far).
CPU-calculated, thread-able (per light).
Lights can have floating point positions.

Cons:
Curved shadows on large lights (~15+ tiles, depending on shadow casters)
Slightly sharp shadows for some angles (45 degrees, 135 degrees, ...)
Tiles close to walls are darker due to interpolation (I will fix this if it looks bad, but it could give a ambient occlusion-like effect).
Not directly portable to a pixel shader, as it uses recursion. Needs multiple passes or no caching.