Trouver quelles tuiles sont intersectées par une ligne, sans les parcourir toutes ou en sauter aucune

10

Je regarde ce problème depuis quelques jours maintenant. J'ai truqué ce graphique pour m'aider à visualiser le problème: entrez la description de l'image ici (à partir du graphique, nous savons que la ligne intersecte [1, 1], [1, 2], [2, 2], [2, 3], se terminant par [ 3,3])

Je veux avancer le long de la ligne jusqu'à chaque espace de grille et vérifier si le matériau de l'espace de grille est solide. Je sens que je connais déjà les mathématiques impliquées, mais je n'ai pas encore pu les enchaîner. J'utilise ceci pour tester la ligne de vue et éliminer les nœuds après qu'un chemin a été trouvé via mes algorithmes de recherche de chemin - mes agents ne peuvent pas voir à travers un bloc solide, donc ils ne peuvent pas passer à travers un, donc le nœud n'est pas éliminé du chemin parce qu'il est nécessaire pour naviguer dans un coin.

J'ai donc besoin d'un algorithme qui se déplacera le long de la ligne jusqu'à chaque espace de grille qu'il intersecte. Des idées?

J'ai jeté un coup d'œil à de nombreux algorithmes courants, comme celui de Bresenham, et celui qui passe à des intervalles prédéfinis le long de la ligne (malheureusement, cette méthode saute les tuiles si elles se croisent avec un coin plus petit que la taille du pas).

Je remplis maintenant mon tableau blanc avec une masse de fonctions floor () et ceil () - mais cela devient trop compliqué et je crains que cela ne provoque un ralentissement.

Suds
la source
Vous savez déjà comment tester l'intersection réelle de la boîte de ligne, non? Je demande simplement, car cela est pertinent pour la réponse.
TravisG
doublon possible de Comment généraliser l'algorithme de ligne de Bresenham aux points de terminaison à virgule flottante? (la question ne concerne pas réellement Bresenham)
sam hocevar

Réponses:

6

Si vous connaissez le bloc de départ (vous connaissez le point X et vous n'incluez pas le bloc [0,1] dans la liste des blocs, donc je suppose que vous connaissez également le bloc de départ), je pense que vous devriez sûrement utiliser l'algorithme de Bresenham. Vous avez écrit, vous l'avez regardé.

C'est un algorithme adapté à ce problème. Il peut également être écrit d'une manière, il ne calcule qu'avec des entiers. Vous pouvez trouver de nombreuses implémentations sur le Web.

ÉDITER:

Je suis désolé, je n'ai pas réalisé que Bresenham ne trouverait pas tous les blocs. J'ai donc trouvé une meilleure solution . Il y a aussi du code écrit en C ++, mais je pense que cela ne devrait pas être difficile à comprendre :)

zacharmarz
la source
1
La raison pour laquelle j'ai regardé l'algorithme de Bresenham était uniquement à cause de l'image sur Wikipedia. ( en.wikipedia.org/wiki/File:Bresenham.svg ) Vous pouvez voir que la ligne intercepte quelques carrés non ombrés, quoique à peine. J'ai besoin de quelque chose qui détecte chaque tuile, quelle que soit la taille de la tranche. Edit: Il semble que j'ai de toute façon mal compris le bresenham. J'ai besoin de l'inverser - j'ai le premier et le dernier point, et j'ai besoin des tuiles qu'il intersecte - plutôt que la ligne qui serait la meilleure pour tracer.
Suds
@JustSuds: Vérifiez la mise à jour dans le post.
zacharmarz
Hé hé! qui correspond presque directement à ce que j'ai sur mon tableau blanc! Merci, mon système est maintenant implémenté et fonctionne. :-)
Suds
Pouvez-vous supprimer la partie sur l'algorithme de Bresenham car il ne répond pas à la question? Ne vous inquiétez pas, il restera dans l'historique des modifications de votre réponse.
zenith
1

Le code de l'exemple auquel la réponse acceptée est liée nécessite un ajustement pour des lignes parfaitement diagonales. Voici une application de démonstration complète écrite avec Qt (C ++ et QML).

intersection de lignes de grille

Code C ++ pertinent:

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
la source