На гексагональной сетке: выбор плиток в пределах заданного радиуса от точки выбора.

Что такое гексагональная сетка?

Вы можете увидеть две сетки. Все дело в том, как вы нумеруете плитки и как вы понимаете, что такое гексагональная сетка. На мой взгляд, гексагональная сетка - это не что иное, как деформированная ортогональная сетка.

Две шестиугольные плитки, которые я обвел фиолетовым, теоретически все еще примыкают к 0,0. Однако из-за деформации, через которую мы прошли, чтобы получить сетку шестиугольника из ортогональной, эти два элемента больше не являются визуально смежными.

Деформация

Что нам нужно понять, так это то, что деформация произошла в определенном направлении, вдоль воображаемой линии в моем примере. Точнее, сетка выглядит так, как если бы сетка была вытянута вдоль этой линии и сжата вдоль линии, перпендикулярной ей. Итак, естественно, две плитки на этой линии разошлись и визуально перестали быть смежными. И наоборот, плитки (1, 1) и (-1, -1), которые были диагонали к (0, 0), теперь необычно близки к (0, 0), фактически так близко, что теперь они визуально смежны с (0, 0). Однако математически они по-прежнему являются диагоналями, и это помогает трактовать их таким образом в вашем коде.

Выбор

Изображение, которое я показываю, показывает радиус 1. Для радиуса два вы заметите, что (2, -2) и (-2, 2) - плитки, которые не должны быть включены в выборку. И так далее. Таким образом, для любого выбора радиуса r не следует выбирать точки (r, -r) и (-r, r). В остальном ваш алгоритм выбора должен быть таким же, как и у квадратной сетки.

Просто убедитесь, что ваша ось правильно настроена на гексагональной сетке и что вы соответствующим образом пронумеровываете плитки.

Выполнение

Давайте немного подробнее остановимся на этом. Теперь мы знаем, что движение по любому направлению в сетке стоит нам 1. А движение по растянутому направлению стоит нам 2. См., Например, с (0, 0) по (-1, 1).

Зная это, мы можем вычислить кратчайшее расстояние между любыми двумя плитками на такой сетке, разложив расстояние на две составляющие: диагональное движение и прямое движение вдоль одной из осей. Например, для расстояния между (1, 1) и (-2, 5) на нормальной сетке мы имеем:

Normal distance = (1, 1) - (-2, 5) = (3, -4)

Это был бы вектор расстояния между двумя плитками, если бы они были на квадратной сетке. Однако нам нужно компенсировать деформацию сетки, поэтому мы выполняем разложение следующим образом:

(3, -4) = (3, -3) + (0, -1)

Как видите, мы разложили вектор на один диагональный (3, -3) и один прямой вдоль оси (0, -1).

Теперь мы проверяем, находится ли диагональ вдоль оси деформации, которая является любой точкой (n, -n), где n - целое число, которое может быть как положительным, так и отрицательным. (3, -3) действительно удовлетворяет этому условию, поэтому этот диагональный вектор направлен вдоль деформации. Это означает, что длина (или стоимость) этого вектора вместо 3, она будет двойной, то есть 6.

Итак, чтобы резюмировать. Расстояние между (1, 1) и (-2, 5) равно длине (3, -3) плюс длина (0, -1). Это distance = 3 * 2 + 1 = 7.

Реализация на C ++

Ниже представлена ​​реализация на C ++ алгоритма, который я объяснил выше:

int ComputeDistanceHexGrid(const Point & A, const Point & B)
{
  // compute distance as we would on a normal grid
  Point distance;
  distance.x = A.x - B.x;
  distance.y = A.y - B.y;

  // compensate for grid deformation
  // grid is stretched along (-n, n) line so points along that line have
  // a distance of 2 between them instead of 1

  // to calculate the shortest path, we decompose it into one diagonal movement(shortcut)
  // and one straight movement along an axis
  Point diagonalMovement;
  int lesserCoord = abs(distance.x) < abs(distance.y) ? abs(distance.x) : abs(distance.y);
  diagonalMovement.x = (distance.x < 0) ? -lesserCoord : lesserCoord; // keep the sign 
  diagonalMovement.y = (distance.y < 0) ? -lesserCoord : lesserCoord; // keep the sign

  Point straightMovement;

  // one of x or y should always be 0 because we are calculating a straight
  // line along one of the axis
  straightMovement.x = distance.x - diagonalMovement.x;
  straightMovement.y = distance.y - diagonalMovement.y;

  // calculate distance
  size_t straightDistance = abs(straightMovement.x) + abs(straightMovement.y);
  size_t diagonalDistance = abs(diagonalMovement.x);

  // if we are traveling diagonally along the stretch deformation we double
  // the diagonal distance
  if ( (diagonalMovement.x < 0 && diagonalMovement.y > 0) || 
       (diagonalMovement.x > 0 && diagonalMovement.y < 0) )
  {
    diagonalDistance *= 2;
  }

  return straightDistance + diagonalDistance;
}

Теперь, учитывая реализованную выше функцию ComputeDistanceHexGrid, теперь у вас может быть наивная, неоптимизированная реализация алгоритма выбора, который будет игнорировать любые плитки за пределами указанного диапазона выбора:

int _tmain(int argc, _TCHAR* argv[])
{
  // your radius selection now becomes your usual orthogonal algorithm
  // except you eliminate hex tiles too far away from your selection center
  // for(x-range;x+range;x++); for(y-range;y+range;y++);
  Point selectionCenter = {1, 1};
  int range = 1;

  for ( int x = selectionCenter.x - range;
            x <= selectionCenter.x + range;
            ++x )
  {
    for ( int y = selectionCenter.y - range;
              y <= selectionCenter.y + range;
              ++y )
    {
      Point p = {x, y};
      if ( ComputeDistanceHexGrid(selectionCenter, p) <= range )
        cout << "(" << x << ", " << y << ")" << endl;
      else
      {
        // do nothing, skip this tile since it is out of selection range
      }
    }
  }

    return 0;
}

Для точки выбора (1, 1) и диапазона 1 приведенный выше код отобразит ожидаемый результат:

(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)

Возможная оптимизация

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

Просто разместите свою сетку следующим образом:

   +-----+-----+-----+-----+
   | 0   |  1  | 2   |  3  |          even row
   +-----+-----+-----+--+-----+
      |  4  |  5  |  6  |  7  | ==>   odd row
   +--+-----+-----+-----+--+--+
   |  8  |  9  |  10 |  11 |          even row
   +-----+-----+-----+-----+

Для нечетных строк (N>>2)&1 == 1 необходимо концептуально сдвинуть слоты на половину ширины слота.
Тогда соседями будут {N-1, N + 1, Na, N-a + 1, N + b, N + b + 1 }, a = b = 4.
Для четных строк a = 5, b = 3. (a = вверху, b = внизу)

С помощью этой идеи можно создать список смежности и выполнить поиск в ширину (с некоторыми метриками для расстояния - евклидовым или каким-либо другим, манхэттенское расстояние будет вызываться в медовой сетке).