以前迷路の解法って何があるか？と思ったことがあったが
今回は迷路の解法アルゴリズムについての覚書
さて、迷路を簡単に解く方法はないのか？エレガントスマートな解法は？ひとまず、みんなが知っている右手法や以前も調べて出てきたトレモー・アルゴリズムなどがある。
これらは迷路を簡単に解く方法ではなく、逆にやみくもに解こうとする方法でもなく、単に地道にゴールまでの道筋を探す解法だ。解法というより手段と言った方がイイかもしれない。
迷路を解くには「賢くシラミ潰し」に
探すが一番というわけだ
そこで、こう思う
シラミツブシに探すのは分かった。ではそのシラミツブシで探したルートが最短であれば、効果的な解決方法と言えないだろうか？（迷路にゴールまでの道のりが複数あることを考慮に入れて）
最速でルートを解く方法は先のトレモーアルゴリズムなのだが、最短ルートを導くには
ダイクストラ法という
アルゴリズムを利用する。
何とも聞きなれない名前だが、カーナビなどのルート検索に使われるアルゴリズムと言えば、大まかに想像がつくだろうと思う。迷路の解法アルゴリズムが目的地から目標に向かってのルートを検索する事ならば
迷路の解法は、
ナビゲーションに使えるというわけだ。
ダイクストラ法は難しいアルゴリズムではないので、じっくり読めば「あ～～！なるほど！！」と納得がいくことだろう。とくに、接点と接線の自由落下した際の例えは、なかなか分かりやすい。こちらの解説などを参照すると勉強になる。
そしてこのダイクストラアルゴリズムをさらに高速化させたものが
A*アルゴリズム
事前に目的地までの距離または方位が分かっていれば、検索は高速化する。正にカーナビにはピッタリなわけだ。
こちらにダイクストラとA*の実際の動作が分かりやすく図解で紹介されている。
これらのアルゴリズムがもつナビゲーションの性質は、色々な所に応用がされている。まず、Googleマップのルート検索の様なナビゲーション。先ほどのカーナビ、そしてゲーム上でのキャラクタの誘導。他に3DCGでの群集シミュレーションなどなど。もしかしたら軍事兵器やミサイルなどの兵器の誘導システムでも組み込まれているかも。挙げれば色々と考えられる。
ただし、このアルゴリズムには足りないものがある。それは、
最短ルートの道のりにある
抵抗要素である
「抵抗」とひとくくりにまとめているが以下のような例は想像できた。
地形要因、坂や水溜まり等
危険要因、崖や荒れた道等
心境要因、好みや心境等
身体要因、疲労度等
規制要因、信号機や渋滞等
時間要因、季節や朝夕等
機械要因、マシントラブル等
例えば、いくら最短ルートとはいえ信号が大量にあり、しかも道路の一部が工事中だったらどうだろうか？この抵抗のおかげで、時間あるいは距離で
最短であったとしても最善とは限らない
Googleマップのナビゲーションは、自分のツーリングの経験上、Googleマップが算出した時間よりも1.5倍は多くかかる。なぜなら、道を常に進んでいる状態にはならないからだ。
運転をしていれば疲れるしトイレにも行きたくなるだろう。休憩所でのおしゃべりや、もしかしたら綺麗な風景に見とれて時間を過ごすかもしれない。そういった考慮（抵抗）がGoogleマップでは計算に入っていない。（ユーザビリティな部分をGoogleマップに反映させる必要はないが）もし、算出時間で到着したければずっと運転し続けることになるだろう。
他にも、キャラクターナビゲーションで言うならば、主人公についてくる仲間のNPCキャラクタが主人公に追いつこうと無茶な所を走ってくることがあれば、それは抵抗を計算に入れていないからだろう。昔のゲームは、NPCが壁に引っかかると、突然空中を歩いて主人公に追いついたものだ。
もしNPCキャラクタが、ものすごく水たまりが嫌いで、しかも高い所が苦手な性格だったら、崖っプチを疾走し、水たまりを避けずに駆けて来るだろうか？？そんな事したらキャラクタの設定が台無しってモノだ。
うんこ踏んででも
最短距離で移動したい！
というキャラクタはいないだろう。
というか想像したくない。
もちろんCGの群集シミュレーションでも、こういった抵抗を実装しなければ、大量のキャラクタがただ有象無象動き回るだけの無意味なものになってしまう。兵器の誘導も、敵の防御網が硬い所をわざわざ飛んで攻撃する必要はない。
抵抗自体は、幾つかの条件を持たせた場合にどれくらいコストを消費するか？などのルーチンと合わせれば比較的簡単に実装が出来ると思われる。もちろん複雑な条件全部を入れる事は不可能であるから、そのエッセンスさえつかんでいれば大丈夫だろう。
他にも抵抗を組み込んだ際に抵抗同士がお互いに干渉し合うと面白い結果が出るかもしれない。この抵抗値を自ら条件をもとに選択していき最短のルートを計算できれば、もしかしたら一種のAIになりうるのかも。
さて、ひとまずメモはこんなところ。
偉そうに色々書いているクセに、一切ソースを出さないこの体たらくっぷりにはいつも通り。実際にこの程度の話なら、もっと詳しい話がネットに出回っているのでそちらを見た方がいいだろう。
余談、巡航ミサイルが採用している誘導システムはフィンガープリントと呼ばれていて、衛星から得た地形情報をあらかじめミサイルに記録させておき、その地形と比較しなが ら飛行する。だから真平な海ではナビゲーションが出来ないため、イラク戦争では砂漠をわざと通るようにミサイルを撃ったそうだ。