A*アルゴリズムのC#実装に関する簡単な説明

もちろん、主な参照アルゴリズム ドキュメントは「http://www.vckbase.com/document/viewdoc/?id=1422」ですが、実際のソース コードはここには示されていません。 A* アルゴリズムのコードを検索したところ、そのほとんどが ActionScript ソースコードでした。結局のところ、Flash を使用してデモを作成する方がはるかに便利です。しかし、Visual Studio が開いているので、C# 実装を記述してみましょう。

A* アルゴリズムで最も重要なことは、パスのスコアリング関数です。実際のアプリケーションでは、この機能の設計によって異なる結果が生成されます。上記の文書から、スコア F の式を簡単に理解できます。

F = H + G

もちろん、記事に記載されている簡単な方法に基づいて、H と G を計算するための次のコードを記述することもできます。

 1プライベート int G(int 親)
 2{
 3 int d = 10;
 4 d + 親を返します。
 5}
 6private int H(int x, int y, ポイント終了)
 7{
 8 戻り値 (Math.Abs​​(x - end.X) + Math.Abs​​(y - end.Y)) * 10;
 9}
経路探索計算を実行するには、この点の F、G、H 値、この点の座標、この点に到達するための前の点の座標など、マップ上の特定の点のトラバース情報の記録を保存するクラスも必要です。


 1クラス PathNode: IComparable
 2{
 3 パブリック int G;
 4 パブリック int H;
 5 パブリック int F {
 6 取得{
 7 G + H を返します。
 8 }
 9 }
 10
 11 パブリック PathNode 親;
 12 パブリックポイントポジション;
 13
 14 パブリック PathNode(ポイント pos)
 15 {
 16 this.Position = pos;
 17 this.Parent = null;
 18 this.G = 0;
 19 this.H = 0;
 20 }
 21
 22 パブリックオーバーライド文字列ToString()
 23    {
 24 Position.ToString() を返します。
 25 }
 26
 27 IComparable メンバー#region IComparable メンバー
28 パブリック int CompareTo(PathNode その他)
 29 {
 30 F - other.F を返します。
 31 }
 32 #終了領域
33}

PathNode クラスは、PathNode リストをソートするために IComparable インターフェイスを実装します。上記の記事の文章を思い出してください。「開いたリストの中で F 値が最も低いグリッドを見つけます。これを現在のグリッドと呼びます。」はい、これがこの条件の準備です。 F 値が最も低い「グリッド」を見つけるには、開いているリストを並べ替えるだけです。

実際のアルゴリズムを実装するときは、次の 3 つのコンテナ オブジェクトも準備する必要があります。

プライベートリスト unLockList = 新しいリスト（）;
プライベート辞書 lockList = 新しい辞書（）;
プライベートリスト パス = 新しいリスト（）;


