プロフィール

Na-7

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


アクセスカウンター


最新記事


最新コメント


最新トラックバック


月別アーカイブ


カテゴリ


DATE: CATEGORY:スポンサー広告
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
DATE: CATEGORY:三国志軍記開発
最短経路の例題
最短経路の例題
A地点からF地点までの最短経路は、A→B→E→F(1+1+3=5)である。このような最短経路探索のアルゴリズムの1つにダイクストラ法がある。



◎要件の確認

今回は、部隊の最短移動ルートを作成します。
まず、フィールドと移動規則を確認しましょう。

・フィールドの地形種別は、256×256の配列に格納済

・部隊は縦/横/斜めの8方向に移動可能

・侵入コスト(その地形に侵入するために要する時間)は、
 地形種別と移動タイプの組み合わせで決定される

・今回はフィールド高度を考慮しない
 →フィールド高度を移動コストに反映させるか後日検討

今回は、侵入コストが最も低いルートを作成します。



◎調査開始

最短ルートの探索方法についてネットで検索すると、こちらの「最短経路探索」にA*アルゴリズムが紹介されてました。

これはダイクストラ法の改良版らしいのですが、ウィキペディアの記述だとわかりにくいので、こちらでダイクストラ法について勉強しましょう。



◎最初のサンプル

文章の内容は一応理解したので、プログラム例をC#用に若干修正して動かすと、cost[]の値は全て0になりました。
…ああ、nに0以上の値をセットする必要があるのですね。

しかし、nに適当な数値をセットすると、無限ループに陥るらしく、いつまで待っても終了しません。
どういうことでしょうか?

しばらく悩んだ末、

if (!this.used[x] && min > this.cost[x])

上記の!を削除するとプログラムは正常終了し、以下のような結果になりました。

・プログラム1

・プログラム1の実行結果
i = 0 used = False cost = 1000000000
i = 1 used = False cost = 1000000000
i = 2 used = False cost = 0
i = 3 used = False cost = 1000000000
i = 4 used = False cost = 1000000000


goalを2としたので、「i=2, cost=0」は正しいです。しかし2以外のコストが全て上限値というのはおかしいですね。また、usedの値は全く更新されません。

修正ミスか?使い方の問題か?
最も不可解なのは、元のソースにusedの値を更新するコードが存在しないことです。

その後もあれこれ悩んだのですが、埒があかないので他のサンプルを探すことにしました。



◎他のサンプル

というわけで、こちらこちらを参考に、勉強し直しました。

なるほど、未確定ノードのうち最短のノードから順次確定していくのですね。こちらの方が、途中経過の解説が詳しくてわかりやすいです。

理論とサンプルコードを理解してから、最初のサンプルを見直すと…やはり、usedの値が更新されていないことが問題と思われます。

条件式を元に戻してusedの値を更新すると…全ノードの最短コストが算出されました!

・プログラム2

・プログラム2の実行結果
i = 0 used = True cost = 0
i = 1 used = True cost = 1
i = 2 used = True cost = 3
i = 3 used = True cost = 2
i = 4 used = True cost = 2
i = 5 used = True cost = 5


i=0をゴールとした場合、上記の結果となりました。他のノードをゴールにした場合でもOKです。
(注:最初の資料のゴールと、次の資料のスタートは同義)

結局、最初のサンプルに問題があったようですね(^_^;



◎改良

最初のサンプルコードは、コスト情報を配列で管理していました。これだとメモリを無駄に喰う可能性があるので、ノードやエッジの情報を構造体で管理しましょう。また、経路情報も記憶して、最短ルートを出力しましょう。

しかしエラーが発生したり無限ループに陥ったりで、思うように動きません。何か勘違いしてる気がしてきたので、こちらで構造体について確認しました。

構造体は値型?うわー、参照型と思ってました。
自分で言うのも何ですが、プログラマーとしてかなり恥ずかしいレベルですね(汗)


構造体をクラスに変えると、問題が概ね解消しました。しかし経路情報(直前のノード番号)はまだおかしな値が散見されます。直前のノード番号を記憶しておいて、次回ループ時に設定するんじゃないのかな?

…そうか!接続先ノードのコスト情報を更新する際に、確定済みの情報を設定するんですね!

・プログラム3

・プログラム3の実行結果
i = 0 used = True cost = 0 from = 0 最短経路:A → A
i = 1 used = True cost = 1 from = 0 最短経路:B → A
i = 2 used = True cost = 3 from = 4 最短経路:C → E → B → A
i = 3 used = True cost = 2 from = 0 最短経路:D → A
i = 4 used = True cost = 2 from = 1 最短経路:E → B → A
i = 5 used = True cost = 5 from = 4 最短経路:F → E → B → A


正しい最短経路が出力できました^^



◎余談

Wikipediaの「探索」に、探索アルゴリズムが多数紹介されています。こんなにあるんですねぇ。



◎次回予告

ダイクストラ法はわりと単純なアルゴリズムだそうですが、理論とは別の問題で難儀したような(苦笑)

次回は、さらに効率的と思われるA*(エースターアルゴリズム)について調査します。

スポンサーサイト

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

コメント

リンク見てみました

はじめまして。
そもそものリンクにあるプログラムは訪問済みフラグが効いてない様ですが、気がつきましたか?nは点の数を現すので本来無限ループにはならないんだけど、同じ経路をぐりぐり辿るわけ。おわかり?

こんにちは

コメントありがとうございます。

一応確認させて頂きたいのですが、「そもそものリンク
にあるプログラム」とは

http://www.ss.cs.meiji.ac.jp/CCP024.html

上記のブログで、「訪問済みフラグ」とは

used[x]

という認識でよろしいでしょうか?

もしそうであれば、本文の「◎他のサンプル」で記述したように、このフラグが更新されない事が問題と思いました。

コメントの投稿


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

トラックバック


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



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