Расчет расстояния по шестиугольной сетке

Ответ 1

Спасибо @user2709663 и @jonathankoren за ответы. Я трачу много времени на ваши ответы, но обнаружил, что у обоих есть некоторые проблемы. Или, по крайней мере, тип сетки, рассматриваемый для этих ответов, четко не оговаривается. Тем не менее, я нашел очень хороший учебник и реализацию кода этой проблемы вместе с библиотекой для управления шестнадцатеричной сеткой по адресу: http://www.redblobgames.com/grids/hexagons/ (библиотека код: http://www.redblobgames.com/grids/hexagons/implementation.html). Я также реализую версию кода расстояния для вертикальной компоновки "нечетного-q" в формате matlab следующим образом:

function f = offset_distance(x1,y1,x2,y2)
    ac = offset_to_cube(x1,y1);
    bc = offset_to_cube(x2,y2);
    f = cube_distance(ac, bc);
end

function f = offset_to_cube(row,col)
    %x = col - (row - (row&1)) / 2;
    x = col - (row - mod(row,2)) / 2;
    z = row;
    y = -x-z;
    f = [x,z,y];
end

function f= cube_distance(p1,p2)
    a = abs( p1(1,1) - p2(1,1));
    b = abs( p1(1,2) - p2(1,2));
    c = abs( p1(1,3) - p2(1,3));
    f =  max([a,b,c]);
end

Вот код тестирования matlab

sx = 6;
sy = 1;
for i = 0:7
    for j = 0:5
        k = offset_distance(sx,sy,i,j);
        disp(['(',num2str(sx),',',num2str(sy),')->(',num2str(i),',',num2str(j),')=',num2str(k)])
    end
end

Ответ 2

Если вы использовали систему координат, которая идет по зерну гексов в двух направлениях, вы могли бы использовать:

distance = max(
     abs(dest.y - start.y),     
     abs(dest.x - start.x),
     abs((dest.x - dest.y)*-1 - (start.x - start.y)*-1)
)

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

straight.y = squiggle.y
straight.x = ciel(squiggle.y / -2) + squiggle.x

Итак, решение для расстояния с использованием этой системы уравнений дает вам:

distance = max(
     abs(dest.y - start.y),     
     abs(ceil(dest.y / -2) + dest.x - ceil(start.y / -2) - start.x),
     abs(-dest.y - ceil(dest.y / -2) - dest.x + start.y  + ceil(start.y / -2) + start.x)
)

Это даст вам расстояние Манхэттена между двумя гексами, используя только их координаты (предположим, что я не делал никаких опечаток, переносящих x и y, так как ваша сетка повернута на 90 градусов от моей). Однако вы должны купить cookie для моего учителя средней школы, чтобы он работал, иначе я испортил бы дистрибутивную собственность.

Примечание. Может потребоваться перезагрузка для работы с отрицательными координатами, я не проверял.

Ответ 3

Чтобы найти кратчайший путь между двумя гексами:

• Начиная с одного гексагона,
• В разных строках следуйте по диагонали по отношению к другой строке.
• В то же время, идите прямо к другому шестнадцатеричному.

Позвольте называть разницу в направлении x dx и разности в направлении y dy. Если dy / 2 > dx, вам не нужно делать второй шаг, поэтому расстояние просто dy. В противном случае расстояние dy + (dx - dy / 2). Если я не ошибся.

Ответ 4

Неверный принятый ответ. Первоначально я подозревал это, когда упоминал использование ортогональных координат на неортогональных осях, но запуск кода против моего собственного решения показывает, что более высокая оценка расстояний.

Фактическое правильное решение:

def hexDistance(start, dest):
  if (start.x == dest.x):
    return abs(dest.y - start.y)
  elif (start.y == dest.y):
    return abs(dest.x - start.x)
  else:
    dx = abs(dest.x - start.x)
    dy = abs(dest.y - start.y)
    if start.y < dest.y:
      return dx + dy - int(math.ceil(dx / 2.0))
    else:
      return dx + dy - int(math.floor(dx / 2.0))

Здесь используется шестнадцатеричное представление:

        ------        
 ------  0, +1 ------ 
 -1, +1 ------ +1, +1  
 ------  0,  0 ------ 
 -1,  0 ------ +1,  0  
 ------  0, -1 ------ 
        ------        

 --------------------------
| -1, +1 |  0, +1 | +1, +1 |
|--------------------------
| -1,  0 |  0,  0 | +1, 0  |
|--------------------------|
|        |  0, -1 |        |
 -------------------------- 

Ответ 5

M H Rasel связал этот пост в своем предыдущем ответе: Шестиугольные сетки. После этой превосходной должности я понял, что мне нужны координаты куба; что дает самый простой способ рассчитать расстояния. Вот фрагмент кода в Kotlin:

data class Point(val x: Int, val y: Int, val z: Int) {

