Fix 4 tile and line checks

[NiteKat]

Switches to a better line drawing algorithm for monsters that need to check if they have line of sight, and fixes situations in the ranged AI where they would just stand still, allowing a player to freely kill them with no resistance.

The old line drawing algorithm only worked in one direction, so if that direction worked, but the other direction didn't and the other direction is the one the projectile would actually travel from the monster, then it would erroneously think it could land a hit. This algorithm works in all directions, so it can safely check the proper path. There still may be an occasional instance where the correct line is not drawn, but I think I've only seen that in one or two instances in testing, much more rare than the vanilla code.

The other change, fixing the standing still behavior, just modifies that code path so the monster walks towards the players. In the original code there was a code path that if there was no line of sight, the monster would just stand still. This should probably do something more intelligent, like find a spot that has line of sight and move toward that, but in the spirit of how the AI originally behaves, I just made it walk to the player. This produces some pacing behavior, but eventually they might settle in a proper spot to attack the player. Better than just standing there. :)

This change will also make monsters that are on top of the player think they don't have a line of sight (to avoid division by 0), which can happen if a player spawns on the floor while a monster is on the spawn tile. I don't think this'll have a big impact on gameplay - most monsters that would end up in this position would want to run away due to the distance, and for those that wouldn't (like maelstroms and blood stones, etc.), it just means they'll stick to melee instead of using their ranged attack.

This may need some additional play testing to make sure there aren't any bad side effects. Thank you to @galaxyhaxz for help with the line algorithm! And thank you to @qndel for helping me stumble through my first pull request.

[NiteKat]

I forgot to note in my pull request, this still does not take blocking objects into account (like Cauldrons).

[julealgon]

The description seems to indicate 2 distinct behaviors on this one. Can we make it 2 separate changes?

[AJenbo]

Apparently this has rounding issues (irrational numbers not adding up to x.0000 when they are "suppose" to) and the following showed improve it:

bool checkLineofSight(int x, int y)
{
    if (x == game->self().getX() && y == game->self().getY())
        return true;

    float x1 = game->self().getFutureX();
    float y1 = game->self().getFutureY();
    int dx = x - game->self().getFutureX();
    int dy = y - game->self().getFutureY();
    int dunX = 0;
    int dunY = 0;
    int steps = 0;
    bool done = false;

    if (abs(dx) > abs(dy))
        steps = abs(dx);
    else
        steps = abs(dy);

    float Xinc = (float)dx / steps;
    float Yinc = (float)dy / steps;

    for (int i = 0; i <= steps; i++) {
        x1 += Xinc;
        y1 += Yinc;
        if (abs(Xinc) < 1) {
            if (Xinc < 0) {
                dunX = ceil(x1);
                dunY = y1;
            } else {
                dunX = floor(x1);
                dunY = y1;
            }
        } else {
            if (Yinc < 0) {
                dunX = x1;
                dunY = ceil(y1);
            } else {
                dunX = x1;
                dunY = floor(y1);
            }
        }
        if (dunX == x && dunY == y)
            return true;
        if (!game->getDungeonPiece(dunX, dunY) || !game->getDungeonPiece(dunX, dunY)->allowsMissile())
            return false;
    }
    return false;
}

[NiteKat]

Apparently this has rounding issues (irrational numbers not adding up to x.0000 when they are "suppose" to) and the following showed improve it:

Note this is from my AI in relation to DAPI, so some of this is not relevant to the DevilutionX code, but it's working on the same principles. If I remember correctly, this is slightly improved, as I was trying to fix a few things with the algorithm. This doesn't have the attempted fix for rounding issues in it though, as I realized that's on another branch I didn't copy from. For right now, I'm going to leave the PR with the rounding issues as it's still "better" when coupled with the AI fix (because while they might occasionally think they can't hit when they can, they will think they can hit when they can't in much fewer scenarios).

Another thing this doesn't check is for objects in the way, but the original game doesn't check that either. So that's something that should be added in to this fix eventually too.

[qndel]

new lines for { } make me uncomfortable 😅

[NiteKat]

4tile.zip lineofsightwithdoor.zip

Two save files, one with Fire Clan archers shooting at the player with most not able to hit through a door (common tactic used to minimize damage, as the player can hit all the archers from where they are standing), and the other with a Flesh clan 4-tiled (standing still, not attacking, not moving, and free to be attacked by the player safely)