私は現在、キャラクターがAIであり、リソースが配置された円形のマップにあるビデオゲームを作成しようとしています。
私は現在、この地図上の2点間の最短距離を計算しようとしていますが、私の問題は、地図が円形であるということです。たとえば、
マップが20*20で、（0,0）のimの場合、（19,0）ポイントの距離は1のみです。私はインターネットを探していましたが、私の問題に対する答えが見つかりませんでした。私はキャラクターの向き（北西南西東）にも注意を払う必要があります。彼はポイントに向かわなければならず、距離を長くする必要があります。
既存の式はありますか？
読んでくれてありがとう ！
すべての座標について、最小距離を選択し、通常どおりに使用します。
int dx = min(abs(x0-x1),20-abs(x0-x1));
int dy = min(abs(y0-y1),20-abs(y0-y1));
ユークリッド距離の場合：
double dist = sqrt(dx * dx + dy * dy);
マンハッタン距離の場合：
int dist = dx + dy;
この問題は、グラフ内の最短経路問題のままです。円形マップのエッジを追加する必要があります。
G = (V,E)どこV = {all squares}とE = { (u,v) | [(u.x + 1 % 20 = v.x or u.x -1 % 20 = v.x) and u.y == v.y] or ... [same for y] }
上記の数学表記が言うこと：Z 20（modolus 20リング）でxまたはy座標の差が1または-1である場合（そしてその場合のみ）、2つの正方形の間にエッジがあります。リングZ20はそれ自体が円形であるため、マップの円形性の問題を解決します。
このグラフがあれば、BFSを使用して、単一のソースから最短パスを見つけることができます（グラフは重み付けされていないため、ダイクストラのアルゴリズムは必要ありません）。
注：障害物がない場合は、通常の距離関数を使用して計算しますが、計算ではZフィールドの代わりにZ20リングを使用します。