私はサイズがLxLの正方格子を持っています。この格子では、古典的な4近傍格子または8近傍格子（対角を含む）を持つことができます。周期的境界を持つ格子上の距離
(i1,j1)と(i2,j2)の2つの点の座標が与えられているので、周期的な境界条件も考慮して、4近傍グリッドと8近傍グリッドの間の距離を計算します。
周期的境界条件がない4近傍の場合、距離はマンハッタン距離d=|i1-i2|+|j1-j2|です。 定期的な境界を考慮したい場合は、距離を何度か計算して（たとえば(i2,j2)で(i2,j2-L)）、最小限に抑えることができますが、もっと効率的な方法があると確信しています。
については、Calculate distance on a grid between 2 points（私の場合はsqrt(2)を1に置き換えます）の境界条件に関する問題は解決しません。
これらの距離の計算方法に関する擬似コードはありますか？より速く、より良い。
差分座標環状検索：対角線移動コスト1この場合
dx = Abs(x1 - x2)
if dx > L/2
dx = L - dx
similar for dy
との距離がマンハッタン距離
dist = dx + dy
として知られ、その後8近傍のケースのためのソリューションは簡単である - に新しい位置に到達するには、dxとdyのステップから最大限に実行する必要がありますが、短い方の移動は長い方の移動、つまり対角線の移動と組み合わされるため、より多くのステップは必要ありません。
dist = Max(dx, dy)
（また、DX、DY）及びHOR/VERT部分はABS（DXある（対角部分が最小であることに注意してください - 。DY）これらの式の合計が、DY DXから最大値に等しい）
優れた答え。あなたは（4つのネイバーの場合の答えが単に 'dx + dy'であることは明白ですが）言及するかもしれません。また、8ネイバーケースの正しい解にどのように到達するかについての説明は参考になります。例えば、8-ネイバーの場合、最適な解は、すべての対角ステップについて「x」と「y」の両方の方向に1つの正方形を近づけ、他のステップごとにより遠くに1ステップ近づけます。 – Patrick87
おそらく最適ではありませんが、境界条件を反映するようにリンクされた答えを修正する必要があります。「同じ行または同じ列のいずれかになるまで、目標に向かって斜めに移動する」と表示されます。境界条件では、4つの可能な対角線の方向はすべて「目標に向かって」とみなすことができます。各方向にそれを行い、分を取る。あなたはすでに4人の仲間のようにしています。 –
明確にする：「周期的な境界条件」とは、オブジェクトがグリッドの上から移動した場合、グリッドの上から移動し、その逆に移動し、グリッドの左側から移動すると、グリッドの右側に再び現れます。グリッドとその逆？また、与えられた列 '（i1、0）'と '（i1、L-1）'の上端点と下端点は区別されますが、 'と'（i1、L） 'は同じ点ですか？ –
@RoryDaulton周期的な境界では、事実上、スペースはトーラスの形をしているので、トップ・ボトムと左右がつながっています。あなたが言うように、私は '（L、L）=（0,0）'を使い、 '（i1,0）'と '（i1、L-1）'は距離1にあります。 – VictorSeven