Манхэттен Расстояние между плитками в шестиугольной сетке

Question

Для квадратной сетки евклидово расстояние между плиткой А и В составляет:

distance = sqrt(sqr(x1-x2)) + sqr(y1-y2))

Для актера, вынужденного двигаться по квадратной сетке, Манхэттенское расстояние является лучшей мерой фактического расстояния, которое мы должны пройти:

manhattanDistance = abs(x1-x2) + abs(y1-y2))

Как мне узнать манхэттенское расстояние между двумя плитками в шестиугольной сетке, как показано красной и синей линиями ниже?

Answer 1

Однажды я настроил гексагональную систему координат в игре так, чтобы ось y находилась под углом 60 градусов к оси x . Это позволяет избежать четного различия строк.

Шестиугольная сетка http://althenia.net/svn/stackoverflow/hexgrid.png?usemime=1&rev=3

Расстояние в этой системе координат:

dx = x1 - x0
dy = y1 - y0

if sign(dx) == sign(dy)
    abs(dx + dy)
else
    max(abs(dx), abs(dy))

Вы можете преобразовать ( x ', y ) из вашей системы координат в ( x , y ) в этой системе, используя :

x = x' - floor(y/2)

Так dx становится:

dx = x1' - x0' - floor(y1/2) + floor(y0/2)

Осторожнее с округлением при реализации целочисленного деления. В C для int y floor(y/2) есть (y%2 ? y-1 : y)/2.

Answer 2

Прямой ответ на этот вопрос невозможен. Ответ на этот вопрос очень сильно связан с тем, как вы организовываете свои плитки в памяти. Я использую odd-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

Для математических деталей этого решения посетите: http://www.redblobgames.com/grids/hexagons/. Вы можете получить полную библиотеку hextile по адресу: http://www.redblobgames.com/grids/hexagons/implementation.html

Answer 3

Если вам нужно прямое расстояние:

double dy = y2 - y1;
double dx = x2 - x1;
// if the height is odd
if ((int)dy & 1){
    // whether the upper x coord is displaced left or right
    // depends on whether the y1 coordinate is odd
    dx += ((y1 & 1) ? -0.5 : 0.5);
}
double dis = sqrt(dx*dx + dy*dy);

Я пытаюсь сказать, что если dy четное, то это просто прямоугольное пространство.Если dy нечетно, то положение верхнего правого угла составляет 1/2 единицы влево или вправо.

Answer 4

Я предполагаю, что вам нужно евклидово расстояние в плоскости между центрами двух плиток, которые идентифицированы, как показано на рисунке. Я думаю, что это можно получить из рисунка. Для любых x и y вектор от центра элемента мозаичного изображения (x, y) к центру элемента мозаичного изображения (x + dx, y) равен (dx, 0). Вектор от центра тайла (x, y) и (x, y + dy) равен (-dy / 2, dy * sqrt (3) / 2). Простое сложение векторов дает вектор (dx - (dy / 2), dy * sqrt (3) / 2) между (x, y) и (x + dx, y + dy) для любых x, y, dx, и ок. Тогда общее расстояние является нормой вектора: sqrt ((dx - (dy / 2)) ^ 2 + 3 * dy * dy / 4)

Answer 5

Если вы определяете различные шестиугольники как график, вы можете получить кратчайший путь от узла A к узлу B. Поскольку расстояние от центров шестиугольников постоянное, установите его в качестве веса ребра.

Этовероятно, будет неэффективным для больших полей.

Answer 6

Это звучит как работа для алгоритма линии Брезенхема . Вы можете использовать это для подсчета количества отрезков, чтобы добраться от A до B, и это скажет вам путь пути.