[[
拡張歩数mapでの経路導出
]]
Mice Wiki
現在位置:
IndexPage
»
拡張歩数mapでの経路導出
文書の表示
以前のリビジョン
最近の変更
索引
ログイン
この文書は読取専用です。文書のソースを閲覧することは可能ですが、変更はできません。もし変更したい場合は管理者に連絡してください。
====== 拡張歩数Mapでの最短経路導出(前書き) ====== ここでは通常の歩数マップ(1マス1歩)を理解していることを前提に話を進めていきます。 通常の歩数マップでは、区画の中心にノードを置いてあるものとして考えられています。 よって、ノードとノードの間には常に一定の距離(常に1)であるため、1歩=1マスとなります。 今回考える歩数マップでは、ノードを別の位置に定義します。 ====== ノードの付け方による違い ====== {{:map1.jpg|}} 前述の歩数Mapの考え方によって、生成される歩数マップと、予想される経路です。 2つの経路が生成されています。 斜め走行が可能な場合、この迷路では斜めを選択した方が速いと思います。 この時、 『目の前に同じ歩数を持つ区画が2つ以上存在する場合、それらを適切に選択するプログラムが必要になる』 ことが問題になります。 この歩数Mapを基準に良い経路を求めるためには、ここから独自のアルゴリズムを用いることになると思います。 次に、拡張歩数Mapの考え方によって、生成される歩数マップと、予想される経路です。 {{:map2.jpg|}} この歩数Mapの生成には以下の考え方を用いています。 1:各区画の境界をノードとする。 ⇒壁の中は最大値int方の最大値等、十分大きい数を与えておきます。 2:1区画の距離を7とし、曲がる方向に距離を5とする。(二等辺直角三角形から、1:1.4142... = 5:7) ⇒歩数を具体的な距離としています。最短経路=最速経路とは限らないが、十分に近くなることが見込める。 ====== 経路選択について ====== 規模が大きい迷路の場合、現在位置よりも値が低いノードが複数現れることがあります。 このとき、各分岐点で 最も値が低いノード=最速のルート とは限りません。 複数のルートを比較して、速くなりそうなルートを選択するアルゴリズムを作ると更に良いルートを見つけられます。
/home/users/2/deca.jp-mice/web/cgi/dokuwiki/data/attic/拡張歩数mapでの経路導出.1424413503.txt.gz · 最終更新: 2015/02/20 15:25 by member
文書の表示
以前のリビジョン
文書の先頭へ