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

Однажды я установил в игре гексагональную систему координат так, чтобы ось 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.

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

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

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

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

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

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

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