Comment déterminer quelles cellules d'une grille se croisent avec un triangle donné?

J'écris actuellement une simulation d'IA 2D, mais je ne suis pas complètement certain de savoir si la position d'un agent est dans le champ de vision d'un autre.

Actuellement, mon partitionnement mondial est un simple partitionnement de l'espace cellulaire (une grille). Je veux utiliser un triangle pour représenter le champ de vision, mais comment puis-je calculer les cellules qui se croisent avec le triangle?

Similaire à cette image:

Les zones rouges sont les cellules que je veux calculer, en vérifiant si le triangle coupe ces cellules.

Merci d'avance.

ÉDITER:

Juste pour ajouter à la confusion (ou peut-être même pour la rendre plus facile). Chaque cellule a un vecteur min et max où le min est le coin inférieur gauche et le max est le coin supérieur droit.

Calculez les trois coins de votre triangle fov, faites-les pivoter pour qu'ils soient orientés dans le bon sens, puis effectuez l'une des opérations suivantes:

1) faire un test point par triangle pour toutes les cibles potentielles

2) calculer la boîte englobante de ce triangle et faire un test point par triangle pour toutes les cibles potentielles dans les cellules de cette boîte englobante - ce sera un code très simple à déboguer

Une approche similaire consiste à utiliser un quadtree plutôt qu'une grille et à faire les intersections à ce sujet. Si l'accès à la tuile O (1) vous accélère, alors simplement tester toutes les cellules dans les limites du triangle fov pour en-triangle devrait être si rapide qu'il soit instantané. Alors que vous envisagez d'autres options, je suppose que ce n'est pas le cas et que le O (1) prend en fait un énorme coût de manque de cache lorsque vous détruisez votre cache. Vous pouvez bien sûr regarder les instructions de prélecture pour annoter votre promenade de boîte englobante avec ...

3) `` pixellisez '' ce triangle et vérifiez les cellules qu'il `` peint '' - probablement le code le plus efficace, mais peut-être seulement de manière marginale car je suppose que tout est dominé par les temps de manque de cache et dépend de la complexité de vos cellules et de leur occupation elles sont.

Une autre approche consiste à rendre le FOV sur une image bitmap hors écran, puis à lire la valeur en pixels de chacun de vos objets; vous ne pouvez pas «démélanger la peinture» mais avec un nombre limité d'objets et en choisissant soigneusement votre peinture, vous pouvez déduire qui a vu qui. Cette approche est similaire au nombre de jeux qui déterminent ce sur quoi l'utilisateur a cliqué - ils dessinent la scène hors écran en utilisant des couleurs unies pour les zones touchées. Les GPU sont très rapides à remplir en triangle ...

