Comments 23
Вообще говоря, в последнем случае совершенно неочевидно, зачем персонажу дергаться вправо-влево, когда путь точно такой же длины получится сначала при движении пол-пути на «юго-восток», и потом еще пол-пути на «юго-запад»? Обычно на смену направления тоже какие-то time-pointы закладываются.
В первом случае тоже можно пройти по горизонтали до определенной точки, потом спуститься на «юго-восток». Путей, реализующих минимальное расстояние, может быть много, мне был интересен путь, близкий к геометрической прямой. Если учитывать время смены направлений, задача становится тривиальной — на такой плоскости из любого пункта A в любой пункт B при отсутствии препятствий существует до двух минимальных по времени путей с максимум одной сменой направления. Это как раз маршруты, ограничивающие «пучок» оптимальных.
Я был бы крайне удивлен, если бы мои юниты, посланные строго вниз, пошли бы по описанной вами траектории…
Если взять косоугольную систему координат:
то работает такой алгоритм:
По крайней мере, мне его обмануть не удалось.
0,0 1,0 2,0 3,0 4,0
0,1 1,1 2,1 3,1
-1,2 0,2 1,2 2,2 3,2
-1,3 0,3 1,3 2,3
-2,4 -1,4 0,4 1,4 2,4
то работает такой алгоритм:
int sign(int a) { return a<0 ? -1 : 1; }
void Line(int x0,int y0,int x1,int y1) {
int dx=x1-x0,dy=y1-y0;
int p=sign(dy),q=sign(dx),r=sign(dx+dy);
int ax=(q+r)/2,ay=(p-q)/2,bx=-ay,by=(p+r)/2;
int da=ay*dx-ax*dy;
int db=by*dx-bx*dy;
int lim=da+db;
int a=0;
SetPixel(x0,y0);
while(x0!=x1 || y0!=y1) {
if(db==0 || (da!=0 && 2*a<lim)) {
x0+=bx; y0+=by; a+=db;
} else {
x0+=ax; y0+=ay; a+=da;
}
SetPixel(x0,y0);
}
}
По крайней мере, мне его обмануть не удалось.
Так даже лучше (не проверял)
int s(int a) { return a<0 ? -1 : 1; }
void L(int x,int y,int f,int e) {
int g=f-x,h=e-y;
int p=sign(h),q=sign(g),r=sign(g+h);
int i=(q+r)/2,j=(p-q)/2,k=-j,l=(p+r)/2;
int m=j*g-i*h;
int n=l*g-k*h;
int z=m+n;
int a=0;
SetPixel(x,y);
while(x!=f || y!=e) {
if(n==0 || (m!=0 && 2*a<z)) {
x+=k; y+=l; a+=n;
} else {
x+=i; y+=j; a+=m;
}
SetPixel(x,y);
}
}Тогда уж так (тоже не проверял) :)
void L(int x,int y,int f,int e) {
int g=f-x,h=e-y;
int i=(g>0)+(g+h>0)-1,j=(h>0)-(g>0);
int m=j*g-i*h,n=(i+j)*g+j*h;
int z=m+n,a=0;
SetPixel(x,y);
while((x-f)|(y-e)) {
if(!n || (m && 2*a<z)) {
x-=j; y+=i+j; a+=n;
} else {
x+=i; y+=j; a+=m;
}
SetPixel(x,y);
}
}
согласен (даже не буду проверять)
void L(int x,int y,int f,int e) {
int g=f-x,h=e-y;
int i=(g>0)+(g+h>0)-1,j=(h>0)-(g>0);
int m=j*g-i*h,n=(i+j)*g+j*h;
int z=m+n,a=0;
SetPixel(x,y);
for(;(x-f)*(y-e);) {
if(!n || (m && (a<<1)<z)) {
x-=j; y+=i+j; a+=n;
} else {
x+=i; y+=j; a+=m;
}
SetPixel(x,y);
}
}Если оптимизировать дальше, то можно убрать вычитание единицы и переменную z, а сравнение в цикле заменить на сравнение с нулём:
Для языков, в которых нет неявного преобразования bool в int, вторую строчку можно переписать как
void Line(int x0,int y0,int x1,int y1) {
int dx=x1-x0,dy=y1-y0;
int ax=(dx>0)-(dx+dy<0),ay=(dy>0)-(dx>0);
int da=ay*dx-ax*dy;
int db=(ax+ay)*dx+ay*dy;
int a=-((da+db)>>1); // we need -floor((da+db)/2)!
SetPixel(x0,y0);
while((x0-x1)|(y0-y1)) {
if(!db || (da && a<=0)) {
x0-=ay; y0+=ax+ay; a+=db;
} else {
x0+=ax; y0+=ay; a+=da;
}
SetPixel(x0,y0);
}
}
Для языков, в которых нет неявного преобразования bool в int, вторую строчку можно переписать как
int ax=(dx>>31)-~((dx+dy)>>31),ay=(dy>>31)-(dx>>31);
без комментариев! только код. только хардкор! (я думаю мы тут «оптимизируем» на си)
я думаю мы тут «оптимизируем» на си
Кстати, не факт. Далеко не очевидно, что будет быстрее —
int ay=(dy>>31)-(dx>>31);
или
int ay=(dy>=0)-(dx>=0);
— хоть для C, хоть для C#, хоть для других языков. В зависимости от компилятора и процессора результаты могут быть любыми.
А комментарий нужен, чтобы последователи не пытались повысить читабельность, заменив сдвиг на деление: это привело бы к ухудшению качества полученных прямых (а в некоторых случаях, возможно, и к зацикливанию).
так стоп. я играю в «возьмём мутно написаный алогритм и сделаем его ещё мутней».
то есть оптимизация здесь совсем в кавычках и о скорости речи нет. только о всё большей нечитаемости кода.
то есть оптимизация здесь совсем в кавычках и о скорости речи нет. только о всё большей нечитаемости кода.
Почитайте отличную статью про гексогональные сетки: www.redblobgames.com/grids/hexagons/
Там в том числе обсуждется тема прямых линий.
Там в том числе обсуждется тема прямых линий.
Спасибо огромное. Там, я бы сказал, обсуждается всё что можно обсудить про шестиугольники :)
Кстати, это продолжение более лаконичной и не такой интерактивной статьи, которую можно использовать для сравнения разных сеток (треугольник, квадрат, гексагон):
Кстати, это продолжение более лаконичной и не такой интерактивной статьи, которую можно использовать для сравнения разных сеток (треугольник, квадрат, гексагон):
Спасибо! С удовольствием посмотрю. Заметное сходство иллюстраций :)
Мне понравилась статья. Возникла мысль, что для гексагональной и треугольной систем координат можно также разработать алгоритмы заливки многоугольников, отсечения отрезков, построения окружностей с помощью алгоритма Брезенхэма и другие алгоритмы компьютерной графики по аналогии с прямоугольной системой координат. Только непонятно зачем :)
Если бы не тот факт, что пиксели экрана квадратные, гексагональная сетка была бы гораздо качественнее. Нет проблем с двумя типами окрестностей. Связные цепочки клеток обязательно пересекаются (если пересекаются соответствующие кривые на плоскости). Округление точки плоскости до пикселя работает точнее. Построение меша по карте глубины даёт более регулярную треугольную сетку. И так далее…
Sign up to leave a comment.
Прямые в гексагональном растре