DATE: --/--/--(--)   CATEGORY: スポンサー広告
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
page top
DATE: 2017/09/19(火)   CATEGORY: 未分類
秘伝のタレからの脱却~探索用歩数マップ~Part3

Part2の続きです。
今回で①について説明が終わるかと思います。


前回の記事で書いた通り
ゴール座標は全区画の組み合わせを網羅できるように定義しておくべき
ことはわかったと思います。

プログラムは自己流で書くのでよりいい書き方があれば自分で直してください。


全区画をゴール座標にできるようにするということで
ゴール座標の定義はこうなりますね。

ゴールデータ宣言


一列32マスなので,配列の各bitがx,何番目の配列かyとすることで
全ての区画にゴールフラグを設けます。


このゴール座標配列を用いるために必要な関数は2つです。

配列初期化関数ゴール座標代入関数です。

それぞれ以下のように書けますね。ついでに座標クリア関数もあると便利ですね。

各関数


これで最小限必要な準備は整いました。
次は、秘伝のタレの中身との整合性を合わせていきましょう。

基本的に秘伝のタレの歩数マップでは以下の手順を踏んでいます。

秘伝のタレ初期化部分


以降queueを用いて展開の順番を保存して歩数マップを展開していく流れです。
簡単な展開の順番の様子はこちらの記事の画像を参照してください。


さて,ゴール座標を複数置く場合どこを変更すればよいかというと
ゴール座標をqueue配列に代入するところです。

自分が書き換えるならこんな感じ。

シン・ウムオ初期化部分


これでゴール座標に0を代入し、queue配列への代入が完了しました。
あとは同様に展開するだけですね。

これだけで複数個の任意ゴールを持った歩数マップを扱えるようになると思います。



このように全区画に任意の個数のゴール座標を扱える歩数マップがあると何かと便利です。
例えば4、9マスゴールに対応させたいとなったときどうするかです。

引数に(基点となる座標、1辺の区画数)として、
基点から順にゴール座標代入関数をする関数
を作ってみましょう。

これだけで4、9マスゴールに対応させた歩数マップが完成です。
ゴール区画に入ったのにキュピキュピっと動くような
かわいらしい(笑)動きはしなくできますね。

4マス歩数マップ


また、全面探索で自分の位置から一番近い未知区画を目指したいときは
全面をスキャンして未知区画全てにゴール座標を代入、
既知区画になった座標はクリアしていくというだけで簡単に行えます。

僕はマイクロマウスの中で全面探索という考え方が
死ぬほど嫌いなので実装しませんが興味があればどうぞ。


このように、全区画をゴール座標にできるようにすることだけで
汎用性の高い仕様の歩数マップが完成したと思います。




次回では② 計算時間短縮のため自分の現在位置に到達で展開を中止
の影響について更新しようと思います。



スポンサーサイト
DATE: 2017/09/19(火)   CATEGORY: 未分類
秘伝のタレからの脱却~探索用歩数マップ~Part2


前回の続きです。

① ゴール区画を任意の位置に複数で設定可能(4、9マスゴールにも対応可能)
について説明していこうと思います。

これを語るためには大前提として理解していてほしいことがあります。

歩数マップは複数個ゴールがあっても何も問題ない

ということです。


このことを理解してほしいので、以下に例を示します。
まず、簡単な例としてエクセルで簡単な歩数マップを作ってみます。

まずは,ゴールは(2,2)の1マスです。

1マス歩数マップ


THe普通。
この歩数マップをもとにマウスを走らせた場合、
マウスは中心に向かって走って行きますね。


では、この歩数マップをもとに等高線グラフを書いてみます。

1マス等高線


真ん中が低くなって外にいくにつれて高くなっているグラフになります。

この床面にボールを置いた場合、ボールは一番低い位置をめがけて転がっていきますね。


この例から、
歩数マップとマウスというのは
勾配のある床とボールの関係と同じであることがわかります。




では次にゴールを2個所に増やしてみます。
ゴール座標は(1,3)、(4,1)です。

2マスゴール


これからどうなっていくか考えてください。
歩数マップは目的地から隣接する区画に歩数を振っていきます。
つまり、こうなります。

2マスゴール歩数マップ


等高線グラフはこんな感じ。

2マス等高線

この等高線マップにボールを置いたらどうなるでしょう。
おそらくボールは、
(1,3)に近い方に置いた場合は(1,3)の穴に
(4,1)に近い方に置いた場合は(4,1)の穴に
転がっていくと思います。

ボールが上のように動くということは、マウスも同じ動きをすることがわかります。

ゴールが複数個ある場合、
マウスは複数個のゴールの中から一番近いゴールを目指して走ることが可能なわけです。


他の位置にゴールを移動したり,ゴールの数を増やしていっても同じです。


ここで考え方を変える必要がありますね。
ゴールは任意の1つではなく、
任意の位置に複数個置けるプログラムの内"たまたま"1個を指定しているのだと。

また、ゴールの位置個数はいくらでもよく、
ゴールの位置は離れていてもよいこと
が上の例からわかりました。


つまり、ゴール座標というのは#defineやconst変数ではなく
全区画の組み合わせを網羅できるように定義しておくべきだということです。


続く

DATE: 2017/09/19(火)   CATEGORY: 未分類
秘伝のタレからの脱却~探索用歩数マップ~Part1


久しぶりの記事となりました。

今回は最近Miceのハーフぜいで話題になった探索用歩数マップについてです。



今年はMiceの老害と呼ばれる部類の人たちの中でハーフが盛んです。
昨年からハーフ競技に取り組んでいる自分としては
たくさんハーフマウサーがいるのは盛り上がって嬉しいです。
今年こそはハーフ勢に人権を!!


ハーフサイズ競技の目玉と言えば、
全日本大会でのエキスパート決勝の32×32迷路ですね。

32×32迷路では16×16迷路では格が違います。
なんと言ってもサイズが4倍の1024マスです。

16×16では8 bit変数で足りていた区画数も16 bit変数でないと足りません。
そして、単純な計算時間は4倍。とてもとても辛い。

僕が16×16迷路は迷路じゃないと言ってしまう理由はこんなところです。



計算時間の問題もあり、歩数マップの話題が度々上がります。
そういうときにいつも思うことがあります。

みんなサンプルとしてもらう歩数マップを信仰しすぎじゃね!?

ってことです。


Miceでは歩数マップを理解した者の証として
歩数マップの展開のサンプルプログラムという秘伝のタレがあります。

秘伝のタレと言っても昔使われていたもので欠点もちらほら。

例えば、
1マスゴールにしか対応していない。

例えば、
32×32には対応していない。

これからはハーフマウスの時代です。(宗教)
秘伝のタレは時代遅れなのでシン・ウムオで使っている探索用歩数マップを紹介します。
みなさん秘伝のタレをアレンジする勇気を持ちましょう!
秘伝のタレは絶対では無いですよ(重要)


既存の全面展開秘伝の歩数マップとの違いは3つ。といっても技術交流会で話した内容の詳細といった感じです。

① ゴール区画を任意の位置に複数で設定可能(4、9マスゴールにも対応可能)

② 計算時間短縮のため自分の現在位置に到達で展開を中止

③ 次の展開が未知区画の袋小路の場合、歩数を振る代わりに壁の代入(未知区画袋小路潰し)


ここまでで長くなってしまったので
それぞれの細かい内容については次回以降の記事に書いていこうと思います。

ではでは

Copyright © うむ夫の歩み. all rights reserved.
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。