Xpoint
   [напомнить пароль]

Определение координат хексов

Метки: [без меток]
2006-05-16 13:34:18 [обр] Михаил(0/17)[досье]
Думаю все представляют что такое хексы, и поля сделанные из хексов. Есть такая задача написать ф-ию которая бы возвращала координаты хексов расположенных на n-ом расстоянии от хекса с заданными координатами.
Если на поле с хексами использовать туже систему координат что и с квадратами, по двум осям X и Y, то получится приимерно следующее: http://www.nldragons.com/wlib/files/1/zap1.gif
Квадратики которые имеют один и тот же цвет, как рас и будут на хексовом поле распологаться на одинаковом радиусе от центра.
спустя 8 минут [обр] Алексей В. Иванов(3/2861)[досье]
Думаю все представляют что такое хексы, и поля сделанные из хексов.
Нет. Объясните, если не трудно.
спустя 10 минут [обр] Михаил(0/17)[досье]
Пустое поле: http://www.nldragons.com/wlib/files/1/heks1.gif
Подкрашены крайние хексы(темиже цветами что и на рисунке с квадратами):http://www.nldragons.com/wlib/files/1/heks2.gif
спустя 25 минут [обр] Даниэль Алиевский(1/125)[досье]

Т.е. "хексы" - это "гексагоны", по-русски "шестиугольники"?

В чем, собственно, вопрос? В приведенной постановке ответ звучит тривиально: перебирайте шестиугольники и проверяйте расстояние до центра заданного шестиугольника, не равно ли оно n. Но, видимо, имеется в виду не точное равенство?

Очевидно, что сей алгоритм легко оптимизируется, как и в случае квадратов. Можно взять стартовый шестиугольник, расположенный по горизонтали от центрального на расстоянии n, и запустить алгоритм, аналогичный Брезенхэмовскому: сдвинаться вверх или наклонно влево-вверх, с тем чтобы после каждого шага погрешность |x^2+y^2-r^2| оставалась минимальной. Вообще, есть масса вариантов решения, более или менее оптимальных. Что именно вызывает затруднения?

спустя 2 минуты [обр] Михаил(0/17)[досье]
перебирайте шестиугольники и проверяйте расстояние до центра заданного шестиугольника, не равно ли оно n
В это собственно и вопрос - как это определить?
спустя 16 минут [обр] Даниэль Алиевский(1/125)[досье]
Если верить школьным учебником, то расстояние вычисляется как sqrt(dx*dx+dy*dy), где dx=x2-x1, dy=y2-y1.
спустя 7 минут [обр] Михаил(0/17)[досье]
Даниэль Алиевский[досье]
Нет, это неподайдет. Нужно _точно_, определить расстояние от одного шестигранника до другого. Если этой ормулой ещё можно воспользоваца в случае с квадартами, то в случае с шестигранниками, сомневаюсь, т.к. распределение радиусов неравномерное. И если хотябы взять 1й радиус, то вверху от центра, правая и левая клетки входят уже во 2й радиус.
см: http://www.nldragons.com/wlib/files/1/heks1.gif
спустя 4 минуты [обр] Алексей В. Иванов(3/2861)[досье]
Для этого нужно пробегать всё поле шестиугольников. Если их много, а делать это надо часто в реал-тайме, то это может быть геморройно.
Кстати, был подобный вопрос. Для него я даже вот это писал, может, интересно будет: http://aivanov.com/test/beehive/
Михаил[досье] Кстати, если соты приплюснутые (как у вас на картинке), то надо считать по расстоянию или "по уму"?
спустя 55 секунд [обр] Алексей В. Иванов(3/2861)[досье]
Первый абзац моего посл. сообщения про решение Даниила[досье].
спустя 11 минут [обр] Михаил(0/17)[досье]
Алексей В. Иванов[досье]
Не суть важно - приплюснутые или нет, если каждый шестигранник имеет статические координаты. Или Вы видете в этом какуюто разницу?
спустя 30 минут [обр] Давид Мзареулян(14/1003)[досье]
Дайте, пожалуйста, определение «расстояния между гексами».
спустя 4 минуты [обр] Михаил(0/17)[досье]
http://www.nldragons.com/wlib/files/1/heks2.gif
Красный - центр, от него ведем отсчет. Синие - находятся на "1м радиусе", зеленые - "на 2м радиусе" от красного шестигранника.
Если считаете что тут неуметсно использовать слово "радиус", то можно просто говорить что шестигранники данного цвета расположены на n-ом расстоянии от центра.
спустя 4 минуты [обр] Давид Мзареулян(14/1003)[досье]
Хорошо. А что тогда такое «координаты хекса»?
спустя 40 секунд [обр] Алексей В. Иванов(3/2861)[досье]
Михаил[досье] Я имею у виду, что если они приплюснутые, то вместо формулы круга нужно формулу эллипса использовать, ну это не суть важно. Просто к слову.
Т.е. я правильно понял, что Вы хотите написать функцию, которой на вход поступают x,y,r, а выходит массив из n*6 пар координат x,y?
спустя 9 минут [обр] Михаил(0/17)[досье]

