yumeの日記： Unity学習 #9 2D Visibility
2D Visibility
●頂点座標のその先
これまでの作業で、
・各ポリゴンの頂点座標
・プレイヤーと頂点座標を結ぶ線上の、ポリゴンとの衝突点
をとることはできたが、もう一種
・頂点座標からさらに進んだ先の、衝突座標
が必要だ。
考え方としては
・ある頂点を目指してRayを投げたとき：
・Rayが頂点まで到達できない場合は、その地点をReturn
・Rayが頂点まで到達した場合は、その点と、さらに
そのRayをColliderにぶつかるまでまっすぐ伸ばし、ぶつかった地点をReturn
（頂点に到達した時点で、そこが終着点になる場合もある）
現状作っている頂点リストは以下の二種だ
・すべてのポリゴンの頂点座標リスト
・衝突チェックをしたあとの、最終的な頂点座標リスト
上の考え方では、「頂点まで到達できた」分は二つの頂点が必要なので、
最終的に作られる頂点数リストの長さは可変になる。
さらに、そこから「可視領域」をポリゴンで作るとしたら、
プレイヤーの位置を基準に、リストの内容を角度でソートすることになる、と思う。
要素の追加・削除・ソートを毎フレーム実行するということだから……計算量的にはどうなんだろう。
qiita @takutoy曰く、
・リストの要素の追加はO(1)
・リストの要素の削除はO(n)
・リストのソートはO(n log n)
＞一番でかいのはソート。
qiita @drken曰く、
・一般の家庭用PCで、1秒間で処理できる for 文ループの回数は、10^8 = 100,000,000 回程度
・n log nの計算量は、nが1000の時 9966、n10000のとき、132877。
仮にFPS60のゲームを作るとしたら、1フレームは0.01667秒。
上の基準で考えると、1フレームの計算ステップ量は166700以下にしたらよいってことかな。
ひとつのポリゴンの頂点数が4だとしたら、シーン上（あるいは、視界の範囲上？）に仮に200個のポリゴンを置いても800。
光源の数が仮に10個あったら、計算量はその10倍？
実際にはほかにも色々やってるわけだけど……とりあえずは大丈夫そう。
では実際に頂点の先の到達点をとる。
ncase.me曰く、（google翻訳）
・各（一意の）ラインセグメントの終点に対して、光線を直接それに向けてキャストし、さらに+/- 0.00001ラジアンでオフセットされた2つの光線を追加します。特定のセグメントコーナーの後ろの壁に当たるには、2つの追加の光線が必要です。
ええとつまり、各頂点目指して飛ばしたRayと、ほんのわずかに角度の違う2本の線を投げることで、ある点の奥まで線を飛ばせるということか。
なるほどだが、となると扱う終点数はさっきの試算の3倍になる……。まぁいいか。とにかくやってみよう。
・まず、すべてのポリゴン頂点を取得し、PolyVertexリストに追加する。
・空の終点リストendPointsを作る。
FieldOfView()
{
endPointsリストをClearする。
forループ：
・polyVertexの要素をとりだし、そこへの角度を算出する
・角度と視界最大距離（現状は常に部屋の外まで伸びる）から終点座標を算出する
・プレイヤー現在地から、終点座標までにRayを飛ばし、衝突位置を探す。
・衝突位置をendPointsリストにAddする。
さらに：
・角度を0.00001度だけ足し、同じように衝突チェック・リストへの追加をする
・角度を0.00001度だけ引き、同じことをする。
}
現状の頂点数は、ポリゴン3つと、部屋の4隅。すべて4角形なのでポリゴンは16個。
endPointsリストの数を数えると48、きっちり3倍のRayが飛んでいることになる。
ともあれ、これで必要な終点（＝可視領域の多角形の全頂点）をとることはできた。
●可視領域の多角形を作る
可視領域を作る、といってもそれを赤く塗り潰したところで意味は無いんだけど、
何をするにしてもこの可視領域という概念が必要だろう。
多角形を作るための頂点はすでにそろっている。ならば、単純にこれを塗りつぶす多角形を作ってみればよい。
多角形をUnityのスクリプトで作るにはどうするか？
Prog-G曰く、
・多角形はMeshで作る
・どんな多角形も、三角形をつなげまくったらできる。
・メッシュには各頂点座標と、「どういう順で繋げるか」という手順が必要になる。
うーむ。とにかくまずは三角形を描いてみよう。
三角形を描くには、各頂点の座標が必要だ。まずは仮のリストを作る。
meshPoints = new List();
meshPoints.Add(new Vector3(2.0f, 2.0f, 0.0f));
meshPoints.Add(new Vector3(2.0f, 1.0f, 0.0f));
meshPoints.Add(new Vector3(1.0f, 1.0f, 0.0f));
そして、各頂点をつなげる順番を指定しなければならない。
その順番は、必ず時計回りになるようにする。（でないと裏返ってしまうらしい）
この座標の場合、上から順につなげればちょうど時計回りになる。
meshTriangles = new List();
meshTriangles.Add(0);
meshTriangles.Add(1);
meshTriangles.Add(2);
そして、実際にメッシュを描く。
FOVMesh = new Mesh();
//仮ポイントリストをMeshに反映
FOVMesh.vertices = meshPoints.ToArray();
FOVMesh.triangles = meshTriangles.ToArray();
//法線を再計算（必須）
FOVMesh.RecalculateNormals();
あとは、MeshRendererコンポーネントがうまいこと描画してくれる。基本はこれだけのことだが、懸念点がある。
・これをUpdate関数で毎フレーム実行する場合、毎フレーム new Mesh();を実行するということになりそう。
・そもそもTriangleの順番をどうとるのか。
＞各頂点座標を取得するときに、角度も計算して角度リストに入れておく……まではいいとして、
その角度リストをもとにソートするとしたらどうすればいいだろう。
あるいは、ソートせずに各頂点を角度順に取得するという手もあるかもしれないが……方法が検討着かず。
とりあえず参考になりそうなのをババっと集めておく
Unity GL（MeshでなくGLでポリゴンをかけないか？）
Meshの頂点をむにゃむにゃ動かす
・meshにSetVertices(vertextList);で、Update関数で動かすことができている
void Update()
{
for (var i = 0; i < vertextList.Count; i++)
{
vertextList[i] += new Vector3(Random.Range(-0.1f,0.1f), Random.Range(-0.1f, 0.1f),0);//全頂点のxとyをランダムでちょっと動かす
}
mesh.SetVertices(vertextList);
}
＞頂点が増えたりしない限りはこれでいけるかな？
＞いや、だめか。プレイヤーが充分に動いた場合、三角形の頂点を結ぶ順番が変える必要があると思う。壁を回り込んだりとか。
最終的には、可視範囲の多角形領域がきちんと定義できて、その領域をうまく扱って地面や敵を明るく写したり、
不可視領域は真っ暗で見えなかったりすればそれでいいわけだから、Meshを描画する必要はないのかもしれないが、とにかくやり方を覚えて損はあるまい。
Unity学習 #9 2D Visibility More ログイン