Прямые в гексагональном растре

[Delsian]

Вообще говоря, в последнем случае совершенно неочевидно, зачем персонажу дергаться вправо-влево, когда путь точно такой же длины получится сначала при движении пол-пути на «юго-восток», и потом еще пол-пути на «юго-запад»? Обычно на смену направления тоже какие-то time-pointы закладываются.

[Anarchist]

В первом случае тоже можно пройти по горизонтали до определенной точки, потом спуститься на «юго-восток». Путей, реализующих минимальное расстояние, может быть много, мне был интересен путь, близкий к геометрической прямой. Если учитывать время смены направлений, задача становится тривиальной — на такой плоскости из любого пункта A в любой пункт B при отсутствии препятствий существует до двух минимальных по времени путей с максимум одной сменой направления. Это как раз маршруты, ограничивающие «пучок» оптимальных.

[soulburner]

Я был бы крайне удивлен, если бы мои юниты, посланные строго вниз, пошли бы по описанной вами траектории…

[Mercury13]

Но в любой гексагональной игре (например, в «Героях») они так и пойдут!

[Anarchist]

Разум игрока смущает путь такой.

[Mrrl]

А пусть этот путь не читает чужие мысли…

[Mrrl]

Если взять косоугольную систему координат:

 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);
            }
        }

По крайней мере, мне его обмануть не удалось.

[dooreelkow]

Так даже лучше (не проверял)

        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);
            }
        }

[Mrrl]

Тогда уж так (тоже не проверял) :)

        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);
            }
        }

[dooreelkow]

согласен (даже не буду проверять)

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);
            }
        }

[Mrrl]

Если оптимизировать дальше, то можно убрать вычитание единицы и переменную z, а сравнение в цикле заменить на сравнение с нулём:

        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);

[dooreelkow]

без комментариев! только код. только хардкор! (я думаю мы тут «оптимизируем» на си)

[Mrrl]

я думаю мы тут «оптимизируем» на си

Кстати, не факт. Далеко не очевидно, что будет быстрее —

    int ay=(dy>>31)-(dx>>31);

или

    int ay=(dy>=0)-(dx>=0);

— хоть для C, хоть для C#, хоть для других языков. В зависимости от компилятора и процессора результаты могут быть любыми.
А комментарий нужен, чтобы последователи не пытались повысить читабельность, заменив сдвиг на деление: это привело бы к ухудшению качества полученных прямых (а в некоторых случаях, возможно, и к зацикливанию).

[dooreelkow]

так стоп. я играю в «возьмём мутно написаный алогритм и сделаем его ещё мутней».
то есть оптимизация здесь совсем в кавычках и о скорости речи нет. только о всё большей нечитаемости кода.

[Mrrl]

А я, наоборот, стараюсь увеличить скорость. Или, по крайней мере, уменьшить число и «вес» сишных операторов. Нечитаемость возникает сама собой — до определенного предела, пока в результате оптимизации не отсечётся всё лишнее, и не проявится истинная суть алгоритма.

[dooreelkow]

лол чо ;) я никогда не буду основываться исключительно на предположениях. я никогда не буду основываться исключительно на предположениях. я никогда не буду основываться исключительно на предположениях.

[Megas]

Почитайте отличную статью про гексогональные сетки: www.redblobgames.com/grids/hexagons/
Там в том числе обсуждется тема прямых линий.

[Devgru]

Спасибо огромное. Там, я бы сказал, обсуждается всё что можно обсудить про шестиугольники :)

Кстати, это продолжение более лаконичной и не такой интерактивной статьи, которую можно использовать для сравнения разных сеток (треугольник, квадрат, гексагон):

[Anarchist]

Спасибо! С удовольствием посмотрю. Заметное сходство иллюстраций :)

[KvanTTT]

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

[Mrrl]

Если бы не тот факт, что пиксели экрана квадратные, гексагональная сетка была бы гораздо качественнее. Нет проблем с двумя типами окрестностей. Связные цепочки клеток обязательно пересекаются (если пересекаются соответствующие кривые на плоскости). Округление точки плоскости до пикселя работает точнее. Построение меша по карте глубины даёт более регулярную треугольную сетку. И так далее…

[KvanTTT]

Вот интересно, а существуют ли экраны с гексагональной пиксельной сеткой?

[Mrrl]

Раньше все экраны были такими. Правда, доступа к отдельным пикселям не было — только к тройкам RGB. А решетка этих троек была уже квадратной.