Jump to content
  • Advertisement
Sign in to follow this  
NoisyPerlin

Simple tile based line of site for strategy game?

This topic is 2104 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement

More information is necessary for a concrete answer: Is this a 2D game? Do you really want *line* of sight, or field of view?

 

In general, it's a collision detection problem: For every unit, you'll have to determine which tiles intersect the line of sight, or which tiles fall within the view volume (if you're actually looking for the field of view).

 

Study basic collision detection algorithms, and that should help.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

@AntiAliased

 

Figure out how many calculations and lines of code are going to be interpreted and consider how many milliseconds your program's going to run before it begins output.

 

Chances are the algorithm could run for 500 units and the output for just 1 unit would still take longer, so you should focus on optimizing output, which in this case is entirely tiles.

 

Which begs the question: How many tiles is one unit's line of sight?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Well the server should do the calculations and just tag the tiles with visible/light level/not visible then before sending them to the client (and not send non visible tiles since the client could maybe cheat then).

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!