私がやろうとしているのは、六角形グリッド上の2点の間にいくつの六角形があるかを見つけることです。オンラインで数式を検索しようとしましたが、使用している16進グリッドのタイプに一致する数式を見つけることができませんでした。
六角グリッドは、同じ座標系で次のようにレイアウトされています：http ://www.gamedev.net/index.php?app=core&module=attach§ion=attach&attach_rel_module=ccs&attach_id=1962
この座標系ではこれが不可能な場合があることは承知していますが、これは私が戻って変更する前の最後の努力です。事前にどうもありがとうございました。
ヘクスの粒子に沿って2方向に進む座標系を使用した場合は、次を使用できます。
distance = max(
abs(dest.y - start.y),
abs(dest.x - start.x),
abs((dest.x - dest.y)*-1 - (start.x - start.y)*-1)
)
ただし、使用しなかった場合は、一方向（水平）にのみ粒子に沿った波状の座標系を使用しています。幸いなことに、2つの間で変換することができます
straight.y = squiggle.y
straight.x = ciel(squiggle.y / -2) + squiggle.x
したがって、この連立方程式を使用して距離を解くと、次のようになります。
distance = max(
abs(dest.y - start.y),
abs(ceil(dest.y / -2) + dest.x - ceil(start.y / -2) - start.x),
abs(-dest.y - ceil(dest.y / -2) - dest.x + start.y + ceil(start.y / -2) + start.x)
)
これにより、座標のみを使用して2つのヘクス間のマンハッタン距離が得られます（グリッドが私のものから90度回転しているため、xとyを転置するタイプミスを行わなかったと仮定します）。ただし、中学校の代数の先生が機能するためにはCookieを購入する必要があります。そうしないと、分配法則が台無しになってしまいます。
注：負の座標を使用するには、いじる必要がある場合があります。確認しませんでした。
回答を提供してくれた@user2709663と@jonathankorenに感謝します。私はあなたの答えに多くの時間を費やしていますが、両方ともいくつかの問題があることがわかりました。または、少なくともこれらの回答で考慮されるグリッドのタイプは明確に述べられていません。ただし、http： //www.redblobgames.com/grids/hexagons/（ライブラリコード：http：//www.redblobgames）で、この問題の非常に優れたチュートリアルとコード実装、および六角形グリッドを管理するためのライブラリを見つけました。 .com / grids / hexagons /implementation.html）。また、次のように、「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
受け入れられた答えは正しくありません。非直交軸で直交座標を使用することについて言及したとき、最初はそれを疑っていましたが、私自身のソリューションに対してコードを実行すると、距離の推定が過大になっていることがわかります。
実際の正しい解決策は次のとおりです。
def hexDistance(start, dest):
if (start.x == dest.x):
return abs(dest.y - start.y)
elif (start.y == dest.y):
return abs(dest.x - start.x)
else:
dx = abs(dest.x - start.x)
dy = abs(dest.y - start.y)
if start.y < dest.y:
return dx + dy - int(math.ceil(dx / 2.0))
else:
return dx + dy - int(math.floor(dx / 2.0))
これは、16進数->正方形の表現を使用します。
------
------ 0、+ 1 ------
-1、+ 1 ------ + 1、+ 1
------ 0、0 ------
-1、0 ------ + 1、0
------ 0、-1 ------
------
--------------------------
| -1、+ 1 | 0、+ 1 | + 1、+ 1 |
| --------------------------
| -1、0 | 0、0 | + 1、0 |
| -------------------------- |
| | 0、-1 | |
--------------------------
2つのヘクス間の最短経路を見つけるには：
dxx方向の差とy方向の差をと呼びましょうdy。の場合dy / 2 > dx、ステップ2を実行する必要がないため、距離は単純にdyです。それ以外の場合、距離はdy + (dx - dy / 2)です。私が間違えない限り。
MH Raselは、以前の回答でこの投稿をリンクしました：六角形グリッド。このすばらしい投稿に続いて、私は立方体の座標が必要であることに気づきました。これにより、距離を計算する最も簡単な方法が得られます。Kotlinのコードスニペットは次のとおりです。
data class Point(val x: Int, val y: Int, val z: Int) {
fun distance(b: Point): Int {
return (abs(x - b.x) + abs(y - b.y) + abs(z - b.z)) / 2
}
}
var x = 0
var y = 0
var z = 0
val p1 = Point(x, y, z) // starting position
val steps = "ne,ne,ne".split(",") // go to North-East 3 times
for (direction in steps) {
when(direction) {
"n" -> { ++y; --z }
"ne" -> { ++x; --z }
"se" -> { ++x; --y }
"s" -> { --y; ++z }
"sw" -> { --x; ++z }
"nw" -> { ++y; --x }
}
}
val p2 = Point(x, y, z) // we arrived here
val dist = p1.distance(p2) // the result is here (in this example: 3)
編集：私はフラットトップの六角形グリッドを想定しています。
グリッド上のタイルがブロックされる可能性がある場合は、A *（またはA-Star）迷路解決アルゴリズムに関心があります：http： //labs.makemachine.net/2010/03/a-star-maze-solver/
このビデオで使用されているメカニズムは、正方形のグリッドに適用されますが、追加のコーディングがほとんどなくても、六角形のメッシュに適用できます。タイルには周囲のタイルへのポインタが格納されているため、ソルバーはすべてのタイルについて、次に試行するタイルを認識しています。正方形のグリッドでは、各タイルは最大4つのポインターを格納し（ブロックされていないタイルへのポインターのみを格納するため最大）、この場合の唯一の違いは最大6つのポインターを格納することです。
タイルが常に通過可能である場合、A *は確実に作業を完了しますが、より高速な方法がある可能性があります。私があなたの質問を正しく解釈しているなら、あなたは距離ではなく、与えられた2つのヘクスの間のヘクス数の整数カウントに興味がありますか？次のことを試してください。
class Coord {
int x;
int y;
}
int dist(Coord hex1, Coord hex2) {
int xSteps = Math.abs(hex1.x - hex2.x);
int ySteps = Math.abs(hex1.y - hex2.y);
return Math.max(xSteps, ySteps) + Math.abs(xSteps - ySteps);
}
なぜあなたは尋ねるかもしれませんか？この質問は、対角線ではなく、垂直方向または水平方向に何回移動する必要があるかを決定することです。できるだけ斜めに移動したいのですが、そうしないと距離が賢くなりません。は、私たちがしなければならない非対角移動の数です。これに、xとyの距離の大きい方を追加すると、完了です。Math.abs(xSteps - ySteps)
これは次善のアルゴリズムですが、あまりにも最適ではありません（O（n）である必要があります）。
まず、六角形グリッドの特定の場所にある六角形が特定の始点と終点の線分と交差するかどうかを判断する関数を作成します（たとえば、それが構成する6本の線を計算し、次のようにします。http： //alienryderflex.com/intersect/。）
次に、ポイントが六角形グリッド上のどの六角形にあるかを決定する関数を作成します。
次に、次のようにアルゴリズムを記述します。
六角形の間の継ぎ目に正確に平行で、それに沿って走っている線分の場合をテストして、六角形が片側、両側、またはどちらにもない（したがって停止する）かどうかを確認することをお勧めします。
六角形のタイリングに方向がある場合：コード2017の問題11のようにN、NE、SE、S、SW、NWで、目標を（0,0）にオフセットします（事前にターゲットから位置を差し引くことにより）次のようになりますロジックは私のために働いた：
def distance(self):
# Take diagonal steps towards self.x == 0
steps = abs(self.x)
# y moves closer to 0 by steps because moving diagonal, but never moving too far
if self.y > 0:
# Might still be positive, but never negative
y = max(self.y - steps, 0)
else:
# Might still be negative, but not positive
y = min(self.y + steps, 0)
# You move 2 positions north/south by a single move so divide y's by 2
return abs(y) // 2 + abs(steps)
xとyの役割を切り替えるだけで、あなたのようにNORTHとSOUTHではなく、EASTとWESTの方向の六角形グリッドで機能する可能性があると思います。その場合、self.y == 0に向かって斜めに移動します（必要な場合）など。