Raytracing (LOS) на трехмерных шестигранных картах плитки

Question

Привет,

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

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

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

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

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

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

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

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

Answer 1

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

Таким образом, вам необходимо определить функцию для карты из Cordesian Coornates к клеткам индексов. Это просто, если немного сложно. Во-первых, решить, 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) простая декартовая система координат с регулярными сложенными блоками. Теперь Rayfacing становится гораздо более простым и менее ошибками.