Введение в геометрию правильных шестиугольников на плоскости

Математика
Задание системы координат
При реализации перемещения по карте в играх последнее время стало модным использование
для точки пространства правильного шестиугольника (hex). Это и вправду решает большое количество вопросов. Например, не требует перемещения через углы многоугольника. Шести направлений для движения оказывается вполне достаточным для передачи реалистичности перемещений.

Система координат
Рис.1. Система координат
Обратим внимание на то, что для фиксации точек на карте применение столь привычной нам декартовой системы координат становится невыгодным, поскольку положение каждой отдельно взятой ячейки становится сложно идентифицировать без использования дробных значений в координатах, что утяжеляет рассчёты. Столь же нетривиальными будут рассчёты расстояний между ячейками, обсчёт действия преград при выстреле и же с ним. Таким образом, сперва наперво требуется выбрать удобную систему координат. Существенно упростил бы вычисления факт того, что перемещение на соседнюю клетку соответствовало бы сдвигу на единичное значение по одной оси координатной сетки.
Сектора
Рис.2. Сектора, образованные координатными осями
При внимательном рассмотрении вариантов для векторных направлений осей наиболее удобным мне видится тот, где угол между направлениями осей соответствует 120°. 3 координатные оси соответствуют 6 направлениям движения.
Подобная система избыточна, покуда каждую точку пространства
можно описать бесконечным множеством способов, каждый из которых становится траекторией перемещения из начала координат в точку, однако кратчайший путь описывается единственным способом проекцией на ближайшие координатные оси. Фактически мы получаем 6 секторов представляющих собой 3 пары, в каждом из которых описание точек, расположенных в них, осуществляется через 2 координатные оси, прилегающие к нему как это показано на рис.2.
Координаты точек
Рис.3. Координаты точек
При этом представлении координаты точек будут фиксироваться так, как показано на рис.3.
Преобразование координаты к нормальному виду
Нормальной, будем называть такую запись координаты, когда она описывает кратчайший путь в неё из начала координат, что соответствует проекциям на близлежащие координатные оси.

Для определения того, что координата находится в нормальном виде, можно выделить несколько свойств, присущих ей:
  • Одна из 3 координат должна быть равной 0, поскольку запись координаты в нормальном виде осуществляется через проекцию на 2 оси.
    Две другие координаты должны быть в соответствии: одна >= 0, а другая <= 0 — поскольку к каждому из секторов прилегают половины двух осей, одна из которых всегда положительная, а другая отрицательная.

    Эти свойства являются необходимыми и достаточными для того, чтобы проверить, что координата записана в нормальном виде.
    Единичный сдвиг по 3 координатам
    Рис.4. Единичный сдвиг по 3 координатам
    Прежде чем решать задачу нормирования координаты обратим внимание на следующее свойство данной системы координат: единичный сдвиг по всем 3 координатам приводит нас в ту же точку (рис. 4). Исходя из этого мы получаем преозбразование:
    (x,y,z) = (x+c,y+c,z+c), где с — константа

    Теперь для получения нормального вида записи координаты точки требуется лишь найти 2 оси, выражение через которые даст минимальное расстояние из начала координат и привести по предложенной выше формуле к требуемому виду. Нам требуется получить
    (c1,c2,c3), где c2 = 0 и c1 <= c2 <= c3,

    а это значит, что до преобразования мы имели
    c2 = c и c1+c <= c2+c <= c3+c,

    значит в ненормированной записи требуется найти такую координату, чтобы её значение располагалось между значениями 2 других и вычесть это значение из всех координат точки.
    Рассчёт расстояния между точками на плоскости
    Координаты точек заданы как кратчайший путь из начала координат в точку, а это значит, что расстояние из начала координат в точку равно
    R0 = |x| + |y| + |z|

    Разница векторов точек даёт координату, которая в нормальном виде соответствуюет расстоянию между ними.
    R = |x1-x2|+|y1-y2|+|z1-z2|

    Поиск препятствия между точками
    Теперь, когда мы обсудили общие вопросы, можно попытаться решить задачку, которая часто возникает в компьютерных играх с картой.
    Выстрел сделанный на расстоянии подразумевает возможность попадания в препятствие, которое может быть встречено на пути.
    Выстрел
    Рис.5. Поиск препятствий при выстреле
    Это ставит перед нами задачу поиска препятствия, в которое может попасть снаряд. Задача имеет в общем случае 2 подхода к решению:
    1. Поиск точек пространства, где может быть расположено препятствие, способное помешать движению снаряда и проверка их;
      Перебор всех препятствий в локации и проверка того, что они не расположены на линии огня.

      При рассмотрении данной задачи я склоняюсь к первому варианту решения, так как первое же встреченное препятствие по ходу движения снаряда, мимо которого снаряду не удалось пролететь, заканчивает решение задачи, в отличие от другого подхода.
      Таким образом нам не всегда требуется перебирать все точки и все препятствия, если мы начинаем путь от атакующего.
      Есть и другой аргумент за этот подход. Для проверки эффективности укрытия (препятствия) часто требуется знать расстояние до стрелка или жертвы.
      В первом случае оно нам в любой момент времени известно и не требует вычислений, а во втором для каждого объекта удовлетворяющего условиям препятствия, нам требуется высчитывать его удалённость от стрелка и жертвы.
      На рис.5. точкой A обозначен стрелок, а B — жертва. Серым цветом отмечены точки, в которых может быть препятствие.
      Сдвиг в клетках при прохождении по «клеточной» прямой, являющей собой перемещение снаряда, будет происходить в пропорции сдвига по координатным осям. Третья координата для решения данной задачи использоваться не будет, потому что вектор выстрела будет в нормальном виде. Поскольку выстрел начинается из середины ячейки и заканчивается в середине ячейки, результат потребует округления.
      y = y(AB) / x(AB) * x

      Итоги
      В данном обзоре мне удалось рассмотреть лишь некоторые частные моменты, встречаемые в играх с картой, что было сделано для того, чтобы продемонстрировать удобную координатную сетку.
      Отметим ещё раз, что выбор подобной системы координат сводит большую часть вычислений к арифметическим. Все координаты представляют собой целые числа, дают удобную возможность описания маршрутов передвижения персонажа и чётко указывают направление движения.
      Издержкой подобной системы может считаться её избыточность, которая компенсируется за счёт простой системы нормирования.
Теги:игрыразработкадизайн игргеометрия
Хабы: Математика
+17
2,3k 13
Комментарии 5

Похожие публикации

Лучшие публикации за сутки