Гексагональные плитки и поиск их соседних соседей

Question

Я разрабатываю простую 2D -настольную игру, используя шестиугольные карты плитки, я читал несколько статей (включая Gamedev One, которые связаны каждый раз, когда возникают вопрос о шестиугольной плитках) о том, как рисовать гексы на экране и как управлять Движение (хотя многое из этого я уже делал раньше). Моя главная проблема - найти соседние плитки на основе данного радиуса.

Вот как работает моя система карт:

(0,0) (0,1) (0,2) (0,3) (0,4)
   (1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
   (3,0) (3,1) (3,2) (3,3) (3,4)

так далее...

Я борюсь с тем, что я не могу просто «выбрать» соседние плитки, используя for(x-range;x+range;x++); for(y-range;y+range;y++); Поскольку он выбирает нежелательную плитку (в примере, который я дал, выбрав (1,1) плитку и давая диапазон 1, также даст мне (3,0) плитку (те, которые мне действительно нужно (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) 0,2) (1,0) (1,2) (2,1) (2,2)), что вроде как примыкает к плите (из -за того, как массив структурирован), но это не то, что я хочу Выбрать. Я мог бы просто придумать это, но это не было бы красиво и, вероятно, не охватило бы все аспекты «выбора радиуса».

Может ли кто -нибудь указать мне правильное направление здесь?

Answer 1

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

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

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

Деформация

Что нам нужно понять, так это деформация произошла в определенном направлении, вдоль [(-1,1) (1,-1)] Воображаемая линия в моем примере. Чтобы быть более точным, как будто сетка была удлинена вдоль этой линии, и раздавлен вдоль линии перпендикулярно этому. Поэтому, естественно, две плитки на этой линии были разбросаны и больше не визуально примыкают. И наоборот, плитки (1, 1) а также (-1, -1) которые были диагональ (0, 0) теперь необычайно близко к (0, 0), так близко на самом деле, что они сейчас визуально прилегает к (0, 0). Анкет Математически, однако, они все еще являются диагоналами, и это помогает обращаться с ними таким образом в вашем коде.

Выбор

Изображение, которое я показываю, иллюстрирует радиус 1. Для радиуса двух вы заметите (2, -2) а также (-2, 2) плитки, которые не должны быть включены в выбор. И так далее. Итак, для любого выбора радиуса р, точки (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) непосредственно в цикл своего отбора, чтобы вы могли итерации сетки таким образом, чтобы избежать доходной плитки вообще.

Answer 2

Самый простой метод, о котором я могу подумать ...

minX = x-range; maxX = x+range
select (minX,y) to (maxX, y), excluding (x,y) if that's what you want to do
for each i from 1 to range:
    if y+i is odd then maxX -= 1, otherwise minX += 1
    select (minX, y+i) to (maxX, y+i)
    select (minX, y-i) to (maxX, y-i)

Это может быть немного не так; Я только что проработал в своей голове. Но, по крайней мере, это идея о том, что вам нужно сделать.

В C'ish:

void select(int x, int y) { /* todo: implement this */ }

void selectRange(int x, int y, int range)
{
    int minX = x - range, maxX = x + range;
    for (int i = minX; i <= maxX; ++i)
        if (i != x) select(i, y);
    for (int yOff = 1; yOff <= range; ++yOff)
    {
        if (y+yOff % 2 == 1) --maxX; else ++minX;
        for (int i=minX; i<=maxX; ++i)
        {
            select(i, y+yOff);  select(i, y-yOff);
        }
    }  
}