グリッド上の移動経路を求めるためのアルゴリズムには、ダイクストラとかA*とかがある。けど、これらは45°単位で移動方向を制限する。もうちょっとななめに効率的に移動してほしい。
ここでやりたいことは、any-angle path planningと呼ぶらしい。
JavaScriptでの経路の話ならPathFInding.jsがあるけど、ここにはまだany-angle path planning用のアルゴリズムは入ってないし（プルリクはあるけど未マージ）、セルごとのweight設定もできなさそうなので（forkはあるらしい）、今は使わない。
Theta*
Any-angle path planningの一つ。この記事がわかりやすい。A*をベースとしていて、A*での「セルの親はneighboring cellでなければならない」というルールをなくすことによっていろんな角度に移動できるようにしている。
以下は、Theta*を実装しようとして考えたことのメモ。
Neighboring cells
セルのneighborとして巡回するセルは、4方向（North, East, West, South）にするべきか、8方向（4方向 + Northeast, Northwest, Southeast, Southwest）にするべきか。
初め、「どうせTheta*だったら子を親の親とまでくっつけようとするんだから、4方向を登録しとくだけで、最終的にななめに移動できるのでは？」と思っていた。だいたいの場合はそうなんだけど、weightが絡んでくると頭が悪い経路ができてしまう。
この経路は、本来ならweightが1000もあるセルは避けて(0, 0) -> (1, 1) -> (2, 0)とななめ移動するべき。それができないのは、(1, 1) -> (2, 2)への経路を作るためには、
(1, 1)を親とする(1, 0)をpriority queueに入れる
(1, 0)がpriority queueから取り出されて、(2, 0)に行ってゴール
という手順を踏まないといけないけど、当然(1, 0)の親としては(0, 0)の方が優秀（コストが低い）なのでそっちが優先で保存されてしまい、理想的なななめの経路は残らなくなってしまうから。やっぱりちゃんと8方向分をneighboring cellとしてチェックしないといけない。
Line of sight
離れているセルに移動するときは、その移動パスが通るセル全てが通行可能である（ブロックされていない）ことを確かめないといけない。直線が通るセルをチェックする方法は、直線をラスターディスプレイに表示するときにどこの画素を塗りつぶすかっていう話に似たようなものになる。
上記のTheta*の記事で書かれているpseudocodeは、移動体はvertexからvertexへと移動することを前提としているので、セルからセルに移動させたい場合はそのままでは使えない。なので、二つのセルの中心を線で繋ぐような方法を探した。
Bresenham's Line Drawing Algorithm
グラフィック分野での古典的なアルゴリズムらしい。これなら、セルの中心から別のセルの中心へのline of sightチェックができそう。
問題は、例えばΔx > Δyのとき、x軸に沿って一列に1セルしか取り上げられないこと（xとyが逆でも同じ） 。すると、直線が微妙に通ってるところにブロックされたセルがあってもすり抜けられてしまう。
ピンクのセルがこのアルゴリズムでピックアップされるセルで、濃いグレーがブロックされてるとこ。(2, 2)にあるセルは本当は通り抜けできないんだけど、line of sightチェックでx = 2のとき(2, 1)しか取り上げられないため、(2, 2)は無視されている。
Supercover
直線が通る全てのセルが欲しいので、上記のアルゴリズムをそのままは使えない。探してたら、Bresenham-based supercover line algorithmってやつが見つかった。やりたいことは私と全く同じだけど、前のerrorを保持しなければいけなかったり複雑なので、自分で書くことにした。
Bresenhamさんのやつはセルの中央でのerrorによってどちらのセルに描画するかを分けている。私はセルの端っこでのerrorから次どこに行くかを判断したい。そこでのerrorは
< 0.5: secondary axisの座標はそのまま= 0.5: secondary axisの座標を進めるけど、行った先で描画はしない> 0.5: secondary axisの座標を進め、行った先で描画する
(secondary axisは、xとyのうち移動量が少ない方の軸)
という3つのケースがある。
座標を進める場合（ケース2と3）のみ、errorの基準（error = 0の場所）が一セル分進むのでerror--する。
この方法で、さっきみたいなすり抜けは発生しなくなった。
Diagonal movements
対角線上の移動を許可するかについては、道の片方だけブロックされてるときは許可して、両方ブロックされてたら許可しないというふうにした。これは好みの問題なので、ブロックされたセルのきわきわを通るのは嫌なときもあるかもしれないけど。
両側ブロックされてるときに対角線上の移動を却下するには、
Line of sightチェックで、セルの端っこでのerror = 0.5のとき、両側のセルの少なくともどちらか一方が空いている場合のみline of sightがあると判定する
セルのneighborリストのイテレーションのときに、そのneighborがななめ方向にあるとき、両側のブロックが空いている場合のみそのneighborを考慮する
という方法が考えられる。上の方法だと、親の親と子を繋げる経路（Path 2って呼ばれてるやつ）にしか適用されなくて、A*でも存在する普通のneighborへの経路（Path 1）がいけるかどうか判断するときには個別で条件分岐をつけないといけなくなるので、下の方法の方が便利。
Gの計算
Gというのは、A*・Theta*での
F (最小化するやつ) = G (cumulative cost) + H (heuristic distance to the goal)
っていう計算に使うGの話。ここでは、
G of child = G of parent
+ parentとchild間の距離
+ parentとchild間にある全てのセルのweightの合計
にすることにした。
Weightとは、そのセルを通るためにかかるコスト。たとえば、さらさらなセル（歩きやすい）とねちゃねちゃのセル（歩きにくい）があったとき、ねちゃねちゃのセルの方が大きなweightを持つ。
ここで、parentとchild間にある全てのセルっていうのをどうやって決めるか考えないといけなかった。
さっき書いたsupercoverのセルのweightを全部足すと、以下のような2×3のグリッド（セルは均一のweight 10を持っている）で、右のようなスムーズな移動よりも左のかくかくした移動の方が有利になる。
けど、普通に考えたら右のほうが選ばれるべき。
なので、Gにweightを加算するセルたちは、supercoverではない方のBresenham's algorithmで求められるやつだけにすることにした。
それはそれでany-angle pathの方が有利になりすぎることもあるけど、どうするのがいいのかよくわからない。アルゴリズム名が検索しづらいせいか、あんまり似たような使用例を見つけられなかった。
ためす
とりあえず上記の方法で実装したやつの動作を試してみるために、小さいツールを作った。進路妨害するの楽しい。
Optimization
Lazy Theta*は、line-of-sightのチェックを本当に必要なときにしかしないことで効率化してくれる。
