Efficient Fog of War

[Mads]

Hi!

I’m implementing fog of war into my tile based game. It’s chunky, meaning that a tile either has the fog, or does not have the fog.
Every frame I set all tiles to “not visible”. Then, I loop through all the entities, lighting up circles of tiles around them. For the circle, I use this algorithm:

public class CircleAlgorithm {
	
	private ArrayList<GridPoint2> pointList = new ArrayList<GridPoint2>();
	
	public List<GridPoint2> getCirclePoints(int x, int y, int radius) {
		pointList.clear();
		for(int j = -radius; j <= radius; j++) {
			for(int i = -radius; i <= radius; i++) {
				if(i*i+j*j <= radius*radius + radius* 0.8f) {
					pointList.add(new GridPoint2(x+i, y+j));
				}
			}
		}
		return pointList;
	}
}

I know it look shady, but it produces really good looking circles for its low complexity. I fear this method of having, and maintaining fog of war is not the best. Here’s an overview of the task, each frame:

• Loop through entire map, setting “not visible” on each tile.
• Loop through all Actors, light up circle (r=3) around the Actor
• The “lighting up” procedure loops through 6*6 tiles, for a radius 3 circle.

I would very much like some input as to how this can be improved! I ruled out only updating the changing parts (as opposed to recalculating every point every frame), because a lot of the vision from actors close to eachother overlap. Because of this, I can not simply “turn off” the circle of vision around an actor.

Maybe I am missing something.

[Hermasetas]

I am actually having the same problem with my game:P

But consider this:

1: Is your light changing every frame? If not you could save some time by only calculating it when it changes.

2: Do you have a performance problem with the way you’re doing it? Seriously I would like to know

[Phased]

I am assuming it is 2D.

First of all, you shouldn’t need to search through every tile, you should just check the tiles being rendered on the screen.

you can just recheck the fog of war when an actor moves.

you could only update the fog of war in locations where an actor moves, instead of checking every actor within view every time it updates, you could have only the tiles around the actor to update.

if your using shaders, you could just send an array of vectors, and create lights around the points, with the rest of the tiles being black / darkened.

[theagentd]

Don’t use LinkedList.

[Mads]

@Hermasetas

I am actually having the same problem with my game:P

But consider this:

1: Is your light changing every frame? If not you could save some time by only calculating it when it changes.
2: Do you have a performance problem with the way you’re doing it? Seriously I would like to know

Alright, only frames that has updates to the fog of war will recalculate it. If this calculation proves costly, this will result in lag-spikes every time the fog of war updates.
Currently, I have no problems. However, I have not tried a real scenario with many units moving on a large map. This means I actually don’t know how well this scales. It does not seem like it would, though.

@Phased

I am assuming it is 2D.

You are correct!

@Phased

First of all, you shouldn’t need to search through every tile, you should just check the tiles being rendered on the screen.

I actually do need to update more than is shown on the screen. The fog is not merely aesthetic - I plan to use the info in AI.

@Phased

you can just recheck the fog of war when an actor moves.

That’s true. Thank you.

@Phased

you could only update the fog of war in locations where an actor moves, instead of checking every actor within view every time it updates, you could have only the tiles around the actor to update.

I don’t see how this would work, seeing as the circle of vision might overlap with other nearby actors. I cannot simply fill the circle around a dead Actor with fog, because some other entity might have shared some of that vision. I hope this makes sense.

@Phased

if your using shaders, you could just send an array of vectors, and create lights around the points, with the rest of the tiles being black / darkened.

I think this still poses the same problem. I don’t use shaders, but I still need to know which tiles are visible in the model.

@theagentd

Don’t use LinkedList.

I fixed it.

[theagentd]

How large area are we talking about here? How many tiles per actor? How many actors?

[Mads]

@theagentd

How large area are we talking about here? How many tiles per actor? How many actors?

For the map, 256 * 256. Each actor will light up a circle of radius 3 around it, meaning 6 * 6 tiles will be checked. There are many Actors, since each tile with a building also will light up tiles.

[theagentd]

That’s nothing. You’re prematurely optimizing. Test it, time it and if it’s slow fix it. The only thing you should optimize right now is possibly pooling your GridPoint2 instances so you don’t generate as much garbage.

[Mads]

@theagentd

That’s nothing. You’re prematurely optimizing. Test it, time it and if it’s slow fix it. The only thing you should optimize right now is possibly pooling your GridPoint2 instances so you don’t generate as much garbage.

The pooling is easily fixable. Thanks for the suggestion, by the way.

I know I should not prematurely optimize, although I would like a solution that scales a little bit better than this does. I know my game is not going to be able to run the levels I would like it to, if I do not fix this.

I imagine the final product to have levels the size of 512^2, or even 1024^2. I seriously doubt a 256^2-size world would be any fun to explore. This is a building game, akin to Warcraft I. That’s a lot of tiles. In this world there would be actors running around. Not one or two, but 50 or 80. Each with a lighting distance of 3, that is (80 * (3*2)^2) 2880 tiles to light up. The player would then have made around 10 buildings, each taking up 4 * 6 tiles. Each of the tiles also light up the world around them, in a circle with a radius of 3. That is another 240 checks through the getCirclePoints code, checking another 8640 tiles. I don’t have time for 11520 checks, even if I limit it to once every movement cycle. This means the game is just not feasible.

Even if this is not possible, I want to get as close as I can. How can this be faster?

[theagentd]

Have you even tried this and timed it? 10 000 tiles is almost nothing.

[Hermasetas]

One easy optimization I can spot:

Do you need to calculate the circles every time?
If it is tile based and all the circles are the same size, couldn’t you store the light in an array?
A 6x6 array as you keep saying

[Mads]

@theagentd

Have you even tried this and timed it? 10 000 tiles is almost nothing.

I have not. I will come back though. Expect necro-threading in a year or two.

@Hermasetas

One easy optimization I can spot:

Do you need to calculate the circles every time?
If it is tile based and all the circles are the same size, couldn’t you store the light in an array?
A 6x6 array as you keep saying

I don’t need to, no. This would remove quite a few calculations. Thanks!

[klaus]

A little late for my input, but maybe it still matters. As @Hermasetas said: you usually don’t need to calculate the FOW every frame. What I did was I set up a Timer that runs every 500 ms to recalculate the fog.

You could just recalculate the fog every 100 frames or so, but the big advantage of doing it in a timer thread is a second thread taking care of these calculations. So you can use multi threading, that means with today’s hardware (almost everybody has more than one core) you can transfer cpu load away from your main thread.

Be warned though, that it will get more complicated. You have to take care of concurrent updates to maps and lists (and maybe also other data structures) you need in your fog calculations. That means you have to implement a locking mechanism.

The whole multi threading topic is quite complex, but concerning performance optimisations it is worth learning.