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

Ответ 1

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

_{(источник: althenia.net)}

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

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.

Ответ 2

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

Ответ 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 единицы влево или вправо.

Ответ 4

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

Ответ 5

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

Ответ 6

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

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