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

Patrzę na ten problem od kilku dni. Przygotowałem tę grafikę, aby pomóc mi w wizualizacji problemu: (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.

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ć :)

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).

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