    fun distance(b: Point): Int {
        return (abs(x - b.x) + abs(y - b.y) + abs(z - b.z)) / 2
    }

}

var x = 0
var y = 0
var z = 0

val p1 = Point(x, y, z)    // starting position

val steps = "ne,ne,ne".split(",")    // go to North-East 3 times

for (direction in steps) {
    when(direction) {
        "n"  -> { ++y; --z }
        "ne" -> { ++x; --z }
        "se" -> { ++x; --y }
        "s"  -> { --y; ++z }
        "sw" -> { --x; ++z }
        "nw" -> { ++y; --x }
    }
}

val p2 = Point(x, y, z)    // we arrived here
val dist = p1.distance(p2)    // the result is here (in this example: 3)

Изменить: я предполагаю решетку с плоским верхом.

Ответ 6

Вот субоптимальный, но не TOO субоптимальный (должен быть O (n)) алгоритм:

Сначала создайте функцию, которая определяет, будет ли шестиугольник в определенном месте в гексагонной сетке пересекать отрезок линии с определенной начальной точкой и конечной точкой (например, вычислить шесть строк, из которых она состоит, и сделать что-то вроде: http://alienryderflex.com/intersect/.)

Во-вторых, создайте функцию, которая определяет, какой шестиугольник на шестнадцатеричной сетке находится в точке.

Теперь напишите свой алгоритм следующим образом:

• Сохраните список всех шестиугольников, которые сегмент линии перекрыл до сих пор
• Начните с шестиугольника, что начало сегмента линии находится в
• Для каждого шестиугольника, окружающего последнее перекрывающееся, если оно отсутствует в списке, посмотрите, пересекает ли сегмент lin этот шестиугольник. Если это так, сделайте это новым заголовком списка и повторите
• Если нам не хватает шестиугольников для проверки, верните список, который мы создали

Я бы предположил, что вы проверите случай, когда сегмент линии точно параллелен и работает вдоль шва между шестиугольниками, чтобы увидеть, получаете ли вы шестиугольники с одной стороны, с обеих сторон или нет (и, таким образом, останавливаетесь).

Ответ 7

Если плитки на сетке потенциально могут быть заблокированы, вас интересует алгоритм решения лабиринта A * (или A-Star): http://labs.makemachine.net/2010/03/a-star-maze-solver/

Механизм, используемый в этом видео, применяется к сетке квадратов, но с едва ли дополнительным кодированием можно применить его к шестиугольной сетке. Для каждой плитки решатель знает, какие плитки нужно попробовать, потому что плитки хранят указатели на окружающие плитки. В сетке квадратов каждая плитка хранит максимум 4 указателя ( максимум, потому что они хранят только указатели для разблокированных плит), и единственная разница в вашем случае будет содержать максимум 6 указателей.

Если плитки всегда пересекаются, то A * все равно наверняка выполнит свою работу, однако скорее всего будет более быстрый способ. Если я правильно истолковываю ваш вопрос, вас интересует не расстояние, а количество целых чисел от числа гексов между двумя заданными гексами? Попробуйте следующее:

class Coord {
    int x;
    int y;
}

int dist(Coord hex1, Coord hex2) {
    int xSteps = Math.abs(hex1.x - hex2.x);
    int ySteps = Math.abs(hex1.y - hex2.y);

    return Math.max(xSteps, ySteps) + Math.abs(xSteps - ySteps);
}

Почему вы можете спросить? Этот вопрос заключается в определении того, сколько раз мы должны перемещать по вертикали или по горизонтали в отличие от по диагонали. Мы хотим как можно больше передвигаться по диагонали, иначе мы не будем в курсе наших расстояний. Math.abs(xSteps - ySteps) - количество недиагональных движений, которые мы должны сделать. Добавьте к этому большее расстояние x и y, и вы закончили.

Ответ 8

Если ваша гексагональная черепица имеет направления: N, NE, SE, S, SW, NW, как в Advent of Code 2017 problem 11 и вы компенсируете цель быть в (0,0) (вычитав свою позицию из цели заранее), для меня работала следующая логика:

def distance(self):
    # Take diagonal steps towards self.x == 0
    steps = abs(self.x)
    # y moves closer to 0 by steps because moving diagonal, but never moving too far
    if self.y > 0:
        # Might still be positive, but never negative
        y = max(self.y - steps, 0)
    else:
        # Might still be negative, but not positive
        y = min(self.y + steps, 0)
    # You move 2 positions north/south by a single move so divide y by 2
    return abs(y) // 2 + abs(steps)

Я думаю, что это может сработать для шестнадцатеричной сетки с направлениями EAST и WEST вместо СЕВЕРНОГО и ЮГО -НОГО, как ваш, просто переключив роли x и y. В этом случае вы будете двигаться в направлении self.y == 0 по диагонали (при необходимости) и т.д.