ゲーム用に2Dのタイルベースの地形システムを作成しています。ただし、ゲーム内の座標も使用しています。これは、バウンディングボックスを「タイル座標」にマッピングし、バウンディングボックスが接触する各タイルをヒットできるようにする必要があります（心配しないでください。kdツリーなどが機能します）。大丈夫）。固定小数点の「実世界」座標を使用して、各タイルを2 ^ nとしてカウントし、ビットを右シフトしてタイル座標に切り捨てることができます。最小のx、yペアと最大のx、yペアを使用してバウンディングボックスを形成します。R0それぞれと呼びますR1。
これは、タイルにマップされる座標R0: 0.8, 0.7を含むバウンディングボックスです。R1: 2.2, 1.7
さて、それは十分に簡単です。ただし、タイルを4つの三角形の象限に分割したいので、もっと面白いものを作成できます。各タイルは4つの三角形になるので、何らかの方法で2ビットで参照できると仮定しました（必ずしも私が示したものとは限りません）。これらの三角形に「ラベルを付ける」ために、できるだけ少ないビットを使用したいと思います。タイル座標のすぐ隣にあるポイントの三角形ラベルを[XX]の形式で配置します。この場合、XXはどの三角形であるかを示すビットです。
しかし、これを使用するといくつかの問題が発生しました。実世界のバウンディングボックスの座標を「三角形の座標」に変換できるようにする必要がありますが、バウンディングボックスを完全に説明するには損失が大きすぎるようです。三角形の土地の同じ座標は、異なる三角形と衝突する境界ボックスを表すことができます。
R0: 0.8, 0.7左側には以前と同じ最初のバウンディングボックスがあります。R1: 2.2, 1.7
右側には、に新しいバウンディングボックスR0: 0.8, 0.3がR1: 2.2, 1.7あるため、左上隅のyコンポーネントが上に移動します。どちらも同じ三角形の座標に変換されますが、実際の座標で行われると、異なる三角形と衝突します。ただし、三角形の座標は区別されないため、データが失われ、誤った一連の衝突が生成されます。
さらに、同じ三角形で開始および終了するバウンディングボックスでも同じ問題が発生します。同じ三角形の座標は、完全にその三角形に含まれる場合と含まれない場合がある境界ボックスを表します。
kd-tree rangeクエリで実行されるすべての三角形座標の比較が、実世界の境界ボックスが実世界の座標で同じ三角形とどのように衝突するかを一致させることができるように、おそらくより多くのビットを使用して、これらをマッピングする方法が必要です。しかし、私は途方に暮れています。
うさぎの穴を下って「サブタイル」を作成し、各タイルを4つの軸に沿った正方形に分割しました。また、交差する軸に沿って各象限タイルを2つに分割しました。これは、多くの場合、どちら側がわからないことが原因であることに気付いたためです。私の座標がマッピングされた各三角形。
しかし、これまで以上に詳細なルールを例外として例外を追うと、最終的にサブタイルを同じ4つの三角形の象限デザインに変え、小さなタイルを除いて、最初の場所に行き着きました。
私は、この「圧縮」を達成し、適切な比較を行うことが可能でなければならないことを知っていますが、私は試みるたびに円を描き続けます。どうすればいいですか？
編集：
Alexeyは、バウンディングボックスを記述できるソリューションを提案しましたが、kdツリーを使用してバウンディングボックスのオーバーラップを見つけることとは互換性がありません。kdツリー（左上と右下の座標を格納する）範囲クエリと検索領域[x0, y0], [x1, y1]を使用して、範囲クエリを実行します。
[0, 0, x1, y1]に[x1, y1, xmax, ymax]
しかし、8次元座標を補正しようとしても、Alexeyのソリューションはこれでは機能しません。
三角形の象限でも同じ結果が得られる限り、座標系が当初考えていたものと多少異なっていてもかまいません。