22

正方形グリッドの場合、タイルAとBの間のユークリッド距離は次のとおりです。

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

正方形のグリッドに沿って移動するように制約されているアクターの場合、マンハッタン距離は、移動する必要のある実際の距離のより良い尺度です。

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

下の赤と青の線で示されているように、六角形のグリッド内の2つのタイル間のマンハッタン距離を取得するにはどうすればよいですか？

ここに画像の説明を入力してください

4

6 に答える 6

47

私はかつて、y軸がx軸に対して60度の角度になるように、ゲームで六角形の座標系を設定しました。これにより、奇数行と偶数行の区別が回避されます。

六角形のグリッド
（出典：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。

于 2011-02-22T23:26:02.543 に答える
2

図に示されているように識別される2つのタイルの中心間の平面内のユークリッド距離が必要であると想定します。これは図から導き出せると思います。任意のxおよびyについて、タイルの中心（x、y）からタイルの中心（x + dx、y）までのベクトルは（dx、0）です。タイル（x、y）と（x、y + dy）の中心からのベクトルは（-dy / 2、dy * sqrt（3）/ 2）です。単純なベクトル加算により、任意のx、y、dx、とdy。その場合、合計距離はベクトルのノルムになります。sqrt（（dx-（dy / 2））^ 2 + 3 * dy * dy / 4）

于 2011-02-22T22:40:52.147 に答える
2

直線距離が必要な場合：

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単位です。

于 2011-02-22T22:44:08.877 に答える
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/をご覧ください。完全な六角形のライブラリは、http：//www.redblobgames.com/grids/hexagons/implementation.htmlで入手できます。

于 2016-11-12T18:09:03.953 に答える
1

これはブレゼンハムの線アルゴリズムの仕事のように聞こえます。これを使用して、AからBに到達するセグメントの数を数えることができます。これにより、パスの距離がわかります。

于 2011-02-22T22:38:50.037 に答える
1

さまざまな六角形をグラフとして定義すると、ノードAからノードBへの最短経路を取得できます。六角形の中心からの距離は一定であるため、それをエッジの重みとして設定します。

ただし、これは大きなフィールドではおそらく非効率的です。

于 2011-02-22T22:46:43.277 に答える