I'm developing a turn based strategy game, and I'm trying to figure out the best way to figure out what tiles are visible to the users. So if the user has say, 50 units in their army, they can see any tile that any of those 50 units has a line of sight to that isn't blocked by an obstacle tile. I'm looking for something that's not too inefficient, since it's a server based game and I'd rather not bog down the server with a lot of calculations. Can anyone point me to some resources, if possible some code? It's in C#, and would be done entirely in an asp.net project (so no access to DirectX or XNA) libraries, etc.

Thanks!

I'd like to add that, in a tiled turn-based strategy game, line of sight is pretty much up to you to design. A turn-based strategy game is fairly abstract. You're basically making a fancy board game, not a simulation. I'd look at the rules for board games for inspiration, and then figure out how to port a board game mechanic I like into software.

For example, I remember one system with a pretty simple line-of-sight rule - the D&D miniatures game. I think it's got a slightly different name and set of rules now but I'm sure Wizards of the Coast still hosts the rulebook for free somewhere on its website. I think the rule is that you can see another square if you can draw a line from any corner of your square to any corner of the target square without passing over an obstacle square. I think you could see past corners as long as both sides of the corner are not blocked. If you cannot picture that, I'm sure if you find a rulebook there will be diagrams. So, to brute-force the test, all you need is to intersect a line and a square, and then iterate over corners.

My main point is that there is no one true algorithm for what you want. You need to play game designer a bit more before you play software engineer. Of course your software engineer half might tell your game designer half that his idea is impossible to program, but currently I think you should focus on what you want the rule to be.

For example, I remember one system with a pretty simple line-of-sight rule - the D&D miniatures game. I think it's got a slightly different name and set of rules now but I'm sure Wizards of the Coast still hosts the rulebook for free somewhere on its website. I think the rule is that you can see another square if you can draw a line from any corner of your square to any corner of the target square without passing over an obstacle square. I think you could see past corners as long as both sides of the corner are not blocked. If you cannot picture that, I'm sure if you find a rulebook there will be diagrams. So, to brute-force the test, all you need is to intersect a line and a square, and then iterate over corners.

Dungeons and Dragons v 3.5 and Pathfinder roughly use that line of sight idea. Each has an system reference document that you can look up their line of sight checks. http://d20srd.com and http://d20pfsrd.com.

http://www.wizards.com/default.asp?x=dnd/glossary&term=Glossary_dnd_lineofsight&alpha=

For Wizard's official ruling.

wodinoneeye, the prebuild idea's a great one. I think it's also a good point that I can decide what the rules are before I code. Definitely it's worth checking out how board games and table top RPGS handle it, particularly since I'm trying for a turn based strategy game based on tiles rather than a real time RTS.

You might also be interested in this wiki article about the field of vision in roguelikes:

http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

There are some strategies explained. Perhaps they would fit your game?

I found the ruling for Line of Sight/Effect for Pathfinder:

Line of Effect

A line of effect is a straight, unblocked path that indicates what a spell can affect. A line of effect is canceled by a solid barrier. It's like line of sight for ranged weapons, except that it's not blocked by fog, darkness, and other factors that limit normal sight. A line of effect starts from any corner of your square and extends to the limit of its range or until it strikes a barrier that would block it. A line-shaped spell affects all creatures in squares through which the line passes.

Line of Sight

A line of sight is the same as a Line of Effect but with the additional restriction that that it is blocked by fog, darkness, and other factors that limit normal sight (such as Concealment).

How does that work? Do you do the calculation 4 times, one for each corner, or do you just pick any corner?

I found the ruling for Line of Sight/Effect for Pathfinder:

Line of Effect

A line of effect is a straight, unblocked path that indicates what a spell can affect. A line of effect is canceled by a solid barrier. It's like line of sight for ranged weapons, except that it's not blocked by fog, darkness, and other factors that limit normal sight. A line of effect starts from any corner of your square and extends to the limit of its range or until it strikes a barrier that would block it. A line-shaped spell affects all creatures in squares through which the line passes.

Line of Sight

A line of sight is the same as a Line of Effect but with the additional restriction that that it is blocked by fog, darkness, and other factors that limit normal sight (such as Concealment).

How does that work? Do you do the calculation 4 times, one for each corner, or do you just pick any corner?

I found the ruling for Line of Sight/Effect for Pathfinder:

Line of Effect

A line of effect is a straight, unblocked path that indicates what a spell can affect. A line of effect is canceled by a solid barrier. It's like line of sight for ranged weapons, except that it's not blocked by fog, darkness, and other factors that limit normal sight. A line of effect starts from any corner of your square and extends to the limit of its range or until it strikes a barrier that would block it. A line-shaped spell affects all creatures in squares through which the line passes.

Line of Sight

A line of sight is the same as a Line of Effect but with the additional restriction that that it is blocked by fog, darkness, and other factors that limit normal sight (such as Concealment).

You do check all 4 corners, but only until you find one that works. In Dungeons and Dragons (and Pathfinder), a regular person stands in a 5 feet by 5 feet square. They don't fill up that square, that's just the size that grants unhampered movement, so in essence, they can move and look from (or shoot from) any corner of their square without the game's rules saying that they have moved any non-negligible distance. To help understand, a person can squeeze into an area that is 2.5 feet by 2.5 feet square before getting stuck (ie they can't squeeze into a space any smaller).