Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 51
Казалось бы всё просто, но так приятно читать! Спасибо за доставленное удовольствие!
Красиво. У меня с первой попытки получилось заметно сложнее.
А главное все сложности инкапсулировать в библиотеке))
Я вот для LibCanvas реализовал гексагональную карту основанную на rgb-координатах. Правда пришлось формулы править, чтобы неправильные шестиугольники можно было забивать (с разной длиной стороны).
Так что интересующиеся могут почитать статью по ссылке — там тоже можно что-то почерпнуть.
Я вот для LibCanvas реализовал гексагональную карту основанную на rgb-координатах. Правда пришлось формулы править, чтобы неправильные шестиугольники можно было забивать (с разной длиной стороны).
Так что интересующиеся могут почитать статью по ссылке — там тоже можно что-то почерпнуть.
Исходник
atom.declare( 'LibCanvas.Engines.Hex.Projection', {
multipliers: {
height: Math.cos( Math.PI / 6 ) * 2,
chord : 1/2 // Math.sin( Math.PI / 6 )
},
initialize: function (settings) {
settings = this.settings = new Settings({
baseLength : 0,
chordLength: null,
hexHeight : null,
start : new Point(0, 0)
}).set(settings);
if (settings.get('chordLength') == null) {
settings.set({
chordLength: settings.get('baseLength') * this.multipliers.chord,
hexHeight : settings.get('hexHeight' ) * this.multipliers.height
});
}
},
isZero: function (c) {
return c[0] === 0 && c[1] === 0 && c[2] === 0;
},
rgbToPoint: function (coordinates) {
var
red = coordinates[0],
green = coordinates[1],
blue = coordinates[2],
settings = this.settings,
base = settings.get('baseLength'),
chord = settings.get('chordLength'),
height = settings.get('hexHeight'),
start = settings.get('start');
if (red + green + blue !== 0) {
throw new Error( 'Wrong coordinates: ' + red + ' ' + green + ' ' + blue);
}
return new Point(
start.x + (base + chord) * red,
start.y + (blue - green) * height / 2
);
},
pointToRgb: function (point) {
var
settings = this.settings,
base = settings.get('baseLength'),
chord = settings.get('chordLength'),
height = settings.get('hexHeight'),
start = settings.get('start'),
// counting coords
red = (point.x - start.x) / (base + chord),
blue = (point.y - start.y - red * height / 2) / height,
green = 0 - red - blue;
var dist = function (c) {
return Math.abs(c[0] - red) + Math.abs(c[1] - green) + Math.abs(c[2] - blue);
};
var
rF = Math.floor(red ), rC = Math.ceil(red ),
gF = Math.floor(green), gC = Math.ceil(green),
bF = Math.floor(blue ), bC = Math.ceil(blue );
return [
// we need to find closest integer coordinates
[rF, gF, bF],
[rF, gC, bF],
[rF, gF, bC],
[rF, gC, bC],
[rC, gF, bF],
[rC, gC, bF],
[rC, gF, bC],
[rC, gC, bC]
].filter(function (v) {
// only correct variants - sum must be equals to zero
return atom.array.sum(v) == 0;
})
.sort(function (left, right) {
// we need coordinates with the smallest distance
return dist(left) < dist(right) ? -1 : 1;
})[0];
},
createPolygon: function (center) {
var
settings = this.settings,
halfBase = settings.get('baseLength') / 2,
halfHeight = settings.get('hexHeight') / 2,
radius = halfBase + settings.get('chordLength'),
right = center.x + halfBase,
left = center.x - halfBase,
top = center.y - halfHeight,
bottom = center.y + halfHeight;
return new Polygon([
new Point(left , top), // top-left
new Point(right, top), // top-right
new Point(center.x + radius, center.y), // right
new Point(right, bottom), // bottom-right
new Point(left , bottom), // bottom-left
new Point(center.x - radius, center.y) // left
]);
}
});
А можете объяснить в чем выигрыш гексагональной сетки перед сеткой разбитой на квадраты? Для квадратных ячеек можно обходиться побитовыми сдвигами и исключить операцию деления совсем, здесь же на одно преобразивание уходит целых 5 операций деления, что невыгодно сказывается на производительности.
Прежде всего — у нее меньше разброс расстояний до центра (при той же площади): для квадрата максимальное расстояние 0.7071, для шестиугольника — 0.6204. Во вторых, при разбивке поля на связные области не возникает проблемы с тем, что две ячейки соприкасаются по вершине. Если уж соприкоснулись — то по углу. В третьих, кратчайший путь по клеткам между двумя точками короче. Четвертое относится к компьютерной графике — при триангуляции нам лучше брать вершины на треугольной сетке (= центры 6-угольной), и если мы хотим, чтобы вершина была усреднением точек области — усреднять как раз по шестиугольникам.
Возможно, есть и другие преимущества.
Возможно, есть и другие преимущества.
При переходе в любую соседнюю клетку расстояние всегда одинаковое. В то время, как для квадратных клеток переход по диагонали в SQRT(2) раз длиннее, чем в стороны.
Прежде всего в игровой механике, я не могу представить себе HoMM на квадратной сетке.
Спросите у пчел за соты. Апологеты численных методов, основанных на гексагональных сетках, рвут волосы на груди, утверждая, что шестиугольные сетки выбрала сама природа.
Про выигрыш уже довольно много комментариев, мне добавить нечего.
А вот насчет
не соглашусь. Как я написал в комментарии в коде, операции деления на полупериод решетки можно засунуть внутрь констант (cos и sin). Итого будет 4 сложения, 2 вычитания, 5 умножений, 2 деления и 5 округлений.
А вот насчет
здесь же на одно преобразивание уходит целых 5 операций деления
не соглашусь. Как я написал в комментарии в коде, операции деления на полупериод решетки можно засунуть внутрь констант (cos и sin). Итого будет 4 сложения, 2 вычитания, 5 умножений, 2 деления и 5 округлений.
Для сетки с квадратами, например, приходится искать / рисовать спрайт в 8 положениях (4 стороны + 4 диагонали), а для гексагональной сетки, соответственно, только в 6.
Добавлю к вышесказанному, что пчелы используют шестиугольные соты из-за того, что шестиугольник с одной стороны по форме больше приближен к кругу, чем квадрат, а значит имеет большее соотношение площадь / периметр (экономия материала), а с другой — шестиугольники упаковываются без промежутков, в отличие от кругов.
Возможно большее количество вещей в нашей жизни могло бы / будет иметь форму шестиугольника, а не квадрата/прямоугольника (разбивка города на кварталы или форма разреза зданий например), просто форма квадрата используется в силу исторических и некоторых других причин (из-за простоты вычислений).
Возможно большее количество вещей в нашей жизни могло бы / будет иметь форму шестиугольника, а не квадрата/прямоугольника (разбивка города на кварталы или форма разреза зданий например), просто форма квадрата используется в силу исторических и некоторых других причин (из-за простоты вычислений).
Разбивка города на 6-угольные кварталы неудобна для лошадей — улицы будут состоять из сплошных поворотов, с ветерком не прокатишься. Для зданий шестиугольник вообще ни к чему: там главный приоритет — не затраты материала на стены, а площадь окон в пересчете на объем, чем больше — тем лучше. Кроме того, вдоль стены прямоугольного склада/фургона можно уложить без щелей прямоугольные контейнеры любого размера. Шестиугольные так не уложишь. Далее, прямоугольник можно двигать по проходу, ширина которого равна ширине прямоугольника (проделанному прямо в решетке их укладки), а для 6-угольника придется освобождать гораздо больше места. И в жизни мы этим пользуемся очень часто. В общем, прямоугольники лучше, и в первую очередь — из-за того, что 90+90=180.
Разбивка города на 6-угольные кварталы неудобна для лошадей — улицы будут состоять из сплошных поворотов, с ветерком не прокатишься.
Вполне прокатишься — не обязательно же на каждом повороте куда-то заворачивать. Для перемещения из точки A в точку B нужен всего один поворот максимум, как в случае и с прямоугольниками. Ну и тем более на лошадях сейчас почти никто не катается.
Для зданий шестиугольник вообще ни к чему: там главный приоритет — не затраты материала на стены, а площадь окон в пересчете на объем, чем больше — тем лучше.
Спорный вопрос — спрошу также у свои родственников-архитекторов.
Кроме того, вдоль стены прямоугольного склада/фургона можно уложить без щелей прямоугольные контейнеры любого размера. Шестиугольные так не уложишь.
Ну а прямоугольные можно так уложить :)
Далее, прямоугольник можно двигать по проходу, ширина которого равна ширине прямоугольника (проделанному прямо в решетке их укладки), а для 6-угольника придется освобождать гораздо больше места. И в жизни мы этим пользуемся очень часто. В общем, прямоугольники лучше, и в первую очередь — из-за того, что 90+90=180.
Но у шестиугольников есть другие преимущества, а везде пользуются прямоугольниками, потому что так привычно, так же как и 10-значной системой счисления. Это мое мнение.
Вполне прокатишься — не обязательно же на каждом повороте куда-то заворачивать. Для перемещения из точки A в точку B нужен всего один поворот максимум, как в случае и с прямоугольниками. Ну и тем более на лошадях сейчас почти никто не катается.
Если я не поверну, то на первом же перекрестке (там сходятся три улицы под углом 120 гр, как и на любом другом) врежусь в угол квартала, находящегося передо мной. И не важно, на лошади я буду, на автомобиле или на гексацикле.
Ну а прямоугольные можно так уложить :)
Да, и все так делают. Особенно если контейнеры одинакового размера. Шестиугольники как не укладывай, а у стен останутся щели — треугольные или трапецевидные.
Но у шестиугольников есть другие преимущества
Еще одно преимущество прямоугольника или квадрата — что его можно разрезать на прямоугольники меньших размеров. И этим мы тоже часто пользуемся — и при застройке прямоугольного квартала, и при разработке карты с непостоянным разрешением, и при проектировании шкафа для одежды. Шестиугольник на меньшие 6-угольники не разрежешь.
Если я не поверну, то на первом же перекрестке (там сходятся три улицы под углом 120 гр, как и на любом другом) врежусь в угол квартала, находящегося передо мной. И не важно, на лошади я буду, на автомобиле или на гексацикле.
Ну а прямоугольные можно так уложить :)
Да, действительно не подумал и написал глупость.
Два умножения можно сэкономить:
double fm = along_coord * ( 2.0 / m_period);
double fl= (cos60 * along_coord + sin60 * other_coord) * ( 2.0 / m_period)
int m = floor(fm);
int l = floor(fl);
int r = floor(fm-fl);
double fm = along_coord * ( 2.0 / m_period);
double fl= (cos60 * along_coord + sin60 * other_coord) * ( 2.0 / m_period)
int m = floor(fm);
int l = floor(fl);
int r = floor(fm-fl);
Тогда уж
double m_period_inv2 = 2.0 / m_period;
double m_cos60_per=m_period_inv2/2;
double m_sin60_per=m_period_inv2*sqrt(3)/2;
double fm = along_coord * m_period_inv2;
double fl= (m_cos60_per * along_coord + m_sin60_per * other_coord);
— как и говорил автор.
В итоге: 3 вещественных умножения, два вещественных сложения, 3 (округления + преобразования к int), 4 целочисленных сложения и два целочисленных деления на константу (правда, там надо унести подальше начало координат — чтобы результат получился неотрицательным).
double m_period_inv2 = 2.0 / m_period;
double m_cos60_per=m_period_inv2/2;
double m_sin60_per=m_period_inv2*sqrt(3)/2;
double fm = along_coord * m_period_inv2;
double fl= (m_cos60_per * along_coord + m_sin60_per * other_coord);
— как и говорил автор.
В итоге: 3 вещественных умножения, два вещественных сложения, 3 (округления + преобразования к int), 4 целочисленных сложения и два целочисленных деления на константу (правда, там надо унести подальше начало координат — чтобы результат получился неотрицательным).
Вообще стоит приучать себя никогда не делить на 2, а умножать на 0.5, тем более если с double работаем.
С double это все равно (компилятор соптимизирует), а с целыми — конечно, надо вместо DIV писать SAR :)
Но надо не перестараться и не заменить деление на 3 умножением на 0.33…
Но целые числа на 0.5 умножать категорически нельзя, если не хотите получить вещественный результат. Впрочем, это все очевидно.
Но целые числа на 0.5 умножать категорически нельзя, если не хотите получить вещественный результат. Впрочем, это все очевидно.
Не вижу рядом корабля :)
А вот насчет оптимизаций компилятора вы неправы — большую часть времени я работаю в Debug режиме и там нет оптимизаций.
А вот насчет оптимизаций компилятора вы неправы — большую часть времени я работаю в Debug режиме и там нет оптимизаций.
Вы правы — компилятор действительно пишет fdiv для деления на два. Теряется на этом примерно 1 такт процессора (0.3 нс)
Дайте ссылку на деление за пару тактов. По моей информации на этом теряется от 10 и более тактов.
Я сравнивал циклы
double u,s;
scanf("%lf",&u);
int N=1000000000;
s=0;
for(int i=0;i<N;i++) s+=(u+i)*0.5;
и
s=0;
for(int i=0;i<N;i++) s+=(u+i)/2;
Разница в коде была только в команде fmul для первого цикла против fdiv для второго. Время выполнения первого — 6.07 сек, второго — 6.38 сек (проверял несколько раз, ставя их в программе в разном порядке, потом усреднил). Разница — 0.3 сек, что в пересчете на один шаг цикла даст 1 такт.
double u,s;
scanf("%lf",&u);
int N=1000000000;
s=0;
for(int i=0;i<N;i++) s+=(u+i)*0.5;
и
s=0;
for(int i=0;i<N;i++) s+=(u+i)/2;
Разница в коде была только в команде fmul для первого цикла против fdiv для второго. Время выполнения первого — 6.07 сек, второго — 6.38 сек (проверял несколько раз, ставя их в программе в разном порядке, потом усреднил). Разница — 0.3 сек, что в пересчете на один шаг цикла даст 1 такт.
Рекомендую больше так никогда не делать, а смотреть в даташитах процессоров, ну или хотя бы по профильным ресурсам полазить.
Дело в том, что кол-во тактов зависит не только от производителя процессора, и даже не только от модели, но еще и от чисел, участвующих в делении, и от того есть ли данные в кэше процессора. В результате кол-во тактов на деление на одном AMD процессоре скачет от 15 до 70 с мелочью, у интела та же ситуация, только цифры другие. И так для всякой тригонометрии и прочего.
Дело в том, что кол-во тактов зависит не только от производителя процессора, и даже не только от модели, но еще и от чисел, участвующих в делении, и от того есть ли данные в кэше процессора. В результате кол-во тактов на деление на одном AMD процессоре скачет от 15 до 70 с мелочью, у интела та же ситуация, только цифры другие. И так для всякой тригонометрии и прочего.
В таком случае мне придется еще и изучить алгоритм распределения команд по логическим устройствам, а данных — по конвееру, разобраться, какие команды в каждом конкретном случае будут выполняться параллельно, а какие будут ждать и сколько — и даже при этом я буду ошибаться, пытаясь определить скорость выполнения кода. Мне кажется, что эксперимент даст более надежный результат (пусть даже этот результат только для конкретных условий).
И, кстати, после того, как я убрал сложение, время выполнения кода с делением уменьшилось до 2.7 сек, т.е. 10 тактов на шаг цикла. Немного не соответсятвует Вашей информации про 15-70 тактов на одно только деление. Проверил по коду — он ничего не оптимизирует.
Процессор AMD FX-8120, 3.9 GHz.
И, кстати, после того, как я убрал сложение, время выполнения кода с делением уменьшилось до 2.7 сек, т.е. 10 тактов на шаг цикла. Немного не соответсятвует Вашей информации про 15-70 тактов на одно только деление. Проверил по коду — он ничего не оптимизирует.
Процессор AMD FX-8120, 3.9 GHz.
Попробовал делить на разные числа (например, на 2.01) — получается проигрыш около 30 тактов на одно деление. Но конкретно деление на 2 проигрывает умножению на 0.5 ровно 1 такт — в нескольких разных экспериментах. Так что «доверяй, но проверяй».
Думаю имеет место быть оптимизация в процессоре. В любом случае тесты годятся в основном для реального кода — когда важна фактическая производительность, когда цикл большой, когда не все данные попали в кэш.
В реальном коде может быть уже поздно: выбор последовательности обработки влияет на архитектуру программы. Например, мне надо решить, как эффективнее обработать массив данных (последовательно несколькими функциями, список их заранее неизвестен): завести массив функций, обрабатывающих по одному элементу (и прогонять каждый элемент по этому массиву без задержки в памяти), или заставить каждую функцию обрабатывать весь массив, и сохранять результаты тоже в массиве. При этом я уже знаю, что эта обработка является узким местом программы (так что оптимизация не будет «преждевременной»). Интуиция вообще ничего не подсказывает — и то и другое плохо. Как тут обойтись без игрушечных тестов?
Так игрушечный тест даст игрушечный результат. Когда будете тестировать на живом коде — результаты могут быть совсем другими. Потому как зависит от того — все ли данные в кеше, помещается ли цикл целиком в кеш или нет. Если же вы все это учтете в игрушечном тесте, то тест по факту уже перестанет быть игрушечным и станет кодом, который уже написан и его можно вставлять в приложение.
посмотрите тут исходники. хоть там и AS3, но разберётесь. там много интересного.
Обратное преобразование нужно, чтоб узнать куда ткнул мышкой(или пальцем) игрок, угадал?
Для 3D такой фокус не пройдет — нужно использовать хит-тест.
В WPF-3D это делается вот так
private void viewport_MouseDown(object sender, MouseButtonEventArgs e)
{
int increment = 0;
RayMeshGeometry3DHitTestResult result = (RayMeshGeometry3DHitTestResult)VisualTreeHelper.HitTest(viewport, e.GetPosition(viewport));
Сell cl = gMap.getCell(result.MeshHit);
тут предполагается, что все поверхности (Mesh) запомнены в словаре, например, и getCell оборачивает к ней доступ.
Для 3D такой фокус не пройдет — нужно использовать хит-тест.
В WPF-3D это делается вот так
private void viewport_MouseDown(object sender, MouseButtonEventArgs e)
{
int increment = 0;
RayMeshGeometry3DHitTestResult result = (RayMeshGeometry3DHitTestResult)VisualTreeHelper.HitTest(viewport, e.GetPosition(viewport));
Сell cl = gMap.getCell(result.MeshHit);
тут предполагается, что все поверхности (Mesh) запомнены в словаре, например, и getCell оборачивает к ней доступ.
Если кому интересно —
Не вставилась картинка:
dl.dropbox.com/u/26488961/398895291.png
dl.dropbox.com/u/26488961/398895291.png
Есть такая убер-статья, почитайте, мне она сильно помогла в своё время: www-cs-students.stanford.edu/~amitp/game-programming/grids/
еще можно почитать про Диаграммы Вороного.
ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE
ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE
Немного переделал под свои нужды, чтобы поле рисовалось не параллелограммом, а прямоугольником:
В прямом преобразовании:
В обратном преобразовании:
В прямом преобразовании:
double along_coord = m_period * m + (l&1 ? m_period/2. : 0.);
В обратном преобразовании:
// Считаем проекции на оси m, l и r (в половинах периода решетки).
// Здесь можно было обойтись меньшим количеством операций,
// засунув, например, двойку и период решетки под косинусы и синусы
// в отдельные константы
// int m = floor(2 * along_coord / m_period); // это уже не нужно
int l = floor(2 * (cos60 * along_coord + sin60 * other_coord) / m_period);
int r = floor(2 * (cos60 * along_coord - sin60 * other_coord) / m_period);
// И, собственно, сам финт ушами:
int rc = floor((l - r + 1) / 3.0);
int cc = floor((along_coord + (!(rc&1) ? m_period/2. : 0.)) / m_period);
return MyPointI(cc, rc);
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О прямоугольных координатах и гексагональных сетках