Трассировка лучей (ЛОС) на 3D подобных шестнадцатеричному числу картах мозаики
Поздравления,
Я работаю над игровым проектом, который использует 3D вариант шестиугольных карт мозаики. Мозаики являются на самом деле кубами, не шестнадцатеричными числами, но размечаются точно так же, как шестнадцатеричные числа (потому что квадрат может быть превращен к кубу для экстраполирования от 2D до 3D, но нет никакой 3D версии шестнадцатеричного числа). Вместо подробного описания, здесь идет пример 4x4x4 карта:
(Я выделил произвольную (зеленую) мозаику и ее смежные мозаики (желтые), чтобы помочь описать, как все это, как предполагается, работает; но функции смежности не являются проблемой, это уже решено.)
У меня есть тип структуры для представления мозаик, и карты представлены как 3D массив мозаик (перенесенный в a Map класс для добавления некоторых служебных методов но это не очень релевантно). Каждая мозаика, как предполагается, представляет совершенно кубическое пространство, и они - все точно тот же размер. Кроме того, смещение между смежными "строками" является точно половиной размера мозаики.
Это - достаточно контекста; мой вопрос:
Учитывая координаты двух точек A и B, как я могу генерировать список мозаик (или, скорее их координаты) что прямая линия между A и B пересекся бы?
Это позже использовалось бы во множестве целей, таких как определение Угла обзора, законности пути заряда, и так далее.
BTW, это может быть полезно: мои карты используют (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 ответа
Пока не появится один из умных помощников, вот мое глупое решение. Я объясню это в 2D, потому что это упрощает объяснение, но достаточно легко обобщить на 3D. Я думаю, что любая попытка работать с этим полностью в пространстве индекса ячеек обречена на провал (хотя я признаю, что это именно то, что я думаю, и я надеюсь, что я ошибаюсь).
Итак, вам нужно определить функцию для отображения декартовых координат в индексы ячеек. Это просто, но немного сложно. Сначала решите, является ли точка (0,0) нижним левым углом ячейки (0,0) , центром или какой-либо другой точкой. Поскольку это упрощает объяснения, я выберу нижний левый угол. Обратите внимание, что любая точка (x, floor (y) == 0) соответствует ячейке (floor (x), 0) . Действительно, любая точка (x, even (floor (y))) отображается в ячейку (floor (x), floor (y)) .
Здесь я изобретаю логическую функцию even , которая возвращает True, если ее аргумент является четным целым числом. Я буду использовать нечетное следующее: любая точка точка (x, odd (floor (y)) сопоставляется с ячейкой (floor (x-0.5), этаж (у)) .
Теперь у вас есть основы рецепта определения прямой видимости.
Вам также понадобится функция для сопоставления из ячейки (m, n). назад к точке в декартовом пространстве. Это должно быть просто, если вы решили, где находится источник.
Теперь, если я не потерял некоторые скобки, я думаю, вы уже в пути. Вам нужно:
- решить, где в
ячейке (0,0)вы разместитеточку (0,0); и соответствующим образом отрегулируйте функцию; - решите, куда попадают точки вдоль границ ячеек; и
- обобщить это на 3 измерения.
В зависимости от размера игрового поля вы можете сохранить декартовы координаты границ ячеек в таблице поиска (или другой структуре данных), что, вероятно, ускорит процесс.
Возможно, вам удастся избежать всей сложной математики, если вы посмотрите на свою задачу с другой стороны:
Я вижу, что вы только сдвигаете свои блоки (поочередно) по первой оси на половину размера блока. Если вы разделите блоки по этой оси, приведенный выше пример станет (со сдвигами) простой декартовой системой координат (9x4x4) с регулярными составными блоками. Теперь трассировка лучей становится намного проще и менее подверженной ошибкам.