タイルベースのゲームでどのタイルが照らされるかを計算する（＆＃8220;レイトレーシング＆＃8221;）
https://stackoverflow.com/questions/174659
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
小さなタイルベースのゲームを書いていますが、そのために光源をサポートしたいと思います。しかし、私のアルゴリズムfuは弱すぎるので、助けを求めてあなたのところに来ます。
状況は次のとおりです。タイルベースのマップ（2D配列として保持）があり、単一の光源といくつかのアイテムが含まれています。光源によって照らされているタイルと影になっているタイルを計算します。
それがどのように見えるかの視覚的補助。 Lは光源、Xは光を遮るアイテム、0は点灯したタイル、-sは影のタイルです。
0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -
もちろん、部分的に不明瞭になっているためにタイルが半影になる可能性がある場合、フラクショナルシステムはさらに優れています。アルゴリズムは完全である必要はありません-明らかに間違っていて合理的に高速ではありません。
（もちろん、複数の光源がありますが、それは単なるループです。）
受験者はいますか
解決
ローグライク開発コミュニティは、視線のアルゴリズムに少し執着しています。
この件に関するローグライクwiki記事へのリンクは次のとおりです。 http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
ローグライクゲームでは、シャドウキャストアルゴリズムを実装しました（ http：// roguebasin。 roguelikedevelopment.org/index.php?title=Shadow_casting ）Pythonで。まとめるのは少し複雑でしたが、（純粋なPythonでさえ）合理的に効率的に実行され、素晴らしい結果が生成されました。
「許容視野」同様に人気を得ているようです： http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View
他のヒント
オクルージョンの計算など、あらゆる種類の複雑な作業を行うことができます。または、単純なブルートフォースメソッドを使用することもできます。すべてのセルに対して、 Bresenham Line Algorithm を使用して、現在のセルと光源の間のすべてのセルを調べます。いずれかのセルが塗りつぶされている場合、または既にテストされて影にあることがわかっているセル（光源が1つしかない場合）のセルは影になります。点灯していることがわかっているセルに遭遇すると、セルも同様に点灯します。これを簡単に最適化するには、ラインに沿って出会うセルの状態を最終結果に合わせて設定します。
これは、多かれ少なかれ 2004 IOCCC受賞作品で使用したものです。ただし、これでは良いコード例にはなりません。 ;）
編集：ローレンが指摘するように、これらの最適化では、トレースするマップの端に沿ってピクセルを選択するだけです。
ここで紹介しているアルゴリズムは、必要以上に多くの計算をしているように思えます。私はこれをテストしていませんが、うまくいくと思います：
最初は、すべてのピクセルを点灯としてマークします。
マップの端にあるすべてのピクセルについて：Arachnidが示唆したように、Bresenhamを使用してピクセルからライトまでのラインをトレースします。その線が障害物にぶつかった場合、エッジから障害物のすぐ上までのすべてのピクセルを影の中にマークします。
手早く汚い：
（配列の大きさによる）
- 各タイルをループ
- 光に線を引く
- 行の一部がXにヒットした場合、それは影になります
- （オプション）：線が通過するXの量を計算し、空想的な計算を行って、影のタイルの割合を決定します。 NB：これは、しきい値設定手順中にタイルとライトの間の線をアンチエイリアシングする（したがって、光源に戻るルートに沿って他のタイルを見る）ことで、小さな異常として表示されます。使用するロジックに応じて、潜在的にタイルがどれだけ影になるかを決定できます。
テスト済みのピクセルを追跡することもできます。そのため、ソリューションを少し最適化し、ピクセルを2回再テストしないでください。
これは、画像操作を使用して、ピクセル（タイル）の間に直線を描画することにより、かなりうまくできます。線が半透明で、Xブロックが再び半透明の場合。画像をしきい値処理して、線が「X」と交差しているかどうかを判断できます
サードパーティのツールを使用するオプションがある場合は、おそらくそれを使用します。長い目で見ればより速くなるかもしれませんが、ゲームについてはあまり理解できません。
これはただの楽しみのためです：
最初にタイルを線に変換するステップを実行すると、Doom 3アプローチを2Dで複製できます。たとえば、
- - - - -
- X X X -
- X X - -
- X - - -
- - - - L
...三角形のソリッドオブジェクトの角を結ぶ3本の線に削減されます。
次に、Doom 3エンジンの機能を実行します。光源の観点から、各「壁」を検討します。それは光に面しています。 （このシーンでは、斜めの線のみが考慮されます。）そのような線ごとに、前端が元の線で、側面が光源から各端点までの線上にあり、後ろが台形である台形に投影します遠く、シーン全体を過ぎて。したがって、「指す」台形です。光。これには、壁が影を落とすすべてのスペースが含まれます。この台形のすべてのタイルを暗闇で満たします。
このような行をすべて実行すると、「ステンシル」になります。これには、光源から見えるすべてのタイルが含まれます。これらのタイルを明るい色で塗りつぶします。光源から離れるとき（「減衰」）にタイルを少し明るくしたり、他の派手なことをしたい場合があります。
シーン内のすべての光源に対して繰り返します。
タイルが影になっているかどうかを確認するには、光源に直線を戻す必要があります。線が占有されている別のタイルと交差する場合、テストしていたタイルは影になります。レイトレーシングアルゴリズムは、ビュー内のすべてのオブジェクト（タイルの場合）に対してこれを行います。
Wikipediaのレイトレーシングの記事には擬似コードがあります。 p>
これは非常にシンプルですが、画面上のタイルの数に線形時間を使用する非常に効果的なアプローチです。各タイルは不透明または透明（私たちに与えられる）であり、それぞれ表示または陰影付けすることができます（計算しようとしているものです）。
まず、アバター自体を「表示」としてマークします。
次に、この再帰ルールを適用して、残りのタイルの可視性を決定します。
- タイルがアバターと同じ行または列にある場合、アバターに近い隣接タイルが表示され、透明である場合にのみ表示されます。
- タイルがアバターから45度の対角線上にある場合、隣接する斜めのタイル（アバターに向かって）が表示され、透明である場合にのみ表示されます。
- 他のすべてのケースでは、問題のタイルよりもアバターに近い3つの隣接するタイルを考慮してください。たとえば、このタイルが（x、y）にあり、アバターの右上にある場合、考慮する3つのタイルは（x-1、y）、（x、y-1）、および（x- 1、y-1）。問題のタイルは、これらの3つのタイルのいずれかが表示され、透明である場合に表示されます。
この作業を行うには、特定の順序でタイルを検査して、再帰的なケースがすでに計算されていることを確認する必要があります。以下は、0（アバター自体）から始まり、カウントアップする正常な順序の例です。
9876789
8543458
7421247
6310136
7421247
8543458
9876789
同じ番号のタイルは、それらの間で任意の順序で検査できます。
結果は、美しいシャドウキャスティングではありませんが、信頼できるタイルの可視性を計算します。
TKのソリューションは、一般的にこの種のものに使用するソリューションです。
部分照明シナリオでは、タイルが影になる場合、そのタイルを4つのタイルに分割し、それぞれをテストすることができます。その後、必要なだけ分割できますか？
編集：
ライトに隣接するタイルをテストしないことで、少し最適化することもできます。これは、複数の光源がある場合に行うことがより重要だと思います...
最近、この機能をプロジェクトの1つに書きました。
void Battle::CheckSensorRange(Unit* unit,bool fog){
int sensorRange = 0;
for(int i=0; i < unit->GetSensorSlots(); i++){
if(unit->GetSensorSlot(i)->GetSlotEmpty() == false){
sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1;
}
}
int originX = unit->GetUnitX();
int originY = unit->GetUnitY();
float lineLength;
vector <Place> maxCircle;
//get a circle around the unit
for(int i = originX - sensorRange; i < originX + sensorRange; i++){
if(i < 0){
continue;
}
for(int j = originY - sensorRange; j < originY + sensorRange; j++){
if(j < 0){
continue;
}
lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j)));
if(lineLength < (float)sensorRange){
Place tmp;
tmp.x = i;
tmp.y = j;
maxCircle.push_back(tmp);
}
}
}
//if we're supposed to fog everything we don't have to do any fancy calculations
if(fog){
for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
}
}else{
bool LOSCheck = true;
vector <bool> placeCheck;
//have to check all of the tiles to begin with
for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
placeCheck.push_back(true);
}
//for all tiles in the circle, check LOS
for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
vector<Place> lineTiles;
lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y);
//check each tile in the line for LOS
for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){
if(false == CheckPlaceLOS(lineTiles[lineI], unit)){
LOSCheck = false;
//mark this tile not to be checked again
placeCheck[circleI] = false;
}
if(false == LOSCheck){
break;
}
}
if(LOSCheck){
Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
}else{
LOSCheck = true;
}
}
}
}
あなた自身の使用のためにそれを適応させるなら、あなたが必要としないだろういくつかの余分なものがあります。 Place型は、便宜上xおよびy位置として定義されています。
行関数は、非常に小さな修正を加えてウィキペディアから取得されます。 x y座標を出力する代わりに、ライン内のすべてのポイントを含む場所ベクトルを返すように変更しました。 CheckPlaceLOS関数は、タイルにオブジェクトがあるかどうかに基づいてtrueまたはfalseを返すだけです。これで行うことができる最適化がいくつかありますが、これは私のニーズには適しています。
これは長年の質問であることは知っていますが、このスタイルのものを探している人には、私がかつて自分のローグライクのために使った解決策を提供したいと思います。手動で「事前計算済み」視野。光源の視野に最大外側距離がある場合、オブジェクトをブロックすることによって作成された影を手で描くのは実際にはそれほど労力ではありません。円の8分の1（さらに直線と斜めの方向）を描くだけです。他の領域にsymmertyを使用できます。円の1/8にある正方形と同じ数のシャドウマップを作成できます。次に、オブジェクトに従ってそれらをORします。
このための3つの主要な長所は次のとおりです。 1.正しく実装すれば非常に迅速です 2.どのアルゴリズムがどの状況を最適に処理するかを比較することなく、シャドウの投影方法を決定することができます。 3.なんらかの修正が必要なエッジケースを誘発する奇妙なアルゴリズムはありません
欠点は、楽しいアルゴリズムを実際に実装できないことです。
iは、単一のC関数でタイルベースの視野を実装しています。ここにあります： https://gist.github.com/zloedi/9551625
これを再発明/再実装するのに時間を費やしたくない場合、たくさんのゲームエンジンがあります。 Ogre3D は、照明とサウンドおよびゲームコントロールを完全にサポートするオープンソースゲームエンジンです。
