Encontrar qué mosaicos están intersectados por una línea, sin recorrerlos todos ni saltarse ninguno

He estado mirando este problema por unos días. Arreglé este gráfico para ayudarme a visualizar el problema: (del gráfico, sabemos que la línea interseca [1, 1], [1, 2], [2, 2], [2, 3], terminando en [ 3,3])

Quiero avanzar a lo largo de la línea hasta cada espacio de la cuadrícula y verificar si el material del espacio de la cuadrícula es sólido. Siento que ya conozco las matemáticas involucradas, pero aún no he podido unirlas. Estoy usando esto para probar la línea de visión y eliminar nodos después de encontrar una ruta a través de mis algoritmos de búsqueda de ruta: mis agentes no pueden ver a través de un bloque sólido, por lo tanto, no pueden moverse a través de uno, por lo tanto, el nodo no se elimina de la ruta porque Se requiere para navegar una esquina.

Entonces, necesito un algoritmo que avance a lo largo de la línea hacia cada espacio de la cuadrícula que se cruza. ¿Algunas ideas?

He echado un vistazo a muchos algoritmos comunes, como el de Bresenham, y uno que avanza a intervalos predefinidos a lo largo de la línea (desafortunadamente, este método omite los mosaicos si se cruzan con una cuña más pequeña que el tamaño del paso).

Ahora estoy poblando mi pizarra con una masa de funciones floor () y ceil (), pero se está volviendo demasiado complicada y me temo que podría causar una desaceleración.

Si conoce el bloque inicial (conoce el punto X y no incluye el bloque [0,1] en la lista de bloques, así que supongo que también conoce el bloque inicial), creo que seguramente debería usar el algoritmo de Bresenham. Escribiste, lo miraste.

Es un algoritmo adecuado para este problema. También se puede escribir de una manera, solo se calcula con números enteros. Puede encontrar muchas implementaciones en la web.

EDITAR:

Lo siento, no me he dado cuenta de que Bresenham no encontrará todos los bloques. Entonces encontré una mejor solución . También hay código escrito en C ++, pero creo que no debería ser difícil de entender :)

El código en el ejemplo al que se vincula la respuesta aceptada necesita algún ajuste para líneas perfectamente diagonales. Aquí hay una aplicación de demostración completa escrita con Qt (C ++ y QML).

Código relevante de 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();
}