2

線分がたくさんあります（壁、天井、床などのさまざまな表面を表します）。プレーヤーのバウンディングボックス内にある行を効率的に特定したいと思います。

（現在、私はすべての行を循環していますが、正しいのですが、非常に遅いことが証明されています）。

Javascriptにはいくつかのkd-treeおよびその他の空間インデックスがありますが、それらはすべて線ではなく点を格納します。

実際には、x軸でクエリするだけで済みます。ある種の1D範囲ツリーで十分です。

線などの形状を効率的に保存および取得するにはどうすればよいですか？

一度構築されると、インデックスはに追加されません。

4

1 に答える 1

2

全体的な空間拡張を適切に制御できる（つまり、最小値と最大値を知っていて、これらは増加しない）2次元だけでは、プレーングリッドやクワッドツリーなどのグリッドベースのアプローチが非常にうまく機能します。特に、クエリの半径（プレーヤーボックスのサイズ）がわかっている場合は、まさにこのサイズのグリッドが非常にうまく機能するはずです。

多くのゲームでは、バイナリ空間分割ツリーであるBSPツリーと呼ばれるものも使用されていました。ただし、パフォーマンスを向上させるために、このツリーは通常、レベルの構築時に事前に計算され、マップが読み込まれるだけです。

于 2013-01-01T16:35:13.953 に答える