Pregunta Distancia de Manhattan entre mosaicos en una cuadrícula hexagonal


Para una cuadrícula cuadrada, la distancia euclidiana entre las piezas 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, 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 fichas en una cuadrícula hexagonal como se ilustra con las líneas rojas y azules a continuación?

enter image description here


18
2018-02-22 22:30


origen


Respuestas:


Una vez configuré un sistema de coordenadas hexagonales en un juego para que el yeje estaba en un ángulo de 60 grados a la X-eje. Esto evita la distinción de filas impares.

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

Usted puede convertir (X', y) desde su sistema de coordenadas hasta (X, y) en este usando:

x = x' - floor(y/2)

Asi que dx se convierte en:

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

Cuidado al redondear al implementar esto usando la división de enteros. En C para int y  floor(y/2) es (y%2 ? y-1 : y)/2.


38
2018-02-22 23:26



Supongo que quiere la distancia euclidiana en el plano entre los centros de dos fichas que se identifican como se muestra en la figura. Creo que esto puede derivarse de la figura. Para cualquier xey, el vector del centro de la losa (x, y) al centro de la losa (x + dx, y) es (dx, 0). El vector del centro de la losa (x, y) y (x, y + dy) es (-dy / 2, dy * sqrt (3) / 2). Una simple adición vectorial 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)


1
2018-02-22 22:40



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 estoy tratando de decir es, si dy es parejo, 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.


1
2018-02-22 22:44



Una respuesta directa para esta pregunta no es posible. La respuesta a esta pregunta está muy relacionada con la forma en que organizas tus fichas 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 de 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 detalles matemáticos de esta visita de solución: http://www.redblobgames.com/grids/hexagons/ . Puede obtener una biblioteca completa de hextile en: http://www.redblobgames.com/grids/hexagons/implementation.html


1
2017-11-12 18:09



Esto suena como un trabajo para el Algoritmo de línea Bresenham. Puede usar eso para contar la cantidad de segmentos que va a obtener de A a B, y eso le indicará la distancia de la ruta.


0
2018-02-22 22:38



Si defines los diferentes hexágonos como un gráfico, puedes obtener el camino más corto desde el nodo A hasta el nodo B. Dado que la distancia desde los centros del hexágono es constante, establece eso como el peso del borde.

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


0
2018-02-22 22:46