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

Привет,

Я работаю над игровым проектом, в котором используется трехмерный вариант шестиугольных карт. Плитки на самом деле являются кубами, а не гексами, но выкладываются точно так же, как гексы (потому что квадрат можно превратить в куб для экстраполяции из 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; но мне не нужен конкретный код, только алгоритм для решения странной геометрической / математической задачи. Я несколько дней пытался решить это безрезультатно; и попытка нарисовать все это на бумаге, чтобы "визуализировать" это тоже не помогло:( .

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

Источник

2 ответа

Решение

Пока не появится один из умных 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 измерения.

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

Источник

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

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

Источник
Другие вопросы по тегам