Jak ustalić, które komórki w siatce przecinają dany trójkąt?

Obecnie piszę symulację AI 2D, ale nie jestem całkowicie pewien, jak sprawdzić, czy pozycja agenta znajduje się w polu widzenia innego.

Obecnie moje partycjonowanie świata to proste partycjonowanie komórki-przestrzeni (siatka). Chcę użyć trójkąta do przedstawienia pola widzenia, ale jak mogę obliczyć komórki, które przecinają się z trójkątem?

Podobne do tego obrazu:

Czerwone obszary to komórki, które chcę obliczyć, sprawdzając, czy trójkąt przecina te komórki.

Z góry dziękuję.

EDYTOWAĆ:

Żeby dodać zamieszanie (a może nawet ułatwić). Każda komórka ma wektor minimalny i maksymalny, gdzie min to lewy dolny róg, a maksimum to prawy górny róg.

Oblicz trzy rogi trójkąta Fov, obróć je, aby były skierowane we właściwą stronę i tak dalej, a następnie wykonaj jedną z następujących czynności:

1) wykonaj test punkt w trójkącie dla wszystkich potencjalnych celów

2) obliczyć ramkę graniczną tego trójkąta i wykonać test punkt-trójkąt dla wszystkich potencjalnych celów w komórkach w tej ramce granicznej - będzie to bardzo prosty kod do debugowania

Podobne podejście polega na użyciu kwadratu zamiast siatki i wykonaniu na nim skrzyżowań. Jeśli dostęp do kafelków O (1) przyspiesza cię, to po prostu testowanie wszystkich komórek w granicach trójkąta fov dla wewnątrz trójkąta powinno być tak szybkie, aby było natychmiastowe. Gdy patrzysz na inne opcje, zakładam, że nie, i że O (1) faktycznie bierze ogromny koszt braku pamięci podręcznej, gdy rzucasz swoją pamięć podręczną. Możesz oczywiście spojrzeć na instrukcje pobierania wstępnego, aby opisać swój spacer po obwiedni ...

3) „zrasteryzuj” ten trójkąt i sprawdź komórki, które „maluje” - prawdopodobnie najbardziej wydajny kod, ale być może tylko nieznacznie, ponieważ spekuluję, że wszystkie są zdominowane przez czasy braków w pamięci podręcznej i zależą od tego, jak złożone są twoje komórki i jak zajmowane są komórki oni są.

Alternatywnym podejściem jest renderowanie pola widzenia na bitmapę poza ekranem, a następnie odczytanie wartości pikseli dla każdego z obiektów; nie można „odmiksować farby”, ale przy ograniczonej liczbie obiektów i ostrożnie wybierając farbę można wywnioskować, kto widział kto. Podejście to jest podobne do tego, ile gier sprawdza to, co kliknął użytkownik - rysują scenę poza ekranem, używając jednolitych kolorów dla obszarów trafień. Procesory graficzne są bardzo szybkie przy wypełnianiu trójkątów ...

Kanonicznym rozwiązaniem w programach do renderowania oprogramowania (które muszą wykonywać ten dokładny algorytm za każdym razem, gdy rasteryzują trójkąt) jest, moim zdaniem, skanowanie tego trójkąta po jednym rzędzie pikseli. Lewą i prawą krawędź każdego rzędu obliczono, przechodząc bokami trójkąta za pomocą Bresenhama , a następnie wypełniając rząd między nimi.

Przeglądam wiele szczegółów, ale to podstawowy pomysł. Jeśli polujesz na „renderowanie oprogramowania” i „rasteryzację trójkątów”, prawdopodobnie znajdziesz więcej szczegółów. To dobrze rozwiązany problem. Twoja karta graficzna robi to miliony razy w ramce.

Jeśli chcesz bardziej roguelike rozwiązania, oto jak zaimplementowałem FOV w moim. Wygląda na to, że działa dość szybko. Zasadniczo jest to prosty rzucacz cieni, pracujący na oktanie jednocześnie, skanujący na zewnątrz odtwarzacza.

Używam odmiany algorytmu skanowania linii, aby rozwiązać dokładnie ten sam problem. Zacząłem od posortowania trzech punktów trójkąta według ich wysokości. Następnie w zasadzie sprawdzam, czy dwie krawędzie są po lewej, czy po prawej stronie. Po stronie z dwiema krawędziami musisz zaznaczyć rząd, w którym zmienisz, która krawędź ogranicza twoje rzędy. Po stronie z jedną krawędzią zawsze możesz tego użyć.

Zatem dla każdego wiersza wiem, które dwie krawędzie go ograniczają, i mogę obliczyć górną i dolną granicę w kierunku x. Brzmi dość skomplikowanie, ale ogranicza się do zaledwie kilku wierszy kodu. Upewnij się, że zajmujesz się specjalnym futerałem, w którym jedna krawędź jest całkowicie pozioma!

Co powiesz na utrzymanie zakresu kolumn dla każdego wiersza w trójkącie? Możesz ustawić minimalną i maksymalną kolumnę dla każdego wiersza, w którym znajduje się każdy punkt i gdzie każda linia trójkąta przecina poziomą linię oddzielającą wiersze.

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

Wynik:

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

W społeczności roguelike wykonano prace nad algorytmem, które zajmują się światłami FOV / LOS / oświetleniem w świecie opartym na kafelkach.

Być może na tej stronie znajdziesz coś, co pomoże rozwiązać Twój problem: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

W szczególności „Permovive FOV” może być najbardziej odpowiedni w twojej sytuacji.