曲がった迷路その12 - 再び方針変更 [曲がった壁を持つ迷路の生成]
あかんがな。最初に気がつけよ
、っていつものことだけど。
昨日ポテンシャルを格子点の値を補間するのにBezier曲線を2次元に拡張した。これはごく普通にやられていることなのでそれをフォローした。補間するならこれだろ、とか思いながらついつい先走ったけどよく考えたらこれは役に立たないということがわかった。
問題発覚
ここまできて基本的なことを忘れていた。Bezier曲面は媒介変数表示なので、位置(x,y)での値を直接得ることができない。Bezier曲線の交点を求めるのと同じ方法を使わないといけない。これは繰り返し計算を行うことになって非常に面倒。
この問題はBezierを使おうと思ったときにまっさきに気がつくべきだった。曲面への拡張のことばかり考えて、この基本的な問題をうっかり忘れていた。
ということでここまでやったけどBezier曲面を利用するのはやめる。
そうすると、まっとうな補間法としてはスプラインということになる。
今回補間したいデータは何度も書くがエレベーションなので
の形の2変数1価関数が決まればよい。そういうのには2次元のスプラインが向いている。ただし、普通のスプライン補間ではひとつの端点の位置が変わると全部に影響が及ぶ。もし補間したいデータが固定的ならそれでかまわない。これはポテンシャル関数をどう使うかによるので、それを考えた後、もう一度この問題に戻ることにする。
衝突回避のためのポテンシャルへの追加
以前は壁どうしが繋がらないように新しい壁を作るたびにそのまわりにポテンシャルの障壁を作ってそこに壁が追加されないようにしようとした。 ポテンシャル関数を使うということは変更しなかったので、この考え方はそのまま使える。ただし、以前は連続なクーロン型のポテンシャル関数を考えていた。今は、もとは離散的な値でそれを補間したポテンシャルにしたので、それと相性のいい障壁ポテンシャルに変更しよう。
壁衝突回避のポテンシャルの形状
クーロン型のポテンンシャルは非常に急な関数で、閾値だけで可否判断するとポテンシャルの形が円筒形のものとあまり変わらない。クーロンポテンシャルや円筒形は値が急に変化するのでその周辺で振動などの悪いことを起こしやすい。
前考えたときは別に気にしなかったが、もうすこしおとなしいポテンシャルを考えてみる。
ここでのポテンシャルは単に閾値より大きな値は無限大と同じなので、てっぺんは閾値以上で、その外はゆっくり減ってあるところで0になる、と言うようなのがいい。
そうすると、例えば図-20のようなテント型(アメリカインディアンのテント「ティピ」の形)のポテンシャルがいい、ということになる。
式で書くと みたいな感じ。 これだと距離がr0以上離れたところには効かなくなるので遠い点での影響を考える必要はない。ただし、テント型だと裾野で微分不可能になるので、数値計算をやってきたものとしてはあまり気持ちよくない。微分可能な関数の方が気分的に楽。と考えると例えば
のような関数がいい。絵に描くと図-21みたいになる。 しかしこれは気分的な問題で、今回のような場合、あまり関係ない。たぶん。こういった衝突回避のためのポテンシャルを、新しく壁を作ったところに足していく。そうすればすでにあるところに新しい壁は作られなくなるのはクーロンポテンシャルで考えていたのと同じである。
違いはスペックルパターンのポテンシャルがもともとあってその上に足し算されることである。そしてそのポテンシャルは格子点の上で定義されていて、補間されるということである。これとの相性を考えなければいけない。
二通りのやり方がある。
- スペックルパターンによるポテンシャルVijに新しい壁を作るたびに足していき、そのたびに補間の式も変更する
- Vijの補間は変更せず、衝突回避ポテンシャルをそのつど加える。総当たりを避けるためのアルゴリズムは以前考えた物を採用する
1番目の方法では、補間法として一般的なスプラインを使うとしたら、新しい壁を作るたびにすべての領域の補間関数を変更しなければならない。このオーバーヘッドは巨大になる可能性がある。
また一方、ポテンシャルの最下点を求める場合、ポテンシャルの微分(グラディエント)の値がある方が収束は速い。2番目の方法では、微分はスペックルパターンのポテンシャルの微分と衝突回避ポテンシャルの微分の和になり、まあ、足せばいいだけだけどめんどくさくなる。その点、1番目の方法は補間式を微分するだけ(式の形は決まっているので微分された式に係数の値を代入するだけ)ですむ。
微分はティピ型であれば簡単(中心からr0以内だと定数でその外は0)なので2番目の方法に向いている。
うーん、どういうのがいいかなあ。こういうときはやっぱり両方実装するのがいいだろうなあ。面倒だけど所詮遊びだから、どっちかをさきにやると、結局それに確定するしなあ。まあいいか。
コメント 0