Raytracing (LOS) на 3D шестигранная типа плитки карты

Question

Привета,

Я работаю над игровым проектом, который использует 3D вариант шестиугольных карт плитки. Плитки на самом деле кубики, а не гексы, но выложены так же, как гексы (потому что квадрат можно превратить в куб, чтобы экстраполировать с 2D на 3D, но нет трехмерной версии гекса). Вместо подробного описания, здесь идет пример 4x4x4 карты:

(я выделенный произвольная плитка (зеленый) и прилегающей к нему плитка (желтой), чтобы помочь описать, как все это является должно работать, но функция смежности является не проблему, которая уже решена)

у меня есть тип структуры для представления плитки и карты представлены в виде 3D-массива плитки (завернутом в Map класса. добавить некоторые полезные методы, но это не очень важно). Каждая плитка должна представлять собой отлично кубическое пространство, и все они точно такого же размера. Кроме того, смещение между соседними «рядами» равно точно половина размера плитки.

Этого достаточно; мой вопрос:
Учитывая координаты двух точек A и B, как я могу сгенерировать список плиток (или, точнее, их координат), чтобы пересечь прямую линию между A и B?

Это позднее будет использоваться для самых разных целей, таких как определение прямой видимости, законности зарядки и т. Д.

Кстати, это может быть полезно: на моих картах используется (0,0,0) в качестве эталонного положения. «Зубчатость» карты может быть определена как смещение каждой плитки ((y+z) mod 2) * tileSize/2.0 справа от положения, которое она имела бы на «нормальной» декартовой системе. Для строк без зубьев, которые дают 0; для строк, где (y+z) mod 2 равен 1, он дает 0,5 плитки.

Я работаю над C# 4, нацеленным на .Net Framework 4.0; но мне не нужен конкретный код, просто алгоритм для решения странной геометрической/математической проблемы. Я пытался в течение нескольких дней решить это безрезультатно; и пытается сделать все это на бумаге «визуализировать» это не помогло :(.

Заранее спасибо за любой ответ

Answer 1

До одного из умного SOers поворачивает вверх, вот мое немым решение. Я объясню это в 2D, потому что это упрощает объяснение, но он будет достаточно обобщен для 3D. Я думаю, что любая попытка попытаться полностью работать в пространстве сотовых индексов обречена на провал (хотя я признаю, что это только то, что я думаю, и я с нетерпением жду того, чтобы быть доказанным неправильно).

Таким образом, вам нужно определить функцию для отображения из декартовых координат в индексы ячеек. Это просто, если немного сложно. Сначала определите, point(0,0) нижний левый угол cell(0,0) или центр, или какой-либо другой момент. Поскольку это упрощает объяснения, я пойду с нижним левым углом. Обратите внимание, что любой point(x,floor(y)==0) соответствует cell(floor(x),0). Действительно, любой point(x,even(floor(y))) соответствует cell(floor(x),floor(y)).

Здесь я выхожу логическую функцию even, которая возвращает True, если ее аргумент является четным целым числом. Я буду использовать odd следующий: любая точка point(x,odd(floor(y)) карты до cell(floor(x-0.5),floor(y)).

Теперь у вас есть основы рецепта для определения линий обзора.

Вам также понадобится функция для отображения от cell(m,n) к точке в декартовом пространстве. Это должно быть просто, как только вы решили, где лежит происхождение.

Теперь, если я не ошибаюсь в некоторых скобках, я думаю, что вы на своем пути. Вам необходимо будет:

• решить, где находится cell(0,0) позиция point(0,0); и соответственно отрегулируйте функцию;
• решить, где падают точки вдоль границ ячейки; и
• обобщить это на 3 размера.

В зависимости от размера игрового поля вы можете хранить декартовы координаты границ ячейки в таблице поиска (или другой структуре данных), что, вероятно, ускорит процесс.

Answer 2

Возможно, вы можете избежать всех сложные математические, если вы посмотрите на вашу проблему по-другому:

Я вижу, что вы только переложить свои блоки (чередуя) вдоль первой оси на половину размера блока. Если вы разделите свои блоки вдоль этой оси, то приведенный выше пример станет (со сдвигами) простой декартовой системой координат (9x4x4) с регулярными уложенными блоками. Теперь выполнение raytracing становится намного более простым и менее подверженным ошибкам.