Raytracing (LOS) em mapas de azulejos em forma de hexadecipal 3D

Question

Saudações,

Estou trabalhando em um projeto de jogo que usa uma variante 3D de mapas de azulejos hexagonais. Os ladrilhos são na verdade cubos, não hexáticos, mas são dispostos como hexágonos (porque um quadrado pode ser transformado em um cubo para extrapolar de 2D para 3D, mas não há versão 3D de um hexadecimal). Em vez de uma descrição detalhada, aqui vai um exemplo de um mapa 4x4x4:

(Destacei um ladrilho arbitrário (verde) e seus ladrilhos adjacentes (amarelos) para ajudar a descrever como tudo deve funcionar; mas as funções de adjacência são não A questão, que já está resolvida.)

Eu tenho um tipo de estrutura para representar ladrilhos, e os mapas são representados como uma matriz 3D de ladrilhos (embrulhada em um Map classe para adicionar alguns métodos de utilidade, mas isso não é muito relevante). Cada ladrilho deve representar um perfeitamente espaço cúbico, e eles são todos exatamente o mesmo tamanho. Além disso, o deslocamento entre "linhas" adjacentes é exatamente metade do tamanho de um ladrilho.

Esse é o contexto suficiente; minha pergunta é:
Dadas as coordenadas de dois pontos A e B, como posso gerar uma lista dos ladrilhos (ou melhor, suas coordenadas) que uma linha reta entre A e B cruzaria?

Isso mais tarde seria usado para uma variedade de propósitos, como determinar a legalidade do caminho da linha de visão, e assim por diante.

BTW, isso pode ser útil: meus mapas usam o (0,0,0) como uma posição de referência. O 'salto' do mapa pode ser definido como compensando cada ladrilho ((y+z) mod 2) * tileSize/2.0 à direita, a partir da posição que ele teria em um sistema cartesiano "sã". Para as linhas não jagadas, isso produz 0; para linhas onde (y+z) mod 2 é 1, ele produz 0,5 ladrilhos.

Estou trabalhando no C#4 direcionando o .NET Framework 4.0; Mas eu realmente não preciso de código específico, apenas o algoritmo para resolver o estranho problema geométrico/matemático. Eu tenho tentado há vários dias resolver isso sem sucesso; E tentando desenhar a coisa toda no papel para "visualizar" também não ajudou :(.

Agradecemos antecipadamente por qualquer resposta

Answer 1

Até que um dos Soers inteligentes apareça, aqui está minha solução idiota. Vou explicar em 2D, que facilita a explicação, mas será generalizada para 3D com bastante facilidade. Eu acho que qualquer tentativa de tentar trabalhar isso inteiramente no espaço do índice de células está fadado ao fracasso (embora eu admita que seja exatamente o que eu acho e estou ansioso por ser provado errado).

Portanto, você precisa definir uma função para mapear de coordenadas cartesianas para índices celulares. Isso é direto, se um pouco complicado. Primeiro, decida se point(0,0) é o canto inferior esquerdo de cell(0,0) ou o centro, ou algum outro ponto. Como facilita as explicações, vou com o canto inferior esquerdo. Observe isso point(x,floor(y)==0) mapeia para cell(floor(x),0). De fato, qualquer point(x,even(floor(y))) mapeia para cell(floor(x),floor(y)).

Aqui, invento a função booleana even que retorna verdadeiro se seu argumento for um número inteiro. Vou usar odd Próximo: qualquer ponto point(x,odd(floor(y)) mapeia para cell(floor(x-0.5),floor(y)).

Agora você tem o básico da receita para determinar as linhas de visão.

Você também precisará de uma função para mapear de cell(m,n) de volta a um ponto no espaço cartesiano. Isso deve ser simples depois de decidir onde está a origem.

Agora, a menos que eu tenha perdido alguns colchetes, acho que você está a caminho. Você precisará:

• decidir onde entrar cell(0,0) sua posição point(0,0); e ajustar a função de acordo;
• Decida onde os pontos ao longo dos limites das células caem; e
• generalize isso em 3 dimensões.

Dependendo do tamanho do campo de jogo, você pode armazenar as coordenadas cartesianas dos limites das células em uma tabela de pesquisa (ou outra estrutura de dados), o que provavelmente aceleraria as coisas.

Answer 2

Talvez você possa evitar toda a matemática complexa se olhar para o seu problema de outra maneira:

Vejo que você apenas muda seus blocos (alternando) ao longo do primeiro eixo pela metade do tamanho do bloco. Se você dividir seus blocos ao longo deste eixo, o exemplo acima se tornará (com turnos) um sistema de coordenadas cartesianas simples (9x4x4) com blocos empilhados regulares. Agora, fazer o Raytracing se torna muito mais simples e menos propenso a erros.