algorithm - paper - Manhattan Distancia entre baldosas en una cuadrícula hexagonal.

hexagon map

Question

Para una cuadrícula cuadrada, la distancia euclidiana entre las baldosas A y B es:

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

Para un actor obligado a moverse a lo largo de una cuadrícula cuadrada, la distancia de Manhattan es una mejor medida de la distancia real que debemos recorrer:

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

¿Cómo obtengo la distancia de Manhattan entre dos baldosas en una cuadrícula hexagonal como se ilustra con las líneas roja y azul a continuación?

Answer 1

Esto suena como un trabajo para el algoritmo de línea de Bresenham . Puede usar eso para contar la cantidad de segmentos que se van a pasar de A a B, y eso le indicará la distancia del camino.

Answer 2

Si define los diferentes hexágonos como un gráfico, puede obtener la ruta más corta del nodo A al nodo B. Dado que la distancia desde los centros del hexágono es constante, establezca eso como el peso del borde.

Sin embargo, esto probablemente será ineficiente para campos grandes.

Answer 3

Si quieres la distancia en línea recta:

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);

Lo que trato de decir es que, si dy es par, es solo un espacio rectangular. Si dy es impar, la posición de la esquina superior derecha es 1/2 unidad hacia la izquierda o hacia la derecha.

Answer 4

Supongo que desea la distancia euclidiana en el plano entre los centros de dos baldosas que se identifican como se muestra en la figura. Creo que esto puede derivarse de la figura. Para cualquier x e y, el vector desde el centro del azulejo (x, y) al centro del azulejo (x + dx, y) es (dx, 0). El vector del centro de la baldosa (x, y) y (x, y + dy) es (-dy / 2, dy * sqrt (3) / 2). Un simple vector de adición da un vector de (dx - (dy / 2), dy * sqrt (3) / 2) entre (x, y) y (x + dx, y + dy) para cualquier x, y, dx, y dy. La distancia total es entonces la norma del vector: sqrt ((dx - (dy / 2)) ^ 2 + 3 * dy * dy / 4)

Answer 5

Una respuesta directa para esta pregunta no es posible. La respuesta a esta pregunta está muy relacionada con la forma en que organiza los mosaicos en la memoria. Uso el diseño vertical impar-q y con el siguiente código matlab siempre me da la respuesta correcta.

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

Aquí hay un código de prueba 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

Para obtener detalles matemáticos de esta solución, visite: http://www.redblobgames.com/grids/hexagons/ . Puede obtener una biblioteca hextile completa en: http://www.redblobgames.com/grids/hexagons/implementation.html

Answer 6

Una vez configuré un sistema de coordenadas hexagonales en un juego para que el eje en y estuviera en un ángulo de 60 grados con el eje x . Esto evita la distinción de filas impares.

Cuadrícula hexagonal http://althenia.net/svn//hexgrid.png?usemime=1&rev=3

La distancia en este sistema de coordenadas es:

dx = x1 - x0
dy = y1 - y0

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

Puede convertir ( x '', y ) de su sistema de coordenadas a ( x , y ) en este usando:

x = x'' - floor(y/2)

Entonces dx convierte en:

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

Tenga cuidado con el redondeo cuando implemente esto usando división entera. En C para int y floor(y/2) es (y%2 ? y-1 : y)/2 .