プロフィール

Na-7

Author:Na-7
SE(システムエンジニア)として約15年間システム系ソフト会社を勤めあげ、2008年3月退社。現在、ゲーム制作会社設立を目指して活動中。


アクセスカウンター


最新記事


最新コメント


最新トラックバック


月別アーカイブ


カテゴリ


DATE: CATEGORY:スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
DATE: CATEGORY:三国志軍記開発
最短経路の例題
最短経路の例題
エースター法で前回の例題を探索するサンプルを作成した。エースター法はダイクストラ法より効率が良いとのこと。



◎概要調査

今回は、ダイクストラの改良版であるエースターアルゴリズムについて調査します。

こちらによると、エースターは『ダイクストラ法を推定値が小さい方ものから順に探索するよう改良したもの』とあります。‘ヒューリスティック関数’というものがポイントらしいのですが、こちらの記述ではよくわかりません。

次に参照したのはこちら。読みやすい文章なので、何となくわかったような気になりましたが、「ではこの文章を具体的にコード化できるか?」と自身に問いかけると、やはりまだあいまいな部分が多いようです(汗)



◎ヒューリスティック関数とは?

まず大前提として、以下の式があります。

f*(n) = g*(n) + h*(n)

これを変形すると、以下のようになりますよね?

ヒューリスティック関数:h*(n)
h*(n) = f*(n) - g*(n)

上記の数式イメージが先行するあまり、ヒューリスティック関数がなかなか理解できませんでした。ヒューリスティック関数が理解できないと、エースターは理解できません。


その後、他の資料を漁ったり1から考え直したりして、ようやく誤解に気付きました。先の数式イメージは、数学的に正しくても、ヒューリスティック関数としては不正解です。

ヒューリスティック関数の具体例は、前述の資料に記述されてました。

「地点nからゴール地点までの直線距離をh*(n)とすることが多いようです。」

ちなみに、この記述は私の脳内で「スタートからゴールまでの直線距離」と誤変換されてました(爆)



◎エースターの概要

ヒューリスティック関数を理解すると、エースターも理解できるようになりました。

例えば、ウィキペディアの

「アルゴリズムの流れ」の6-1に「また g*(n) は g*(n) = f*(n) - h*(n) で求めることができる。」

とありますが、これは

「出発点からゴールまでの直線距離 - 地点nからゴールまでの直線距離」

のようにイメージすると理解しやすいです。

また、g*(n)の値が小さい方が低コストとして優先されるので、

「地点nからゴールまでの直線距離が近い経路を優先する効果がある」

と言えそうです。


こちらの「◆A*って具体的には何なのよ?」にエースターの概要が簡潔にまとめられています。これを読んでから他の資料と組み合わせて理解すると良いでしょう。



◎サンプルが動かない?

概要は把握したので、こちらのサンプルコードを動かそうとしたのですが、コピペするとエラーになります。ソース一式をダウンロードすると、.slnファイルが開けません。XNAのバージョン違いによるものでしょうか?

ソースを解析するという選択肢もありますが、統合エディタで開けない&解説無いのでちょっと気後れします。

他のサンプルコードも探してみたのですが、見当たりません。

…うむむ、自作した方が早いかも?



◎サンプル作成

というわけで、ウィキペディアのアルゴリズムに沿ってコーディングしました。

・結果
root:F ← E ← B ← A コスト:5

おお正解!
出来たっぽいですよ!!



◎不正解1件

スタートとゴールを変えて10パターン以上試したら、1件だけ不正解がありました。

○ スタート:A、ゴール:F F ← E ← B ← A  コスト:5
○ スタート:F、ゴール:A A ← B ← E ← F  コスト:5
○ スタート:B、ゴール:F F ← E ← B  コスト:4
× スタート:F、ゴール:B B ← E ← C ← F  コスト:5

他は正しいのに、何故4番目だけ不正解になるのでしょうか?

ヒューリスティック関数に問題があるのかなぁ…ブツブツ。



◎原因判明

なかなか原因特定に至らず、最後は全変数の値の変化を1ステップずつチェックして判明したのですが、

if (this.openList.IndexOf(m) > 0)

上記コードを下記のように修正したら直りました。

if (this.openList.IndexOf(m) != -1)

またしても、アルゴリズムと無関係のミスでした。ぐはっ!!



◎サンプルコード

サンプルコードをHPにUPしました。

A*(エースター:最短経路探索アルゴリズム)サンプル



◎次回予告

ようやくエースターのサンプルが作成できたので、次回はメインプログラムにエースターを実装します。

スポンサーサイト

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

コメント

A* のサンプルコードを書いたものです。
VisualStudio は何を使っているでしょうか?
2008 以前を使っている場合、それがエラーの原因として考えられます

こんにちは

VisualStudio 2008 です。

アニメライブラリ等の都合でまだXNA4.0に移行できず、XNA3.1を使用中ですが…やはりバージョン違いが原因だったようですね。

どうもお騒がせしました&ご連絡ありがとうございました。

コメントの投稿


管理者にだけ表示を許可する

トラックバック


この記事にトラックバックする(FC2ブログユーザー)



copyright © ゲーム制作の舞台裏 all rights reserved.Powered by FC2ブログ
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。