ゲームプレイの一部として光 (および影) を利用するゲームを作成することを計画していますが、それらを実装するための効率的なアルゴリズムは思いつかず、エレガントなソリューションがあると確信しています。
白い部分は直接光に照らされ、明るい灰色は直接照らされた壁に照らされ、暗い灰色は暗闇です。
それらの領域を効率的に見つけたいと考えています。(リアルタイム、ライトが移動可能)
現実的ではありませんが、それが私の問題を考える最も簡単な方法です。直接光と反射光を含む他の実装は大歓迎です。
...
私の最初の試みは、光から画面の周囲まで線を引き、それらが交差する最初の壁を見つけることです。しかし、壁の照明部分ごとにこのアルゴリズムを繰り返して「環境」光をマークすることは現実的ではありません。
また、ゲームは Flash であるため、GPU を利用できないと思います。
ライアンの答えに触発されました。
2D グリッドでは、画面のすべての点を点灯としてマークします。次に、画面上のすべての壁に対して (ポイントに近い順に) 影をその背後に描画します
。 . 次のステップのために影が描かれたすべての壁に印を付けます。これらはおそらく照らされた壁です。（次のパートの前にもう一度確認する必要があります）
点灯している線分 (壁) ごとに、最初に壁が線分と交差しているかどうかを確認します。交差点ごとに、照らされたセグメントを交差点で 2 つに分割します。
すべての線分の終点について、最初の部分を一時配列で繰り返し、最後にすべての点灯点を最終配列に追加します。
最初の部分は、画面上のすべてのポイントと壁上のすべてのポイントを一度に通過する必要があります。したがって、O(面積 + 壁の長さ) であり、シーンの複雑さ (壁の数と交差) に応じて、2 番目の部分は最初の部分を約 20 回適用する必要があります。
これはリアルタイムで機能する可能性がありますが、ライトが動いていない間に照らされた領域を保存してください。
すべての光の線を描く必要はありません。重要なものだけを描きます。たとえば、1 つの点光源と 1 つの線の場合、解決する必要があるのは 2 つの交点だけです。
反射照明の場合、強度 n の点光源から始め、この光が壁と交差するたびに、壁を小さなセグメントに分割し、照らされたセグメントに強度 n-1 の線形光源を追加します。これは、好きなだけ何度でも行うことができます。