-2

私はこれが完璧ではないことを知っています。ボードは 19 x 19 の配列で、1 は空の正方形を表します。今は真っ直ぐ下って西へ。その左側に壁がある場合、スタック オーバーフローが発生します。その理由は、壁を「登ろう」とすると、何度も何度も下に戻ってクラッシュするからです。ただし、これを修正しても、最短パスは見つかりません。私が見つけた解決策は、パスがいくつ離れているかを数えるのではなく、パスを描きます。

private static int turnsforshortestmove(Vector2 location, int[,] board, int endrow)
{
    if (location.Y == endrow)
    {
        return 0;
    }
    if (board[(int)location.X, (int)location.Y - 1] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X, location.Y - 2), board, endrow);
    }
    else if (board[(int)location.X - 1, (int)location.Y] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X - 2, location.Y), board, endrow);
    }
    else if (board[(int)location.X, (int)location.Y + 1] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X, location.Y + 2), board, endrow);
    }
    else if (board[(int)location.X + 1, (int)location.Y ] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X + 2, location.Y), board, endrow);
    }

    return 0;
}
4

1 に答える 1

0

これは経路探索の問題です。SJuan76 がすでに示唆しているように、ダイクストラのアルゴリズムは、この種の問題の出発点として最適です。

直交移動 (上、下、左、右) のみが許可され、各移動のコストが同じである、開いた/ブロックされた正方形のグリッド スタイル マップを考えると、1 つのグリッド セルから別のグリッド セルへのパスを見つけるには、かなり単純ですが時間がかかります。可能な動きの反復を消費します。

基本的な原則は、可能な動きのリストを作成し、最短経路を探してそれぞれを処理することです。各ステップで、現在の位置から可能な移動を確認し、ターゲットの場所が以前に移動されたかどうかを確認し、まだ確認されていない場所、または前の確認よりも早く移動できる場所を追加します。処理するリスト。目的の場所が見つかるまで、リストを処理し続けます。

これをどのように行うかが楽しい部分です。

これを開始するために必要なことがいくつかあります。

  • グリッド内の任意の点から可能な動きを見つける方法。
  • すでに訪れた場所と、どの場所から訪れたかを追跡する方法。
  • 次にチェックするのに最適な場所をすばやく見つける方法。

単純な正方形のグリッドから作業していて、直交する移動 (上下左右) のみを行っており、すべての移動のコストが同じであることを考えると、役に立たない概念のいくつかを大まかに説明できます。あなたのシナリオで。そう...

  1. 2 つのコレクションを作成します。1 つは への場所のリストをprocess格納するためのもので、もう 1 つはvisited場所のリストを格納するためのものです。

  2. 出発点をprocessリストに追加します。

  3. processリストが空でない間

    1. processリストから次の場所を取得する
    2. 現在の場所がターゲットの場合、パスを形成する以前の場所のリストを返します。
    3. visitedリスト内の移動を除外して、その場所から利用可能な移動を検索します
    4. 未訪問のすべての可能な動きをprocessリストにプッシュします

最終的には、まだチェックされていない可能性のある動きがなくなるか、ターゲット ポイントが見つかるかのいずれかが起こります。

これは、前回このように経路探索を行ったときに使用したものと同様の構造です。

public struct SearchNode
{
    public Vector2 position;
    public SearchNode prior;
    public int TotalCost;
}

リストはvisited辞書で行うことができます:

var visited = new Dictionary<Vector2, SearchNode>();

リストはprocess、一連のコレクション型で実行できます。最も単純な形式は次のとおりです。

var process = new Queue<Vector2>();

うまくいけば、私はあなたに手始めに何かを与えました.

于 2013-10-31T05:47:17.177 に答える