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!

2d tile based strategy game. Field of view, I guess. It's basically a fog of war type situation. See which tiles are visible to the player's army so that I can tell which units are visible, which tiles to color black (since they're unseen) etc.

A simple approach of implementing a field of view could be to use a modified midpoint circle algorithm. You can use this algorithm to clear a circular area around a given point on a fog of war map (for example). The algorithm looks something like the this:

// This code was taken from http://en.wikipedia.org/wiki/Midpoint_circle_algorithm, ported to JavaScript and modified
// to draw a filled circle.
function drawFilledCircle(centerX, centerY, radius) {
    var x = radius,
        y = 0,
        radiusError = 1 - x;

    while (x >= y) {
        drawLine(x + centerX, y + centerY, -x + centerX, y + centerY);
        drawLine(y + centerX, x + centerY, -y + centerX, x + centerY);
        drawLine(y + centerX, -x + centerY, -y + centerX, -x + centerY);
        drawLine(x + centerX, -y + centerY, -x + centerX, -y + centerY);

        y += 1;

        if (radiusError < 0) {
            radiusError += 2 * y + 1;
        } else {
            x--;
            radiusError += 2 * (y - x + 1);
        }
    }
}

However, the code above doesn't take line of sight into consideration, meaning all tiles in range will be considered visible.

To check for line of sight between two given tiles you could use Bresenham's line algorithm instead. Here it is (again JavaScript):

// This code is based on an example taken from http://de.wikipedia.org/wiki/Bresenham-Algorithmus
function drawLine(fromX, fromY, toX, toY) {
    var deltaX = Math.abs(toX - fromX),
        deltaY = -Math.abs(toY - fromY),
        signX = fromX < toX ? 1 : -1,
        signY = fromY < toY ? 1 : -1,
        error = deltaX + deltaY;

    while (true) {
        drawPixel(fromX, fromY);

        if (fromX === toX && fromY === toY) {
            break;
        }

        if (error * 2 > deltaY) {
            error += deltaY;
            fromX += signX;
        }

        if (error * 2 < deltaX) {
            error += deltaX;
            fromY += signY;
        }
    }
}

You could also combine both algorithms to get what you want:

1. Collect all tiles within range using the first algorithm.
2. Check for each collected tile if it is in line of sight using the second algorithm.
3. Remove all tiles that are not in line of sight from the collection.
4. You're done!

This might not be the very best solution for your problem but it might be a start (and it should work I guess). I hope it helps!

Burrick, I took a look at Bresenham, but wouldn't that have speed problems? As I see it, I'd have to run the Bresenham routine for every square within range of one of the player's units. I can't even limit it to testing tiles that have units on them, since I need to know if I tile is visible so I can color it black to show it's not in the line of sight. Is that kind of algorithm feasible from a speed standpoint?

By optimizing output, do you mean the graphics output? If so, it's a bit tricky figuring out the relative timing. See, it's for a multiplayer game that's client/server. The server needs to be where the field of view stuff is done so that the players can't cheat and use hacks to see hidden units. But the graphics of course will be done on the client.

Hi.

if you know the stating point and the end point of the line of sight then

You could use Bresenham algorithm by starting the search with a rectangle around the line of sight start and end points.

or if you only know the starting point and a direction pluss max vision then you could vector at tile step intervals then call up

what cell is under the current interval set.