Line-of-sight algorithm for tile-based tactics

Question

I've tried Bresenham line and Raycasting, but they don't quite give the results I need (examples in the screenshot).

'&' - character

'+' - cells that can be attacked by the character

'#' - walls

Supercover:

Bresenham:

As can be seen in the screenshot, a character can attack a cell, but if moved to it, it cannot attack from there to its original position.

Is there a fair algorithm so that a character who can attack an enemy can be attacked by the enemy in return.

Perhaps the problem is in my code?

void FieldOfSight(Field &field, const Vector2i &player, float distance,
                  int type)
{
    Vector2i endPosition;
    float    radians = 0;
    float    step    = M_PI / (distance * 10);

    while (radians < 2 * M_PI) {
        endPosition.x = player.x + round(cos(radians) * (distance));
        endPosition.y = player.y + round(sin(radians) * (distance));
        if (endPosition.y >= field.GetHeight())
            endPosition.y = field.GetHeight() - 1;
        else if (endPosition.y <= 0)
            endPosition.y = 0;
        if (endPosition.x >= field.GetWidth())
            endPosition.x = field.GetWidth() - 1;
        else if (endPosition.x <= 0)
            endPosition.x = 0;
        radians += step;

        switch (type) {
        case (0):
            SupercoverLine(field, player, endPosition);
            break;
        case (1):
            WalkLine(field, player, endPosition);
            break;
        case (2):
            BresenhamLine(field, player, endPosition);
            break;
        }
    }
}

void SupercoverLine(Field &field, int x0, int y0, int x1, int y1)
{
    int dx = x1 - x0, dy = y1 - y0;
    int nx = abs(dx), ny = abs(dy);
    int sign_x = dx > 0 ? 1 : -1, sign_y = dy > 0 ? 1 : -1;

    int px = x0, py = y0;

    field.SetFG(px, py, 8);

    for (int ix = 0, iy = 0; ix < nx || iy < ny;) {
        int decision = (1 + 2 * ix) * ny - (1 + 2 * iy) * nx;
        if (decision == 0) {
            px += sign_x;
            py += sign_y;
            if (field[py - sign_y][px] == 1 && field[py][px - sign_x] == 1)
                break;
            ++ix;
            ++iy;
        } else if (decision < 0) {
            px += sign_x;
            ++ix;
        } else {
            py += sign_y;
            ++iy;
        }
        if (sqrt((x0 - px) * (x0 - px) + (y0 - py) * (y0 - py)) > 5 ||
            field[py][px] == 1)
            break;
        field.SetFG(px, py, 8);
    }
}

void WalkLine(Field &field, int x0, int y0, int x1, int y1)
{
    int dx = x1 - x0, dy = y1 - y0;
    int nx = abs(dx), ny = abs(dy);
    int sign_x = dx > 0 ? 1 : -1, sign_y = dy > 0 ? 1 : -1;

    int px = x0, py = y0;
    for (int ix = 0, iy = 0; ix < nx || iy < ny;) {
        if ((0.5 + ix) / nx < (0.5 + iy) / ny) {
            px += sign_x;
            ix++;
        } else {
            py += sign_y;
            iy++;
        }
        if (sqrt((x0 - px) * (x0 - px) + (y0 - py) * (y0 - py)) > 5 ||
            field[py][px] == 1)
            break;
        field.SetFG(px, py, 8);
    }
}

void BresenhamLine(Field &field, int x0, int y0, int x1, int y1)
{
    int dx    = abs(x1 - x0);
    int sx    = x0 < x1 ? 1 : -1;
    int dy    = -abs(y1 - y0);
    int sy    = y0 < y1 ? 1 : -1;
    int error = dx + dy;
    int x = x0, y = y0;

    field.SetFG(x0, y0, 8);

    while (true) {
        if (x0 == x1 && y0 == y1)
            break;

        int e2 = 2 * error;

        if (e2 >= dy) {
            if (x == x1)
                break;
            error += dy;
            x += sx;
        }
        if (e2 <= dx) {
            if (y == y1)
                break;
            error += dx;
            y += sy;
        }

        if ((field[y - sy][x] == 1 && field[y][x - sx] == 1) ||
            sqrt((x0 - x) * (x0 - x) + (y0 - y) * (y0 - y)) > 5 ||
            field[y][x] == 1)
            break;
        field.SetFG(x, y, 8);
    }
}

Sorry for the code without comments

Answer 1

As the answer by Tim C explained, it's not possible in a tile-based world to guarantee that a character who can see a tile can also see it from any point which counts as part of that line-of-sight. The reason is that tiles don't offer sufficient resolution. You would need floating-point positions for that to work.

But if you want fairness in the sense that "if A can attack B, then B can attack A", then one solution would be to calculate both the sight-line from A to B and then from B to A, and only consider it unbroken if both are unbroken (or if one of them is unbroken, if you want to be more liberal).

What you can also do to fake a higher resolution for sightline calculation is to use floating-point-precision raycasting, but not just cast the rays from the center of the character. Cast rays from multiple points of the character, and cast them to multiple points on the target.

In this example, I am using 3 points per character and calculate 9 lines of sight of which 4 connect and 5 are broken. The more points you use, the more accurate and predictable the results. The computational cost increases quadratically with the amount of points you sample, but in case of a turn-based game on modern hardware, that should not be too much of a problem.

You can also use this method to quantify visibility. For example, in this case you could say that 9/5 obstructed lines of sight means that the target is 56% in cover, and feed that information into your combat or stealth mechanics.

Answer 2

This is a partial answer. I can explain the cause of the problem you're seeing, but I don't have any proposal to fix it.

Subsets of valid sightlights are not guaranteed to be valid sightlines

This is, I think, the property that's causing you trouble (and resulting in your asymmetry). I'll illustrate with a diagram.

Consider a line pointing 9 tiles to the right, and 1 square up:

##########
.....xxxxx
@xxxx.....
##########

Now add a wall right before the crossover point. Walking through the supercover algorithm, this line of sight is still valid. decision is exactly 0 at the crossover point (nx = 9, ny = 1, ix = 4, iy = 0), so it will make the diagonal step.

##########
....#xxxxx
@xxxx.....
##########

However, the following, shorter sightline is not valid, despite being a subset of the other sightlight.

##########
....#x....
@xxxx.....
##########

Why does this matter?

These algorithms are symmetric end-to-end. If you can see an endpoint, the endpoint can see you. However, there is no guarantee that every point along that sightline can see you. For example, in the following

##########
....#@...b
a.........
##########

The Supercover algorithm will not allow any sightline from @ to reach a, even though a can see @ through its sightline to b

I believe this is the reason you are seeing the behavior that you are.

Described mathematically, "You can see a space if you can draw a line from the center of your space to the center of another space, which passes through any part of the intervening space." If you take this to the limit as vision range increases, the meaningfulness of the distant target space falls away and the definition becomes result would be, "You can see a space if you can draw a line from the center of your space to any part of the target space"

Because your sight-lines are from the center, but you allow visibility by even the smallest corner, the result will be asymmetric visibility even when using symmetric line-rasterizing algorithms.