前回の続き。
迷路は解けなくなりましたがさほど複雑でない地形の場合はちゃんと目的地にたどり着けるようにしました。
ダウンロード
前回だと、ツリー上のルートなら問題ないのですがルートにサイクルが出てくるとそのままぐるぐるとまわるケースがあったのでサイクル状態を判定させるようにしました。
前回は壁が右手の位置にあるように歩くようにしていたのですが
左手の位置になるように歩く場合も作って切り替えられるようにしておきます。
はじめは目的地へ近づくように歩いていきますが歩けなくなった場合、
地形マップのチップ数と同じ長さの配列を作り各要素の初期値を0b0000にセットして
方向が2なら0b0001、4なら0b0010、6なら0b0100、8なら0b1000を加えるようにして
そのチップ上で過去に言った方向を記憶しながら、右手に壁があるように歩きます。
もし同じチップ上で同じ方向に進むのならばサイクルとなるのでそこで左手と右手の基準を切り替えるようにしました。
また最初に右手を基準に歩くように切り替わったところより目的地に近づくと
通常の目的地へ近づくように切り替わります。
この場合もしかすると重くなるのかもしれないのでそこのところをもう少し調べたいです。
余談
他にもいろいろ必ず目的地へたどり着くにはどうしたらいいかと考えていて
アイデアはあるのですが（きちんと吟味すると間違えてるかもしれません）
これは重くなりそうな上にルートの選び方が不自然になるので作ってません。
まず前回のように右手または左手に壁があるように歩くのですが
歩いたルートにサイクルができた場合、
目的地がサイクル内にあるか、サイクル外にあるかを判断させて
目的地がある方のみ移動できるようにします。（つまりサイクルを境界として領域を分ける）
これを繰り返していき、取り除かれたサイクル同士が共通で持つ境界線をとりぞきます。
最終的には単純なサイクル構造に還元されて
そして目的地へとたどり着きます。（境界部分も行動できるのでサイクル領域を取り除いて行く
過程でも残った領域は連結されています）
上で目的地がサイクルの内部にあるかの判定ですが
これも色々考えていましたがとりあえず次のような感じです。
まず目的地を中心に画像のように領域を8つに分けます。
目的地を通らない場合、かならず隣の領域から入ってきます。
（つまり飛ばすことはできないので1回りするとき必ずA,Bの領域を通ります。）
そこで回転数という値を作って
図のAの領域からBの領域へ進むとき -1、
Bの領域からAの領域へ進むとき+1を加えるようにします。
するとサイクルで同じ位置に帰ってきても回転数が異なれば
サイクルの内部に目的地があります。
予断ですがサイクルの内部にあるかの判定なんですが
他にも複素平面で考えて目的地を極とするような適当な正則関数f(z)をとって
ルートを経路とするf(z)の積分を考えて0ならば内部に目的地を含まず
0以外ならば内部に目的地にあると判定しようかなとも考えたのですが
なんだか上手くいかなさそうなのでやめました。（ちゃんと考えてないので分かりませんが）
