I am looking for a symmetrical LoS algorithm that would allow me to precompute all pair los when creating a level (dungeon or outdoor), and quickly update the table whenever a terrain change is made (mostly when someone opens a door, breach a wall, or when a character creates some kind of barrier).

So I would need to first determine all of the tiles that can see the one being updated, and raycast through the updated cells to update the visibility changes.

I wanted to go with this algorithm to compute LoS from each point, but I would need to change it to make it symmetrical: I was thinking about tracing LoS from center to center, but then, it becomes impractical to determine which cells are affected by a terrain change (because LoS can still be blocked even if you don't have LoS from center to center): I would have to first test each cell to determine whether it sees any part of the one being updated (unless I also store this value for this specific purpose, so I would store whether A can see any part of B, whether B can see any part of A, and whether the center of A can see the center of B).

I suppose if LoS was from center to any part of the target hex, or from any part of the target hex to center, it would remain symmetric, and would make it much easier to get all the cells affected by the change at once (instead of storing whether a center can see another one, I would have to store whether A can see any part of B, and whether B can see any part of A, then OR the results, so that would double the size of the table). That doesn't make for a very elegant rule, and I fear it could be pretty difficult to guess which cells can see each other at a glance.

What other options should I consider?

Thanks!

Indeed, a single LoS query would be fast, but I need the AI to know the visibility from all the tiles reachable in a turn to all tiles reachable by each of the player characters, so that would make quite a lot of LoS queries, while opening or closing a door, or breaching a wall would be a much less common occurrence.

Sorry, I was not very clear:

I am making a turn based tactical game.

I don't need LoS to move units, but I need to get the field of vision for each position an AI unit can reach during its turn to evaluate how good this position is.

Even for a single turn look ahead, I would need to check around 100 tiles for a single unit.

Of course, I can save the processing time for all the non passable tiles, and reuse the results of one unit for another one if they are close enough, but that still makes a lot of Field of views to compute, especially outdoor.

Rather than calculating visibility for every single tile (which could very well just be thrown away on turn 1, the moment the terrain changes), consider calculating the LoS at run-time and caching the result into some kind of lookup table. The next time the game needs to check visibility for that tile, it can use the cached result.

Invalidate the cache when the world geometry changes. A naive solution would be to clear the entire level's cache when the level is modified, but if you have an upper bound on visibility distance, you could get away with dropping cache entries for locations within a box of a certain size.

All in all, this means that the areas of your map where no action is happening aren't doing visibility checks that will just be thrown away before any actors can get there.

With all this said, be sure to profile your game to determine the impact of visibility checks on performance before going down this road.

Good luck. :)

Thank you for your answers.Indeed, both requirements are at odds.

Rather than calculating visibility for every single tile (which could very well just be thrown away on turn 1, the moment the terrain changes), consider calculating the LoS at run-time and caching the result into some kind of lookup table. The next time the game needs to check visibility for that tile, it can use the cached result.

That sounds like a good compromise to me:

Cache the results, and start updating the cache during the player turn, as the AI pieces won't move at this time.

The Los situation is only one of the parameters that will be used. The viability of a tile will be the result of a weighted sum of several factors.

I never said I wanted to move to the tile with the highest number of tiles seen, I merely said that visibility to all "relevant" tiles was important.

The game system would be in the same family as X(-)COM:

The reason for this is that if you want an AI agent to defend an objective by overwatch (opening fire during the player's turn), it better had LoS to the path that leads to it and the player can take if the player is either not visible by the agent, or too protected to shoot now.

On the other hand, if the AI is willing to protect a VIP, it better put it in a position where it can hardly be seen by the player on its next turn.

So if the AI agent is meant to go on overwatch, the idea would be to run an expected value minimax search for the possible moves of the player, and try to find positions where as many as these tiles can be covered.

If he is to attack a given target, on the other hand, the best location would be one where he can see the target, while minimizing the number of player agents that can move and shoot him during their turn.

If it is scouting, maximizing the field number of tiles which are currently unknown to the AI is also desirable.