Encontrar quais peças são cruzadas por uma linha, sem passar por todas elas ou pular nenhuma

10

Estou encarando esse problema há alguns dias. Eu montei esse gráfico para me ajudar a visualizar o problema: insira a descrição da imagem aqui (no gráfico, sabemos que a linha cruza [1, 1], [1, 2], [2, 2], [2, 3], terminando em [ 3,3])

Quero avançar ao longo da linha para cada espaço da grade e verificar se o material do espaço da grade é sólido. Sinto que já conheço a matemática envolvida, mas ainda não fui capaz de entender. Estou usando isso para testar a linha de visão e eliminar nós depois que um caminho é encontrado através dos meus algoritmos de busca de caminhos - meus agentes não podem ver através de um bloco sólido, portanto, eles não podem se mover através de um, portanto o nó não é eliminado do caminho porque é necessário para navegar em um canto.

Então, eu preciso de um algoritmo que vá ao longo da linha para cada espaço da grade que cruzar. Alguma ideia?

Examinei muitos algoritmos comuns, como o de Bresenham, e um que pisa em intervalos predefinidos ao longo da linha (infelizmente, esse método ignora blocos se eles estiverem se cruzando com uma cunha menor do que o tamanho da etapa).

Agora estou preenchendo meu quadro branco com uma grande quantidade de funções floor () e ceil () - mas está ficando muito complicado e tenho medo de que possa causar uma desaceleração.

Suds
fonte
Você já sabe como testar a interseção de caixa de linha real, certo? Basta perguntar, porque isso é relevante para a resposta.
TravisG
possível duplicata de Como generalizo o algoritmo de linha de Bresenham para pontos finais de ponto flutuante? (a questão não é realmente sobre Bresenham)
Sam Hocevar

Respostas:

6

Se você conhece o bloco inicial (você conhece o ponto X e não inclui o bloco [0,1] na lista de blocos, então suponho que também conheça o bloco inicial), acho que certamente deve usar o algoritmo de Bresenham. Você escreveu, você olhou para ele.

É um algoritmo adequado para esse problema. Também pode ser escrito de uma maneira, calcula apenas com números inteiros. Você pode encontrar muitas implementações disponíveis na web.

EDITAR:

Sinto muito, não percebi que Bresenham não encontrará todos os blocos. Então eu encontrei uma solução melhor . Também há código escrito em C ++, mas acho que não deve ser difícil de entender :)

zacharmarz
fonte
1
A razão pela qual olhei além do algoritmo de Bresenham foi puramente por causa da imagem na Wikipedia. ( pt.wikipedia.org/wiki/File:Bresenham.svg ) Você pode ver que a linha intercepta alguns quadrados não sombreados, embora apenas um pouco. Preciso de algo que detecte todos os blocos, independentemente de quão infinitamente pequena seja a fatia. Edit: Parece que eu entendi mal Bresenham de qualquer maneira. Preciso invertê-lo - tenho o primeiro e o último ponto e preciso das peças que se cruzam - em vez da linha que seria melhor traçar.
Suds
@JustSuds: verifique se há atualizações no post.
Zacharmarz 23/11
Ei ei! que corresponde quase diretamente ao que tenho no quadro branco! Obrigado, meu sistema está agora implementado e funcionando. :-)
Suds
Você pode remover a parte do algoritmo de Bresenham por não responder à pergunta? Não se preocupe, ele permanecerá no histórico de edições da sua resposta.
zenith
1

O código no exemplo ao qual a resposta aceita se vincula precisa de algum ajuste para linhas perfeitamente diagonais. Aqui está um aplicativo de demonstração completo escrito com Qt (C ++ e QML).

interseção da linha de grade

Código C ++ relevante:

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
fonte