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

10

Ich habe dieses Problem jetzt seit ein paar Tagen angestarrt. Ich habe diese Grafik zusammengestellt, um das Problem besser veranschaulichen zu können: Geben Sie hier die Bildbeschreibung ein (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.

Schaum
quelle
Sie wissen bereits, wie Sie den tatsächlichen Linienkastenschnittpunkt testen können, oder? Fragen Sie einfach, denn dies ist für die Antwort relevant.
TravisG

Antworten:

6

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

zacharmarz
quelle
1
Der Grund, warum ich über den Bresenham-Algorithmus hinausgeschaut habe, war nur das Bild auf Wikipedia. ( en.wikipedia.org/wiki/File:Bresenham.svg ) Sie können sehen, dass die Linie einige nicht schattierte Quadrate abfängt, wenn auch kaum. Ich brauche etwas, das jede Kachel erkennt, unabhängig davon, wie unendlich klein die Scheibe ist. Edit: Es scheint, dass ich Bresenhams sowieso missverstanden habe. Ich muss es umkehren - ich habe den ersten und letzten Punkt und ich brauche die Kacheln, die es schneidet - und nicht die Linie, die am besten zu zeichnen wäre.
Suds
@ JustSuds: In der Post nach Updates suchen.
Zacharmarz
Hey hey! das passt fast direkt zu dem, was ich auf meinem Whiteboard habe! Danke, mein System ist jetzt implementiert und funktioniert. :-)
Suds
Können Sie den Teil über Bresenhams Algorithmus entfernen, da er die Frage nicht beantwortet? Keine Sorge, es bleibt im Bearbeitungsverlauf Ihrer Antwort.
Zenit
1

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.

Gitterlinienschnittpunkt

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