x_oある場所からy_oの方向に線が突き出ていthetaます。世界は無限ではなく、境界があります。
線と交点が当たる最初の四角形を見つけたいです。
これは典型的な 2D ゲーム プログラミングの問題ですが、私が読める簡単な論文/チュートリアルはありますか? 検索ワードで困っています。
編集：レイキャスティングについて知っています。私が見ることができる非常に単純な実装はありますか? また、これを効率的に解決するための分析的な方法はありますか。最後に、長方形のみに頼らずに作成できる一般化はありますか(回転した長方形..、円など)
Edit2: また、マップと障害物を保存するための優れた効率的なデータ構造にも開かれています
あなたの世界を格子状に分割してみませんか。すべてのセルに、このセルに完全にまたは部分的にある障害物を格納します。これが検索構造になります。
(xo, yo) から方向 theta に光線 R を発射すると、(xo, yo) を含むセルの位置を特定することから始まります。次に、R とセルの間の交点 (つまり、R がセルを離れる場所) を計算し、R がセルを離れる側に応じて、その隣接セルを新しい現在のセルにします。このセルについても、R がセルを離れる場所などを計算します。
到達した各セルで、R がこのセルに保存されている障害物と衝突するかどうかを確認します。衝突している場合、レイは障害物と衝突しており、セルの移動を停止できます。
明らかに、これには、グリッドのセルを十分に小さくして、それぞれに少数の障害物しか含まれないようにする必要があります。障害物のサイズが大きく異なる場合は、通常のグリッドではなくQuadtreeの使用を検討できます。ただし、これにより、セルのトラバースがより複雑になります。
障害物の四角形をノードとエッジとして定義することで、牽引力を得ることができます。各コーナーは点 (ノード) であり、各辺はエッジです。ノードのコレクションを指定すると、エッジの線形方程式を生成できます。
次に、光線の既知の方程式を使用して、光線と各エッジの間に同時解があるかどうかを判断します。存在する場合、そのエッジはソリューション ポイントでの衝突の候補です。
さて、これらのエッジ方程式は実線です...長方形の辺は、線全体ではなく、その線の一部です。そう...
最後に、ソリューション ポイントがエッジ セグメントに含まれているかどうか (2 つのノード内にあるかどうか) を判断できます。存在する場合、候補エッジは実際の衝突エッジです。複数の衝突エッジが見つかった場合は、解点がレイの原点に最も近いものを選択します。