Finden, welche Kacheln von einer Linie geschnitten werden, ohne sie alle zu durchlaufen oder zu überspringen

Ich habe dieses Problem jetzt seit ein paar Tagen angestarrt. Ich habe diese Grafik zusammengestellt, um das Problem besser veranschaulichen zu können: (Aus der Grafik wissen wir, dass sich die Linie schneidet [1, 1], [1, 2], [2, 2], [2, 3] und endet mit [ 3,3])

Ich möchte entlang der Linie zu jedem Gitterraum gehen und prüfen, ob das Material des Gitterraums fest ist. Ich habe das Gefühl, dass ich die Mathematik bereits kenne, aber ich konnte sie noch nicht aneinander reihen. Ich verwende dies, um die Sichtlinie zu testen und Knoten zu entfernen, nachdem ein Pfad über meine Pfadfindungsalgorithmen gefunden wurde. Meine Agenten können nicht durch einen festen Block sehen, daher können sie sich nicht durch einen bewegen, daher wird der Knoten nicht aus dem Pfad entfernt, weil er ist erforderlich, um eine Ecke zu navigieren.

Ich brauche also einen Algorithmus, der entlang der Linie zu jedem Gitterraum geht, den er schneidet. Irgendwelche Ideen?

Ich habe mir viele gängige Algorithmen wie den von Bresenham angesehen, die in vordefinierten Intervallen entlang der Linie ausgeführt werden (bei dieser Methode werden leider Kacheln übersprungen, wenn sie sich mit einem kleineren Keil als der Schrittgröße schneiden).

Ich fülle mein Whiteboard jetzt mit einer Vielzahl von Funktionen für Boden () und Decke () - aber es wird zu kompliziert und ich befürchte, es könnte zu einer Verlangsamung führen.

Wenn Sie den Startblock kennen (Sie kennen Punkt X und Sie nehmen Block [0,1] nicht in die Blockliste auf, also kennen Sie wahrscheinlich auch den Startblock), sollten Sie sicher den Bresenham-Algorithmus verwenden. Du hast geschrieben, du hast es angeschaut.

Es ist ein geeigneter Algorithmus für dieses Problem. Es kann auch so geschrieben werden, dass es nur mit ganzen Zahlen berechnet. Im Internet finden Sie viele Implementierungen.

BEARBEITEN:

Es tut mir leid, ich habe nicht bemerkt, dass Bresenham nicht alle Blöcke findet. Also habe ich eine bessere Lösung gefunden . Es gibt auch Code in C ++, aber ich denke, es sollte nicht schwer zu verstehen sein :)

Der Code im Beispiel, auf den die akzeptierte Antwort verweist, muss für perfekt diagonale Linien angepasst werden. Hier ist eine vollständige Demo-Anwendung, die mit Qt (C ++ und QML) geschrieben wurde.

Relevanter C ++ - Code:

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