Raytracing (LoS) на трехмерных гексоподобных картах плиток

Question

Привет,

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

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

У меня есть тип структуры для представления плиток, а карты представлены в виде трехмерного массива плиток (в класс 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

Пока не появится один из умных SO, вот мое глупое решение. Я объясню это в 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) простой декартовой системой координат с регулярными сложенными блоками. Теперь трассировка лучей становится намного проще и менее подвержена ошибкам.