最初の 2 つは、アルゴリズムに記載されている「オープン リスト」と「クローズ リスト」であり、最後の 1 つは最終的に見つかったパスです。
最後に、A* アルゴリズムを実装します。
 1公開リスト パス検索()
 2{
 3 ロックを解除します。
 4 ロックリストをクリアします。
 5 パスをクリアします。
 6 パス検索();
 7 パス.Reverse();
 8 戻りパス;
 9}
 10
 11プライベートvoid doFindPath()
 12{
 13 PathNode start = 新しい PathNode(Start);
 14 パスノード cur = start;
 15 ながら（真）
 16 {
 17 if(!lockList.ContainsKey(cur.ToString()))
 18 lockList.Add(cur.ToString(), cur);
 19 (int i = 0; i < delta.Length; i++) の場合
20 {
 21 ポイント newp = new Point(cur.Position.X + delta[i][0],
 22 cur.Position.Y + delta[i][1]);
 23 if (!canWalkOnIt(newp))
 24 継続;
 25 (lockList.ContainsKey(newp.ToString())) の場合
26 継続;
 27 if (isPointInUnlockList(newp))
 28 {
 29 パスノード ulnode = __pn;
 30 int newg = G(cur.G);
 31 (newg < ulnode.G) の場合
32 {
 33 ulnode.Parent = cur;
 34 ulnode.G = newg;
 35 }
 36 続く;
 37 }
 38 PathNode newpn = 新しいPathNode(newp);
 39 新しいpn.G = G(cur.G);
 40 newpn.H = H(newp.X, newp.Y, 終了);
 41 newpn.Parent = cur;
 42 ロックリストをアンロックします。
 43 }
 44 (unLockList.Count == 0)の場合
45 休憩;
 46 ロックを解除します。
 47 cur = unLockList[0];
 48 ロックを解除します。
 49
 50 (cur.Position.Equals(End)) の場合
51 {
 52 (cur != null) の間
53 {
 54 パスを追加します(cur);
 55 cur = cur.Parent;
 56 }
 57 休憩;
 58 }
 59 }
 60}
 61
 62プライベートPathNode__pn;
 63
 64private bool isPointInUnlockList(ポイント src)
 65{
 66 __pn = ヌル;
 67 foreach (unLockList 内の PathNode 項目)
 68 {
 69 if (item.Position.Equals(src))
 70 {
 71 __pn = アイテム;
 72 true を返します。
 73 }
 74
 75 }
 76 false を返します。
 77}
 78
 79private bool canWalkOnIt(ポイントノード)
 80{
 81 （ノード.X < 0 || ノード.Y < 0）の場合
82 は false を返します。
 83 if (node.X > 幅 - 1 || node.Y > 高さ - 1)
 84 は false を返します。
 85 GetNodeValue(node.X, node.Y) >= 0 を返します。
 86}

コメントはありませんが、考え方は上記の「A*メソッドのまとめ」と同じです。ここに再度貼り付けることはしません。ここでもう少し説明する必要があります。閉じたリストは辞書を使用します。実際、閉じたリストの目的は、次のポイントが閉じたリスト内にあるかどうかを確認することです。辞書の ContainsKey メソッドを使用する方が簡単です。結局のところ、リスト内の要素を検索するよりも、ハッシュテーブル内のキーを検索する方が高速です。

C# 実装アルゴリズムを簡略化するために、ここでは現在のポイントの上、下、左、右の 4 つの隣接するポイントのみが走査されます。上記では 8 つのポイントを移動する状況を紹介しましたが、これはそれほど複雑ではありません。唯一の問題は、斜めに移動しているかどうかを判断する必要がある G メソッドにあります。さらに、隣接する 4 つのポイントをトラバースする方法は、オフセット配列を使用して 8 つのオフセットを保存する、以前に見た AS コードの一部から取得されます。ここでは 4 つのオフセットのみが保存されます。実際のアルゴリズムでは、オフセット配列をループするのが非常に便利です (以前、この方法を使用せず、8 つの短い同様の関数呼び出しコードをコピーしたコードを見たことがありますが、これはロジックがこれほど明確ではありませんでした)。デルタ配列は次のとおりです。

プライベートint[][]デルタ = 新しいint[][]{
    新しいint[]{0,1}、
    新しいint[]{0,-1}、
    新しいint[]{1,0}、
    新しいint[]{-1,0}
 };

C# 実装で注意すべきもう 1 つの点は、4 つのオフセットの新しいポイントがオープン リストに含まれている場合、オープン リスト内の対応する PathNode の G 値を更新する必要があることです。新しい PathNode が作成され、オープン リストに追加されると、アルゴリズムに問題が発生し、無限ループに陥る可能性があります。

パス検索の結果を取得するには、PathNode リンク リスト内の各 PathNode をトラバースし、それをリストに入れて、それを逆にするだけです。マップには、ここでは int 配列が使用されます。要素が 0 未満の場合、渡すことができないことを意味します。 A* アルゴリズムによって計算された結果は最適な結果ではない可能性がありますが、スコアリング関数の助けを借りて、より少ないノードを走査できるため、その効率は依然として比較的高くなります。

最後に、デモ プロジェクト全体のファイルを投稿します。構造とコードは見栄えがよくないかもしれません。