4

A* 検索アルゴリズムの実装を作成しました。問題は、私が現在使用しているヒューリスティックが正方形のグリッドでのみ正確に機能することです。私のマップは等角図であるため、ヒューリスティックは実際のマップのレイアウトを考慮していないため、セル間の距離が考慮されていません。

更新:大規模なログ記録と分析の後 (平凡さを理解しようとして多くの時間を費やしていると読んでください)、現在のヒューリスティックが非常にうまく機能するという結論に達しましたが、1 つの小さな例外があります。斜め移動。

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const
{
    int diagonal = std::min(abs(coord.x-goal->position.x), abs(coord.y-goal->position.y));
    int straight = (abs(coord.x-goal->position.x) + abs(coord.y-goal->position.y));
    return 14 * diagonal + 10 * (straight - 2 * diagonal);
}

これは、アイソメsqrt(2)マップ上で実際には斜めの移動よりも何倍もコストがかかる直線の移動が、斜めの移動として計算されることを意味します。問題は、アイソメ レイアウトで正しい結果が得られるように現在のヒューリスティックを変更するにはどうすればよいかということです。を単純に置き換えたり、その逆を行ったりするだけでは機能しません。diagonalstraight

地図のレイアウト

4

2 に答える 2

4

試してみる1つのことは、すべての計算でアイソメ座標から正方形のグリッド座標セットに変換することです。

0,0がマップのルートのままであると言います。0,1は同じままで、1,2は0,2になります。1,3は0,3になります。2,3は1,4になります。3,3は2,5になります。0,2は-1,1になります。など。これにより、座標とヒューリスティックが再び機能するように、正方形のグリッドに戻ります。

Y座標はY+sourceXオフセットになります（3,3はx = 2にあるため、2,5になります）。sourceXを数学的に見つけることは、それ自体がより困難であることを証明しています。

[意識の流れ; 無視]Y= 0でのアイソメ座標は、ソースXに対して正確です。したがって、ソースXを計算するには、「Y回左/上に移動」する必要があります。これにより、Y/2の変化が相殺されます。X座標で切り捨てられます。大まかに言うと、正方形の座標は次のようになります。

sourceX = X - Y/2
sourceY = Y + sourceX

ここで、sourceXとsourceYは、通常の正方形グリッドの座標です。Y/2は整数演算/切り捨てです。

したがって、理論的には、これは次のようになります。

double DistanceToEnd(Point at, Point end)
{
    Point squareStart = squarify(at);
    Point squareEnd = squarify(end);
    int dx=squareStart.X-squareEnd.X;
    int dy=squareStart.Y-squareEnd.Y;
    return Math.Sqrt(dx*dx+dy*dy);
}
Point squarify(Point p1)
{
     return new Point(p1.X-p1.Y/2, p1.Y+(p1.X-p1.Y/2));
}

新しい質問に基づいて更新します。

あなたがdistance（3,2; 3,3）<（distance（2,3; 3,3）= distance（3,1; 3,3））;を取得しようとしていると仮定します。以下が機能するはずです:(C＃から翻訳;タイプミスは存在しないことが保証されていません）

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const
{
    int cx=coord.x - coord.y/2;
    int cy=coord.y + cx;
    int gx=goal->position.x - goal->position.y/2;
    int gy=goal->position.y + gx;
    int diagonal = std::min(abs(cx-gx), abs(cy-gy));
    int straight = (abs(cx-gx) + abs(cy-gy));
    return 14 * diagonal + 10 * (straight - 2 * diagonal);
}

編集：恐ろしいタイプミスを修正しました....もう一度。

于 2009-08-12T15:12:12.567 に答える
-1

ここでAmitは、「六角形のマンハッタン距離」を計算します。そのC++コード、そして私はそれを保証することはできませんが、Amitは私が以前にゲーム開発のために聞いた名前です。

六角形のマンハッタン距離は、適切なヒューリスティックに適している必要があります。

編集：ハイパーリンクの構文を逆にしました。

于 2009-08-12T15:15:45.693 に答える