DATE: 2016/11/08(火)   CATEGORY: 未分類
フレッシュマン詐欺候補たちへ2

今回は既知区間加速編について更新しよう!と思っていたのですが,
止めました.理由は主に2つです.

① "既知区間加速はかっこいい"が16×16迷路ではその効果は薄い
② Mice guestのドライブに冬の技術交流会で作った簡単な資料をあげてある


今回は今年実装をしたものですが,
フレッシュマンでも簡単に実装できる直線優先歩数マップの作り方を紹介したいと思います.

直線優先歩数マップとは何かというと,
Mice Wikiに記述を見つけたためこちらを参照してください.


フレッシュマンの人たちは足立法ベースの最短経路導出がほとんどだと思います.
しかし,様々な地区大会を経て,

あっちの経路の方が直線多くて良いタイムが出たのに><

という経験も多いのではないかと思います.
そこでこの問題を解決しましょう!(斜め走行はしりません)
これを簡単に解決できるものの一つが直線優先歩数マップです.


今回紹介するのは自分なりの実装なので,Mice Wikiのやり方とは少し変わります.
参考にしてもらえればと思います.
まずは,準備です.

① 歩数マップを16 bit変数に拡張する.
(unsigned char→unsigned short,もしくは,uint8_t→uint16_t)

従来は区画の総数で十分な数でよかったのですが,
重みをつける以上255以上の数になってしまいます.

なので変数の型をより大きなものに変更しましょう.
これで,最大値は65535までとれるようになりました.
32×32の迷路にも対応できますね^^


準備は以上です.それでは直線優先歩数マップを作製していきましょう.
ただ曲がるだけに重みをつけるなら,歩数マップの展開のときに方角の情報を設ける
もしくは,一度展開した歩数マップを簡単に解析する関数があれば,
Mice Wikiの通り簡単にできますね.

しかし,この方法だと長い直線を探すのが面倒そうだと思い,
自分は別の方法をとりました.それを紹介します.

簡単に言うと,"歩数マップの展開の順番を変える"です.

Mice Wikiの迷路を例に説明します.
従来の歩数マップ展開では,以下の順番に次の歩数を決めています.
従来の展開順番

自分の方法ではこういう順番に展開を決めます.
新しい展開順番


違いとしては,従来のゴールを中心に1マスずつ順番に展開していくのではなく,
基点となるマスから4方角の直線状に突き当りがあるまで,
歩数マップを展開していくという点です.
次の基点は左右の分岐がある点のみ候補にします.

この方法なら長い直線を簡単に見つけ出せるかなと考えました.
北に伸ばす例として以下にソースコードを載せます.(見にくいのは許して)
北方向の展開


基本は1歩目は固定として,直線が長くなるにつれて歩数を増やす量を調整しています.
これを残り3方角に伸ばすだけです.
マウスや走行パラメータによって,曲がり角のパラメータや直線減少量を調節してあげると
よりいい経路が得られるかもしれません.
直進優先歩数マップ


これで簡単に直線優先をした経路が見つけられるようになると思います.

ではでは

スポンサーサイト

コメントの投稿

 管理者にだけ表示を許可する
Copyright © うむ夫の歩み. all rights reserved.