La solution canonique dans les moteurs de rendu logiciel (qui doivent faire cet algorithme exact chaque fois qu'ils pixellisent un triangle) est, je crois, de balayer le triangle une ligne de pixels à la fois. Les bords gauche et droit de chaque ligne et calculés en descendant les côtés du triangle à l'aide de Bresenham , puis vous remplissez la ligne entre eux.

Je passe sous silence de nombreux détails, mais c'est l'idée de base. Si vous recherchez le «rendu logiciel» et la «tramage triangle», vous trouverez probablement plus de détails. C'est un problème bien résolu. Votre carte graphique fait cela des millions de fois par image.

Si vous voulez une solution plus spécifique à roguelike, voici comment j'ai implémenté FOV dans le mien. Cela semble fonctionner assez rapidement. Il s'agit essentiellement d'un simple lanceur d'ombres, travaillant sur l'octant à la fois, balayant vers l'extérieur depuis le joueur.

J'utilise une variante de l'algorithme scanline pour résoudre exactement le même problème. J'ai commencé par trier les trois points triangulaires selon leur hauteur. Je vérifie ensuite essentiellement si deux bords sont à gauche ou à droite. Pour le côté avec deux bords, vous devez marquer leur ligne là où vous changez le bord qui délimite vos lignes. Pour le côté avec un bord, vous pouvez toujours l'utiliser.

Donc, pour chaque ligne, je sais quels deux bords le délimitent et je peux calculer les limites supérieure et inférieure dans la direction x. Cela semble assez compliqué, mais il se condense en quelques lignes de code. Assurez-vous de manipuler le cas spécial où un bord est complètement horizontal!

Que diriez-vous de maintenir une plage de colonnes pour chaque ligne qui se trouvent dans le triangle? Ce que vous pouvez faire est de définir la colonne min et max pour chaque ligne où se trouve chaque point et où chaque ligne de triangle croise une ligne de séparation de ligne horizontale.

public class Point
{
    public float X;
    public float Y;
    public Point(float x, float y) { this.X = x; this.Y = y; }
}

public class Line
{
    float ROW_SIZE = 100f;
    float COL_SIZE = 100f;

    public Point P1, P2; // P1 has the lowest Y
    public float Slope, Intercept; // set in constructor
    public bool IsVertical;

    public Line(Point p1, Point p2)
    {
        if (p1.Y > p2.Y) { P1 = p2; P2 = p1; } // p1 has lowest Y
        else { P1 = p1; P2 = p2; }
        IsVertical = (p1.X == p2.X);
        if (!IsVertical) { Slope = (p2.Y - p1.Y) / (p2.X - p1.X); Intercept = p1.Y - Slope * p1.X; }
    }

    public void ExpandRanges(int[] minCol, int[] maxCol)
    {
        // start out at row, col where P1 is, which has lowest Y
        int row = (int)(P1.Y / ROW_SIZE);
        int col = (int)(P1.X / COL_SIZE);
        int lastRow = (int)(P2.Y / ROW_SIZE);
        int lastCol = (int)(P2.X / COL_SIZE);

        // expand row to include P1
        minCol[row] = Math.Min(col, minCol[row]); maxCol[row] = Math.Max(col, maxCol[row]);

        // now we find where our line intercepts each horizontal line up to P2
        float currY = P1.Y;
        float currX = P1.X;
        while (row < lastRow)
        {
            row = row + 1;
            float rowY = row * ROW_SIZE;
            float diffY = rowY - currY;
            float diffX = IsVertical ? 0f : diffY / Slope;
            currY = currY + diffY;
            currX = currX + diffX;
            col = (int)(currX / COL_SIZE);

            // expand rows above and below dividing line to include point
            minCol[row - 1] = Math.Min(col, minCol[row - 1]);
            maxCol[row - 1] = Math.Max(col, maxCol[row - 1]);
            minCol[row] = Math.Min(col, minCol[row]);
            maxCol[row] = Math.Max(col, maxCol[row]);
        }

        // expand last row to include P2
        minCol[lastRow] = Math.Min(lastCol, minCol[lastRow]);
        maxCol[lastRow] = Math.Max(lastCol, maxCol[lastRow]);
    }

    public static void Test()
    {
        Point p1 = new Point(160, 250);
        Point p2 = new Point(340, 250);
        Point p3 = new Point(250, 40);
        Line l1 = new Line(p1, p2);
        Line l2 = new Line(p2, p3);
        Line l3 = new Line(p3, p1);

        Line[] lines = { l1, l2, l3 };

        int rowCount = 4;
        int[] minCol = new int[rowCount];
        int[] maxCol = new int[rowCount];
        for (int i = 0; i < rowCount; i++)
        {
            minCol[i] = int.MaxValue;
            maxCol[i] = int.MinValue;
        }

        for (int i = 0; i < lines.Length; i++)
            lines[i].ExpandRanges(minCol, maxCol);

        for (int i = 0; i < rowCount; i++)
            Console.WriteLine("Row {0}:  {1} - {2}", i, minCol[i], maxCol[i]);
    }
}

Production:

Row 0:  2 - 2
Row 1:  1 - 3
Row 2:  1 - 3
Row 3:  2147483647 - -2147483648

Il y a un travail d'algorithme fait dans la communauté roguelike qui traite de FOV / LOS / éclairage dans un monde basé sur les tuiles.

Vous trouverez peut-être sur cette page quelque chose qui peut être utilisé pour résoudre votre problème: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Plus précisément, "FOV permissif" pourrait être le plus approprié à votre situation.