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

    Данное исследование не претендует на оригинальность, я полагаю, что на самом деле изобретаю велосипед, но никаких деталей от него при (признаю, довольно поверхностном) изучении интернета мне найти не удалось.

    Понаблюдав за разнообразными игрушками, передвижение персонажей в которых производится на плоскости, вымощенной правильными шестиугольниками, меня зацепил вопрос — а как должна выглядеть прямая на такой плоскости. Собственно, задача оптимального перемещения персонажа из шестиугольника A в шестиугольник B (подразумеваю, что на плоскости нет препятствий, под оптимальным перемещением подразумеваю такое, чтобы оно происходило через наименьшее количество шестиугольников) может быть решена кучей разных способов, маршрут далеко не единственен, так же, как, впрочем, и на плоскости, покрытой квадратами. Но мне хотелось бы, чтобы маршрут был приближен к отрезку прямой, как приближено к отрезку прямой изображение, построенное по алгоритму Брезенхэма, и в то же время реализация должна быть достаточно прозрачной и простой.

    С использованием вычислений в области действительных чисел наиболее прозрачным будет следующий подход: допустим, есть координаты центров начала и конца. Допустим, уже построена часть прямой (например, поставлен начальный шестиугольный «пиксель»). От последнего построенного пикселя нужно выбрать в его окрестности (в которой находится 6 других шестиугольников) тот шестиугольник, сумма расстояний (в смысле обычной геометрии) от центра которого до начала и конца строящегося отрезка минимальна (на самом деле достаточно рассмотреть два случая — либо два нижних, либо нижний правый и правый, в зависимости от некоторого условия, которое будет описано ниже). На сам алгоритм требует вычислений в области действительных чисел, вычислений квадратных корней, чего не очень хочется делать.

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



    В каждом из шестиугольников записаны координаты — x и y — которые для удобства буду называть «растровыми» для отличия от координат точек, которые удобно называть «геометрическими».

    В процессе решения задача разбилась на два случая, условие для разделения которых я получил в процессе решения. Ниже станет понятно, почему так происходит, а пока я приведу условие. Если брать координаты начала отрезка как (0, 0), а конца как (x, y), то первый случай получается при выполнении условия x ≥ [y / 2] и, соответственно, x < [y / 2], где квадратные скобки обозначают взятие целой части. Эти условия разбивают мозаику на два неравных участка, граница которого проходит следующим образом:



    Первый случай: x ≥ [y / 2]

    Сначала приведу решение для первого случая, он, пожалуй, наиболее очевидный. Бросается в глаза, что применение алгоритма Брезенхэма «в лоб» не даст нужного эффекта. Дело в том, что в нем x растет на каждой итерации, а y при переполнении значения ошибки. Но при переходе с четной строки на нечетную одновременный рост x и у приведет к разрыву. Например, если в шестиугольнике (2, 2) увеличить обе координаты на единицу, получится шестиугольник (3, 3), не имеющая, как видно на рисунках выше, с первым общих границ. А вот если из (2, 2) перейти к точке (2, 3), а потом к (3, 3), никаких разрывов не будет. Мозаику можно деформировать следующим образом:



    А также временно изменить координаты:



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





    Длина линии (количество шестиугольников, участвующих в построении) равна x + [(y + 1) / 2] + 1. Квадратные скобки — все то же взятие целой части. Геометрически это количество точек по горизонтали плюс количество переходом с четных строк на нечетные (верхняя строка имеет номер 0, потому она четная).

    Второй случай: x < [y / 2]

    Во втором случае очевидно, что длина линии не должна превышать y + 1. В отличие от классического алгоритма Брезенхэма, этот случай не симметричен первому, однако методика аналогично — произвести описанную выше деформацию и нарисовать отрезок, но уже согласно правилам другого октета, где основные изменения происходят по оси y.





    Код на Java
    public final class Line implements Iterable<Point> {
        private final Point begin;
    
        private final int dx;
        private final int dy;
        private final int sx;
        private final int sy;
    
        public Line(final Point begin, final Point end) {
            this.begin = begin;
    
            int dx = end.x - begin.x;
            int dy = end.y - begin.y;
            if (dx < 0) {
                dx = -dx;
                sx = -1;
            } else {
                sx = 1;
            }
            if (dy < 0) {
                dy = -dy;
                sy = -1;
            } else {
                sy = 1;
            }
            this.dx = dx + (dy + 1) / 2;
            this.dy = dy;
        }
    
        @Override
        public Iterator<Point> iterator() {
            return dx > dy ? new LineIterator1() : new LineIterator2();
        }
    
        private final class LineIterator1 implements Iterator<Point> {
            private int x = 0;
            private int y = 0;
            private int error = 0;
    
            @Override
            public boolean hasNext() {
                return x <= dx;
            }
    
            @Override
            public Point next() {
                if (x > dx)
                    return null;
                Point point = new Point(begin.x + (x - (y + 1) / 2) * sx, begin.y + y * sy);
                x++;
                if (x <= dx) {
                    error += dy;
                    if (2 * error >= dx) {
                        y++;
                        error -= dx;
                    }
                }
                return point;
            }
    
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        }
    
        private final class LineIterator2 implements Iterator<Point> {
            private int x = 0;
            private int y = 0;
            private int error = 0;
    
            @Override
            public boolean hasNext() {
                return y <= dy;
            }
    
            @Override
            public Point next() {
                if (y > dy)
                    return null;
                Point point = new Point(begin.x + (x - (y + 1) / 2) * sx, begin.y + y * sy);
                y++;
                if (y <= dy) {
                    error = error + dx;
                    if (2 * error >= dy) {
                        error -= dy;
                        x++;
                    }
                }
                return point;
            }
    
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        }
    }
    


    Класс Point
    public final class Point {
        public final int x;
        public final int y;
    
        public Point(final int x, final int y) {
            this.x = x;
            this.y = y;
        }
    }



    Еще раз повторюсь — я допускаю, что это изобретение велосипеда, и прошу прощения за отнятое время в таком случае.
    Share post

    Comments 23

      0
      Вообще говоря, в последнем случае совершенно неочевидно, зачем персонажу дергаться вправо-влево, когда путь точно такой же длины получится сначала при движении пол-пути на «юго-восток», и потом еще пол-пути на «юго-запад»? Обычно на смену направления тоже какие-то time-pointы закладываются.
        +2
        В первом случае тоже можно пройти по горизонтали до определенной точки, потом спуститься на «юго-восток». Путей, реализующих минимальное расстояние, может быть много, мне был интересен путь, близкий к геометрической прямой. Если учитывать время смены направлений, задача становится тривиальной — на такой плоскости из любого пункта A в любой пункт B при отсутствии препятствий существует до двух минимальных по времени путей с максимум одной сменой направления. Это как раз маршруты, ограничивающие «пучок» оптимальных.
          +2
          Я был бы крайне удивлен, если бы мои юниты, посланные строго вниз, пошли бы по описанной вами траектории…
            0
            Но в любой гексагональной игре (например, в «Героях») они так и пойдут!
              0
              Разум игрока смущает путь такой.
                0
                А пусть этот путь не читает чужие мысли…
          0
          Если взять косоугольную систему координат:
           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);
                      }
                  }
          

          По крайней мере, мне его обмануть не удалось.
            –1
            Так даже лучше (не проверял)

                    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);
                        }
                    }
              –1
              Тогда уж так (тоже не проверял) :)
                      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);
                          }
                      }
              
                –1
                согласен (даже не буду проверять)
                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);
                            }
                        }
                  –1
                  Если оптимизировать дальше, то можно убрать вычитание единицы и переменную 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);
                  
                    –1
                    без комментариев! только код. только хардкор! (я думаю мы тут «оптимизируем» на си)
                      –1
                      я думаю мы тут «оптимизируем» на си

                      Кстати, не факт. Далеко не очевидно, что будет быстрее —
                          int ay=(dy>>31)-(dx>>31);
                      

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

                      — хоть для C, хоть для C#, хоть для других языков. В зависимости от компилятора и процессора результаты могут быть любыми.
                      А комментарий нужен, чтобы последователи не пытались повысить читабельность, заменив сдвиг на деление: это привело бы к ухудшению качества полученных прямых (а в некоторых случаях, возможно, и к зацикливанию).
                        –1
                        так стоп. я играю в «возьмём мутно написаный алогритм и сделаем его ещё мутней».
                        то есть оптимизация здесь совсем в кавычках и о скорости речи нет. только о всё большей нечитаемости кода.
                          –1
                          А я, наоборот, стараюсь увеличить скорость. Или, по крайней мере, уменьшить число и «вес» сишных операторов. Нечитаемость возникает сама собой — до определенного предела, пока в результате оптимизации не отсечётся всё лишнее, и не проявится истинная суть алгоритма.
                            –1
                            лол чо ;) я никогда не буду основываться исключительно на предположениях. я никогда не буду основываться исключительно на предположениях. я никогда не буду основываться исключительно на предположениях.
            +4
            Почитайте отличную статью про гексогональные сетки: www.redblobgames.com/grids/hexagons/
            Там в том числе обсуждется тема прямых линий.
              0
              Спасибо огромное. Там, я бы сказал, обсуждается всё что можно обсудить про шестиугольники :)

              Кстати, это продолжение более лаконичной и не такой интерактивной статьи, которую можно использовать для сравнения разных сеток (треугольник, квадрат, гексагон):
                0
                Спасибо! С удовольствием посмотрю. Заметное сходство иллюстраций :)
                0
                Мне понравилась статья. Возникла мысль, что для гексагональной и треугольной систем координат можно также разработать алгоритмы заливки многоугольников, отсечения отрезков, построения окружностей с помощью алгоритма Брезенхэма и другие алгоритмы компьютерной графики по аналогии с прямоугольной системой координат. Только непонятно зачем :)
                  0
                  Если бы не тот факт, что пиксели экрана квадратные, гексагональная сетка была бы гораздо качественнее. Нет проблем с двумя типами окрестностей. Связные цепочки клеток обязательно пересекаются (если пересекаются соответствующие кривые на плоскости). Округление точки плоскости до пикселя работает точнее. Построение меша по карте глубины даёт более регулярную треугольную сетку. И так далее…
                    0
                    Вот интересно, а существуют ли экраны с гексагональной пиксельной сеткой?
                      0
                      Раньше все экраны были такими. Правда, доступа к отдельным пикселям не было — только к тройкам RGB. А решетка этих троек была уже квадратной.

                Only users with full accounts can post comments. Log in, please.