見返すかもしれないメモスマートフォン用の表示で見る見返すかもしれないメモ2018-10-05ななめに移動してほしいその他グリッド上の移動経路を求めるためのアルゴリズムには、ダイクストラとかA*とかがある。これらは45°単位で移動方向を制限する。ななめに効率的に移動してほしい。planningと呼ぶらしい。planning用のアルゴリズムは入ってないし(プルリクはあるけど未マージ)、セルごとのweight設定もできなさそうなので(forkはあるらしい)、今は使わない。planningの一つ。この記事がわかりやすい。cellでなければならない」というルールをなくすことによっていろんな角度に移動できるようにしている。以下は、Theta*を実装しようとして考えたことのメモ。Southwest)にするべきか。初め、「どうせTheta*だったら子を親の親とまでくっつけようとするんだから、4方向を登録しとくだけで、最終的にななめに移動できるのでは?」と思っていた。だいたいの場合はそうなんだけど、weightが絡んでくると頭が悪い経路ができてしまう。0)とななめ移動するべき。0)の方が優秀(コストが低い)なのでそっちが優先で保存されてしまい、理想的なななめの経路は残らなくなってしまうから。cellとしてチェックしないといけない。sight離れているセルに移動するときは、その移動パスが通るセル全てが通行可能である(ブロックされていない)ことを確かめないといけない。直線が通るセルをチェックする方法は、直線をラスターディスプレイに表示するときにどこの画素を塗りつぶすかっていう話に似たようなものになる。上記のTheta*の記事で書かれているpseudocodeは、移動体はvertexからvertexへと移動することを前提としているので、セルからセルに移動させたい場合はそのままでは使えない。二つのセルの中心を線で繋ぐような方法を探した。Algorithmグラフィック分野での古典的なアルゴリズムらしい。sightチェックができそう。Δyのとき、x軸に沿って一列に1セルしか取り上げられないこと(xとyが逆でも同じ)。すると、直線が微妙に通ってるところにブロックされたセルがあってもすり抜けられてしまう。ピンクのセルがこのアルゴリズムでピックアップされるセルで、濃いグレーがブロックされてるとこ。2)は無視されている。Supercover直線が通る全てのセルが欲しいので、上記のアルゴリズムをそのままは使えない。algorithmってやつが見つかった。やりたいことは私と全く同じだけど、前のerrorを保持しなければいけなかったり複雑なので、自分で書くことにした。Bresenhamさんのやつはセルの中央でのerrorによってどちらのセルに描画するかを分けている。私はセルの端っこでのerrorから次どこに行くかを判断したい。axisは、xとyのうち移動量が少ない方の軸)という3つのケースがある。0の場所)が一セル分進むのでerror--する。この方法で、さっきみたいなすり抜けは発生しなくなった。movements対角線上の移動を許可するかについては、道の片方だけブロックされてるときは許可して、両方ブロックされてたら許可しないというふうにした。これは好みの問題なので、ブロックされたセルのきわきわを通るのは嫌なときもあるかもしれないけど。左は片方ブロックされているだけなので移動可、右は両方なので通れない。sightがあると判定するセルのneighborリストのイテレーションのときに、そのneighborがななめ方向にあるとき、両側のブロックが空いている場合のみそのneighborを考慮するという方法が考えられる。1)がいけるかどうか判断するときには個別で条件分岐をつけないといけなくなるので、下の方法の方が便利。goal)っていう計算に使うGの話。parentとchild間にある全てのセルのweightの合計にすることにした。Weightとは、そのセルを通るためにかかるコスト。さらさらなセル(歩きやすい)とねちゃねちゃのセル(歩きにくい)があったとき、ねちゃねちゃのセルの方が大きなweightを持つ。ここで、parentとchild間にある全てのセルっていうのをどうやって決めるか考えないといけなかった。10を持っている)で、右のようなスムーズな移動よりも左のかくかくした移動の方が有利になる。4けど、普通に考えたら右のほうが選ばれるべき。algorithmで求められるやつだけにすることにした。pathの方が有利になりすぎることもあるけど、どうするのがいいのかよくわからない。アルゴリズム名が検索しづらいせいか、あんまり似たような使用例を見つけられなかった。ためすとりあえず上記の方法で実装したやつの動作を試してみるために、小さいツールを作った。進路妨害するの楽しい。Theta*は、line-of-sightのチェックを本当に必要なときにしかしないことで効率化してくれる。Technologiesっていう...2016-12-12色差を求めるある色を与えられたときに、それに近似した色の服部をデータベ...2016-02-14AndroidでDatePickerDialogのまがい物を作る2日かけて、AndroidのDatePickerDialogのまがい物を作った。(1)Searchはてなブログをはじめよう!YaaMaaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。