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

Question

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

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

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

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

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

Answer 1

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

http://althenia.net/svn/stackru/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)

Осторожнее с округлением при реализации целочисленного деления. В С для int yfloor(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

Я предполагаю, что вы хотите евклидово расстояние в плоскости между центрами двух плиток, которые идентифицированы, как вы показали на рисунке. Я думаю, что это можно получить из рисунка. Для любых 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 4

Если вы хотите прямолинейное расстояние:

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 5

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

Answer 6

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

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