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

Понаблюдав за разнообразными игрушками, передвижение персонажей в которых производится на плоскости, вымощенной правильными шестиугольниками, меня зацепил вопрос — а как должна выглядеть прямая на такой плоскости. Собственно, задача оптимального перемещения персонажа из шестиугольника 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.

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

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

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