El trazado de rayos (Los) en 3D hexagonal como mapas de azulejo

Question

Saludos,

Estoy trabajando en un proyecto de juego que utiliza una variante de mapas 3D hexagonales baldosas. Los azulejos son en realidad cubos, no hexágonos, pero se presentan como hexágonos (debido a un cuadrado se puede dar vuelta a un cubo para extrapolar de 2D a 3D, pero no hay una versión en 3D de un hexágono). En lugar de una descripción detallada, aquí va un ejemplo de un mapa 4x4x4:

(I han puesto de relieve una baldosa arbitraria (verde) y sus baldosas adyacentes (amarillo) para ayudar a describir cómo todo el asunto se supone que funciona, pero las funciones de adyacencia son no el tema , eso ya está resuelto.)

Tengo un tipo de estructura para representar los azulejos, y los mapas se representan como una matriz 3D de azulejos (envueltos en una clase Map añadir algunos métodos de utilidad, pero eso no es muy relevante). Cada baldosa se supone que representa un perfectamente espacio cúbico, y todos ellos son exactamente del mismo tamaño. Además, el desplazamiento entre filas "" adyacentes se exactamente la mitad del tamaño de una baldosa.

Eso es suficiente contexto; mi pregunta es:
Teniendo en cuenta las coordenadas de dos puntos y A B, ¿cómo puedo generar una lista de las baldosas (o, mejor dicho, sus coordenadas) que una línea recta entre A y B cruzaría?

que más tarde se pueden utilizar para una variedad de propósitos, tales como la determinación de la línea de visión directa, cargo ruta legalidad, y así sucesivamente.

Por cierto, esto puede ser útil: mis mapas utilizan el (0,0,0) como posición de referencia. El 'entrecorte' del mapa se puede definir como la compensación de cada ((y+z) mod 2) * tileSize/2.0 baldosas a la derecha de la posición que tendría en un sistema cartesiano "sano". Para las filas no dentadas, que los rendimientos de 0; para las filas donde (y+z) mod 2 es 1, produce 0,5 azulejos.

Estoy trabajando en C # 4 de orientación del .Net Framework 4.0; pero realmente no necesita código específico, sólo el algoritmo para resolver el problema geométrico raro / matemática. He estado tratando durante varios días para resolver esto en vano; y tratando de sacar todo el asunto en el papel de "visualizar" no ayudó tampoco :(.

Gracias de antemano por cualquier respuesta

Answer 1

Hasta que uno de los Soers inteligentes aparece, aquí está mi solución tonta. Voy a explicar en 2D cos' que hace que sea más fácil de explicar, pero va a generalizar a 3D con bastante facilidad. Creo que cualquier intento de tratar de resolver esto por completo en el espacio índice de células está destinado al fracaso (aunque voy a admitir que es justo lo que pienso y espero estar equivocado demostrado).

Así que hay que definir una función para mapear de coordenadas cartesianas a índices de glóbulos. Esto es sencillo, aunque un poco complicado. En primer lugar, debe decidir si point(0,0) es la esquina inferior izquierda de cell(0,0) o en el centro, o en algún otro punto. Ya que hace más fácil las explicaciones, voy a ir con la esquina inferior izquierda. Observe que cualquier point(x,floor(y)==0) asigna a cell(floor(x),0). De hecho, cualquier point(x,even(floor(y))) asigna a cell(floor(x),floor(y)).

A continuación, invento el even función booleana que devuelve verdadero si su argumento es un entero par. Voy a usar odd siguiente:. point(x,odd(floor(y)) cualquier punto se asigna a cell(floor(x-0.5),floor(y))

Ahora usted tiene los fundamentos de la receta para la determinación de las líneas de visión.

También tendrá una función para mapear desde la parte posterior cell(m,n) a un punto en el espacio cartesiano. Eso debería ser sencillo una vez que haya decidido dónde se encuentra el origen.

Ahora, a menos que haya extraviado algunos soportes, creo que está en su camino. Tendrá que:

• decidir en qué posición se cell(0,0) point(0,0); y ajustar la función en consecuencia;
• decidir dónde puntos a lo largo de los límites de las celdas caen; y
• generalizar esto en 3 dimensiones.

Dependiendo del tamaño del campo de juego se podría almacenar las coordenadas cartesianas de los límites de las celdas en una tabla de búsqueda (u otra estructura de datos), lo que probablemente acelerar las cosas.

Answer 2

Tal vez usted puede evitar todo el complejo de matemáticas si nos fijamos en el problema de otra manera:

Veo que sólo cambia sus bloques (alterna) a lo largo del primer eje a la mitad el tamaño de bloque. Si se divide de seguridad de sus bloques a lo largo de este eje el ejemplo anterior se convertirá (con cambios) un (9x4x4) el simple sistema de coordenadas cartesianas con bloques apilados regulares. Ahora hacer el trazado de rayos se hace mucho más simple y menos propenso a errores.