Wie kann man bestimmen, welche Zellen in einem Gitter ein bestimmtes Dreieck schneiden?

Ich schreibe gerade eine 2D-KI-Simulation, bin mir aber nicht ganz sicher, wie ich überprüfen soll, ob sich die Position eines Agenten im Sichtfeld eines anderen Agenten befindet.

Derzeit ist meine Weltpartitionierung eine einfache Zellraumpartitionierung (ein Raster). Ich möchte ein Dreieck verwenden, um das Sichtfeld darzustellen, aber wie kann ich die Zellen berechnen, die sich mit dem Dreieck schneiden?

Ähnlich wie bei diesem Bild:

Die roten Bereiche sind die Zellen, die ich berechnen möchte, indem überprüft wird, ob das Dreieck diese Zellen schneidet.

Danke im Voraus.

BEARBEITEN:

Nur um die Verwirrung zu verstärken (oder es vielleicht sogar einfacher zu machen). Jede Zelle hat einen Min- und Max-Vektor, wobei Min die untere linke Ecke und Max die obere rechte Ecke ist.

Berechnen Sie die drei Ecken Ihres Fov-Dreiecks, drehen Sie sie so, dass sie in die richtige Richtung weisen, und führen Sie dann einen der folgenden Schritte aus:

1) Führen Sie einen Punkt-in-Dreieck-Test für alle potenziellen Ziele durch

2) Berechnen Sie den Begrenzungsrahmen dieses Dreiecks und führen Sie einen Punkt-in-Dreieck-Test für alle potenziellen Ziele in Zellen in diesem Begrenzungsrahmen durch. Dies ist ein sehr einfacher Code zum Debuggen

Ein ähnlicher Ansatz besteht darin, einen Quadtree anstelle eines Gitters zu verwenden und die Schnittpunkte darauf zu erstellen. Wenn der Zugriff auf die O (1) -Kachel Sie beschleunigt, sollte es so schnell wie möglich sein, alle Zellen in den Grenzen des Fov-Dreiecks auf In-Dreieck zu testen. Wenn Sie sich andere Optionen ansehen, gehe ich davon aus, dass dies nicht der Fall ist und dass O (1) tatsächlich massive Cache-Fehlkosten verursacht, wenn Sie Ihren Cache verprügeln. Sie können sich natürlich auch die Anweisungen zum Vorabrufen ansehen, um Ihren Begrenzungsrahmen-Spaziergang mit ...

3) "rastern" Sie dieses Dreieck und überprüfen Sie die Zellen, die es "malt" - wahrscheinlich der effizienteste Code, aber vielleicht nur am Rande, da ich spekulieren würde, dass alles von Cache-Fehlzeiten dominiert wird und davon abhängt, wie komplex Ihre Zellen sind und wie beschäftigt Sie sind.

Ein alternativer Ansatz besteht darin, das Sichtfeld in eine Bitmap außerhalb des Bildschirms zu rendern und dann den Pixelwert für jedes Ihrer Objekte zu lesen. Sie können Farbe nicht „entmischen“, aber mit einer begrenzten Anzahl von Objekten. Durch sorgfältige Auswahl Ihrer Farbe können Sie ableiten, wer wen gesehen hat. Dieser Ansatz ähnelt der Anzahl der Spiele, auf die der Benutzer geklickt hat. Er zeichnet die Szene außerhalb des Bildschirms mit Volltonfarben für die Trefferbereiche. GPUs sind bei Dreiecksfüllung sehr schnell ...

Die kanonische Lösung in Software-Renderern (die genau diesen Algorithmus jedes Mal ausführen müssen, wenn sie ein Dreieck rastern) besteht meines Erachtens darin, das Dreieck jeweils eine Pixelreihe zu scannen. Der linke und der rechte Rand jeder Reihe werden berechnet, indem Sie mit Bresenham die Seiten des Dreiecks hinuntergehen und dann die Reihe zwischen ihnen ausfüllen.

Ich beschönige viele Details, aber das ist die Grundidee. Wenn Sie nach "Software-Rendering" und "Dreieck-Rasterisierung" suchen, werden Sie wahrscheinlich weitere Details finden. Dies ist ein gut gelöstes Problem. Ihre Grafikkarte macht dies millionenfach pro Frame.

Wenn Sie eine roguelike-spezifischere Lösung wünschen, habe ich FOV in meiner implementiert. Es scheint ziemlich schnell zu funktionieren. Es handelt sich im Wesentlichen um einen einfachen Schattenwirker, der jeweils an einem Oktanten arbeitet und vom Player nach außen scannt.

Ich verwende eine Variation des Scanline-Algorithmus, um genau das gleiche Problem zu lösen. Ich begann damit, die drei Dreieckspunkte nach ihrer Höhe zu sortieren. Ich überprüfe dann grundsätzlich, ob zwei Kanten links oder rechts sind. Für die Seite mit zwei Kanten müssen Sie die Zeile markieren, in der Sie ändern, welche Kante Ihre Zeilen begrenzt. Für die Seite mit einer Kante können Sie diese einfach immer verwenden.

Dann weiß ich für jede Zeile, welche zwei Kanten sie begrenzen, und ich kann die oberen und unteren Grenzen in x-Richtung berechnen. Es klingt ziemlich kompliziert, aber es reduziert sich auf nur wenige Codezeilen. Stellen Sie sicher, dass Sie den Sonderfall behandeln, bei dem eine Kante vollständig horizontal ist!

Wie wäre es, einen Spaltenbereich für jede Zeile im Dreieck beizubehalten? Sie können die Min- und Max-Spalte für jede Zeile festlegen, in der sich jeder Punkt befindet und in der jede Dreieckslinie eine horizontale Zeilentrennlinie kreuzt.

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]);
    }
}

Ausgabe:

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

In der Roguelike-Community gibt es einige Algorithmen, die sich mit FOV / LOS / Beleuchtung in einer kachelbasierten Welt befassen.

Vielleicht finden Sie auf dieser Seite etwas, mit dem Sie Ihr Problem lösen können: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Insbesondere "Zulässiges Sichtfeld" ist möglicherweise am besten für Ihre Situation geeignet.