Алексей В. Иванов[досье]
Да, про ф-ию совершенно правильно.

Давид Мзареулян[досье]
Координаты - x,y. Для большей нагялдности - первая картинка.

спустя 2 минуты [обр] Михаил(0/17)[досье]
Алексей В. Иванов[досье]
Как я понял, в вашем алгоритме, на который вы дали ссылку, перебираюся все шестигранники, что не совсем приемлимо.
спустя 7 минут [обр] Михаил(0/17)[досье]
После всех обсуждений, поискал свой старый код, и мне кажется он является вполне работоспособным и раиональным:
int P=1;  // какая то константа - уже непомню зачем вводил
// getr0 - возвращает координаты всех шестигранников справа(если смотреть на экран) вверху от заданного
// остальный ф-ий - возвращают координаты шестигранников двигаясь по часовой стрелкет (если мне не изменяет память)
void getr0 (int x, int y, int *xr, int *yr, int ur)
{
   int d=2;
   for (int i=0; i<ur-P; i++)
   {
      xr[i]=x+i;
      yr[i]=y-ur-1+d;
      if ( i%2 == 1)
      {
         d++;
      }
      if ( x%2==1 && i%2==1)
      {
         yr[i]+=1;
      }
   }
}

void getr1 (int x, int y, int *xr, int *yr, int ur)
{
   for (int j=0; j<ur-P; j++)
   {
      xr[j]=x+ur-1;
      yr[j]=y-(ur/2)+j;
      if (x%2 == 1 && ur%2==0)
         yr[j]++;
   }
}

void getr2 (int x, int y, int *xr, int *yr, int ur)
{
   int d=2;
   for (int k=0; k<ur-P; k++)
   {
      xr[k]=x+k+1;
      yr[k]=y+ur-d;
      if ( k%2 == 1)
      {
         d++;
      }
      if ( x%2==1 && k%2==0)
      {
         yr[k]++;
      }
   }
}

void getr3 (int x, int y, int *xr, int *yr, int ur)
{
   int d=2;
   for (int l=0;l<ur-P;l++)
   {
      xr[l]=x-l;
      yr[l]=y+ur-d+1;
      if ( l%2 == 1)
      {
         d++;
      }
      if ( x%2==0 && l%2==1)
      {
         yr[l]-=1;
      }
   }
}

void getr4 (int x, int y, int *xr, int *yr, int ur)
{
   for (int b=0; b<ur-P; b++)
   {
      xr[b]=x-ur+1;
      yr[b]=y-(ur/2)+b+1;
      if (x%2 == 1  && ur%2==0)
         yr[b]++;

   }
}

void getr5 (int x, int y, int *xr, int *yr, int ur)
{
   int d=2;
   int d2=0;
   for (int v=0; v<ur-P; v++)
   {
      if (x%2==0)
      {
         d2=-1;
      }
      else
      {
         d2=0;
      }
      xr[v]=x-v-1;
      yr[v]=y-ur+d+d2;
      if ( v%2 == 1)
      {
         d++;
      }
      if ( x%2==0 && v%2==1)
      {
         yr[v]++;
      }
   }
}
спустя 3 минуты [обр] Михаил(0/17)[досье]

Маленькая поправка: getr0 - возвращает координаты всех шестигранников вверху от заданного

Кто что думает по этому поводу? Есть место быть данному алгоритму, или всеже стоит воспользоваца другим?

спустя 1 минуту [обр] Алексей В. Иванов(3/2861)[досье]

Не читал пока Ваш пост выше. Но написал эа это время следующее:


Задача решается 2(3) циклами, где i:=0; i<r; ++i;. Закономерность видна из следующей картинки (цветом обозначены циклы). Т.е. верхние и нижние ячейки рассчитываются просто — там меняется на единицу только x, а боковые ячейки рассчитываются как x=|x±0.5|, а y=y±1

спустя 2 минуты [обр] Алексей В. Иванов(3/2861)[досье]
Поправлюсь: цикл должен быть один. Формул 2-3 по сути. В итоге — 6 цепочек координат.
спустя 22 часа [обр] Даниэль Алиевский(1/125)[досье]

Действительно, при таком определении "расстояния" алгоритмической задачи тут вообще нет. Все просто. Правда, в итоге найденные шестиугольники всегда образуют большой шестиугольник, а не "нарисованную окружность", на которую автор намекал картинкой http://www.nldragons.com/wlib/files/1/zap1.gif

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

Powered by POEM™ Engine Copyright © 2002-2005