tokoro10g / libamaze Goto Github PK

Solver::preSense, Solver::postSense の実行前後で Solver::getCurrentNodeId() 等の値はどうなるか，Maze や MazeGraph に対してどんな処理を行うべきかを明確にする．

#3 の実現方法として，既存のソルバに LookAheadFeature を継承することで機能を付加することが考えられる．

この場合，現状の preSense, postSense メソッドをオーバーライドすることになるが，共通の処理を LookAheadFeature に実装し，そこからタイミング別に各ソルバ固有の処理を呼ぶ形式にすると書きやすい．
preSense, postSense メソッド内の処理を細分化したい．

現状 MazeGraph::neighbors で隣接ノードを取得してから、その各ノードに対して MazeGraph::edgeCost を計算している。
どちらのメソッドも内部的に MazeGraph::getEdge をコールしているため、1回のコールで済むものを2回コールしていることになり、効率が悪い。

現段階では不要だがセットアップしておいて損はない．

Related:
#11 #12 #13

簡単なベンチマークプログラムを実装済みだが，あらゆる迷路に対して網羅的に取ったデータがまだない．

こういう便利なライブラリがある

• https://github.com/google/benchmark
• https://github.com/DigitalInBlue/Celero

テストから最初に書けよと言われそうだが，先に実装してしまったものは仕方がないのでなるべく網羅できるテストを書く．

特定の組み合わせで問題が起こると困るので，ソルバの種類とMazeGraphの種類のすべての組に対してテストが必要．

動的な探索で問題が起きる可能性がある．どう対処するか．

Solver::preSense の段階で，壁の状態に対する次のノードIDを事前に計算しておき，Solver::postSense では事前計算したものをチェックするだけにしたい．
このような実装にすることで，壁を観測した後に高負荷な探索アルゴリズムを実行する必要がなくなり，比較的時間に余裕のある区画走行時の計算リソースを有効活用できる．

実装上の課題として，現状のD* Liteの実装では壁の状態に関する仮定を置いたまま最短経路を導出できないことが挙げられる．Solver から直接操作できる MazeGraph は Maze の const 参照しか持たせておらず，壁のデータは書き換えられない．したがって，ソルバの内部に仮定を保持して，MazeGraph から受け取った迷路情報を仮定で上書きしてから計算する処理をソルバに加える必要がある．

そろそろバージョン番号をつけたい．リリースのための準備をする．

現状Doxygenで出てくる無愛想なリファレンスしかないので，サンプルコードやGetting started的なマニュアルを整備する．

現在の状態からつぎに観測する壁のリストを計算したり，実際に観測したデータからMazeを更新するクラスを作成する．

Solver::preSense や Solver::postSense に渡す位置の候補を取得するメソッド，実際にsenseするメソッドなどを備えるようにする．

iostreamを混ぜたまま組み込み向けにコンパイルすると地獄を見るので分離する必要がある．

迷路の保存形式や表示形式を
https://github.com/kerikun11/MazeLibrary/tree/master/mazedata
や
https://github.com/micromouseonline/mazefiles
のものに変更する．

自分で迷路データ作るのだるいし．

ゴールに到達できない迷路の場合のエラー処理や，ソルバの詳細な状態を取得するための機能がほしい

主に帰りの探索中に，特定の区画や壁の情報を取得するために一時的にゴールを変更することがある．
現状 MazeGraph::getGoalNodeId は Maze::getGoal で取得した迷路のゴールをノードIDに変換して返しているが，本来グラフ探索上の(一時的な)ゴールと迷路の(大局的な)ゴールは分けて考えるべきである．

混乱しないようなインタフェースや命名を考える必要がある．

探索走行時には未探索の壁を横切る経路を候補として走行してよいが，最速走行時にはそのような経路を選んではならない．

現状のライブラリ実装ではこの2つのモードの切り替えに対応していない．実装方針は2つある．

1. MazeGraph と Solver のインタフェースを変更してモードの切り替えを実装する
2. MazeGraph を継承して，最速走行モード用のグラフ表現を実装する(もしくはテンプレートパラメータを使用する)

1の場合，ソルバの実装に本質的でないものが紛れ込むほか，コード自体が煩雑になる可能性がある．ただし使い方はシンプルになる．
2の場合，実装は最小限で済むが，使用する際に MazeGraph を2種類インスタンス化しなければならない(※メンバ変数は Maze への参照だけなのでメモリは食わない)．