Znalezienie, które kafelki przecinają linia, bez zapętlania ich wszystkich i pomijania


10

Patrzę na ten problem od kilku dni. Przygotowałem tę grafikę, aby pomóc mi w wizualizacji problemu: wprowadź opis zdjęcia tutaj (z wykresu wiemy, że linia przecina [1, 1], [1, 2], [2, 2], [2, 3], kończąc na [ 3,3])

Chcę przejść wzdłuż linii do każdej przestrzeni siatki i sprawdzić, czy materiał przestrzeni siatki jest solidny. Wydaje mi się, że już znam matematykę, ale nie byłem jeszcze w stanie jej połączyć. Używam tego do testowania linii wzroku i eliminowania węzłów po znalezieniu ścieżki za pomocą moich algorytmów odnajdywania ścieżek - moi agenci nie widzą stałego bloku, dlatego nie mogą przejść przez jeden, dlatego węzeł nie jest eliminowany ze ścieżki, ponieważ jest wymagany do nawigacji w rogu.

Potrzebuję więc algorytmu, który będzie przechodził wzdłuż linii do każdej przecinającej się przestrzeni siatki. Jakieś pomysły?

Przyjrzałem się wielu powszechnym algorytmom, takim jak Bresenham, i takim, który kroczy w określonych odstępach czasu wzdłuż linii (niestety ta metoda pomija kafelki, jeśli przecinają one mniejszy klin niż rozmiar kroku).

Zapełniam teraz moją tablicę masą funkcji floor () i ceil () - ale robi się to zbyt skomplikowane i obawiam się, że może to spowodować spowolnienie.


Wiesz już, jak przetestować rzeczywiste przecięcie pola z liniami, prawda? Tylko pytam, bo ma to związek z odpowiedzią.
TravisG,

możliwy duplikat Jak uogólnić algorytm liniowy Bresenhama na zmiennoprzecinkowe punkty końcowe? (pytanie tak naprawdę nie dotyczy Bresenhama)
sam hocevar

Odpowiedzi:


6

Jeśli znasz blok początkowy (znasz punkt X i nie umieścisz bloku [0,1] na liście bloków, więc przypuszczam, że znasz także blok początkowy), myślę, że powinieneś na pewno użyć algorytmu Bresenhama. Napisałeś, spojrzałeś na to.

Jest odpowiedni algorytm dla tego problemu. Można go również napisać w pewien sposób, oblicza tylko liczby całkowite. W sieci można znaleźć wiele implementacji.

EDYTOWAĆ:

Przepraszam, nie zdawałem sobie sprawy, że Bresenham nie znajdzie wszystkich bloków. Więc znalazłem lepsze rozwiązanie . Jest także kod napisany w C ++, ale myślę, że nie powinno być trudno zrozumieć :)


1
Powodem, dla którego obejrzałem algorytm Bresenham, był wyłącznie obraz z Wikipedii. ( en.wikipedia.org/wiki/File:Bresenham.svg ) Widać, że linia przechwytuje niektóre niecieniowane kwadraty, choć ledwo. Potrzebuję czegoś, co wykryje każdy kafelek, niezależnie od tego, jak nieskończenie mały jest ten kawałek. Edycja: Wygląda na to, że i tak źle zrozumiałem bresenhama. Muszę to odwrócić - mam pierwszy i ostatni punkt i potrzebuję przecinających się kafelków - zamiast linii, którą najlepiej byłoby narysować.
Suds

@JustSuds: Sprawdź aktualizację w poście.
zacharmarz

Hej hej! który prawie bezpośrednio pasuje do tego, co mam na mojej tablicy! Dzięki, mój system jest teraz zaimplementowany i działa. :-)
Suds

Czy możesz usunąć część dotyczącą algorytmu Bresenhama, ponieważ nie odpowiada na pytanie? Nie martw się, pozostanie w historii edycji odpowiedzi.
zenith,

1

Kod w przykładzie, do którego prowadzi zaakceptowana odpowiedź, wymaga pewnej korekty w celu uzyskania idealnie ukośnych linii. Oto kompletna aplikacja demonstracyjna napisana w Qt (C ++ i QML).

przecięcie linii siatki

Odpowiedni kod C ++:

void rayCast()
{
    if (!isComponentComplete())
        return;

    mTiles.clear();
    mTiles.fill(QColor::fromRgb(255, 222, 173), mSizeInTiles.width() * mSizeInTiles.height());

    const QPoint startTile = startTilePos();
    const QPoint endTile = endTilePos();
    // http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html
    int x0 = startTile.x();
    int y0 = startTile.y();
    int x1 = endTile.x();
    int y1 = endTile.y();

    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int x = x0;
    int y = y0;
    int n = 1 + dx + dy;
    int x_inc = (x1 > x0) ? 1 : -1;
    int y_inc = (y1 > y0) ? 1 : -1;
    int error = dx - dy;
    dx *= 2;
    dy *= 2;

    for (; n > 0; --n)
    {
        visit(x, y);

        if (error > 0)
        {
            x += x_inc;
            error -= dy;
        }
        else if (error < 0)
        {
            y += y_inc;
            error += dx;
        }
        else if (error == 0) {
            // Ensure that perfectly diagonal lines don't take up more tiles than necessary.
            // http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html?showComment=1281448902099#c3785285092830049685
            x += x_inc;
            y += y_inc;
            error -= dy;
            error += dx;
            --n;
        }
    }

    update();
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.