私は現在、2D の架空の宇宙に数千の星がある趣味のプロジェクトに取り組んでいます。これらの星を画面にレンダリングする必要がありますが、すべての星を操作する必要はなく、常に表示されている星のみを操作する必要があることは明らかです。
概念を証明するために、すべての星を見て、プレイヤーの画面の境界に対してその座標をテストするブルート フォース アルゴリズムを作成しました。
for (const std::shared_ptr<Star>& star : stars_) {
if (moved_)
star->MoveStar(starfield_offset_, level_);
position = star->position();
if (position.x >= bounds_[0] &&
position.x <= bounds_[1] &&
position.y >= bounds_[2] &&
position.y <= bounds_[3])
target.draw(*star);
}
この不格好な方法は、実際には目に見える星だけを画面に描画しますが、明らかに線形時間で動作します。星は背景の一部にすぎず、率直に言って、プロセッサがフィルタリングに時間を費やす最も重要なものではないため、負荷を軽減するためのより高速なアルゴリズムを考案したいと考えています。
したがって、私の現在の考えは、バイナリ検索を使用して関連する星を見つける方法に沿っています。このためには、明らかにデータを並べ替える必要があります。ただし、座標データを並べ替える方法がよくわかりませんでした。(x 座標と y 座標の両方に関して) データを昇順で適切に並べ替えることができる絶対的な順序は考えられませんでした。 .
そこで、2 つの新しいコンテナーを実装しました。1 つは x 座標でソートされたデータ用で、もう 1 つは y 座標でソートされたデータ用です。私の最初の考えは、これらの 2 つの並べ替えられたセットの交点を取得し、結果の星を画面に描画することでした (x 座標と y 座標が画面の境界内にある星)。
struct SortedStars {
std::vector<std::shared_ptr<Star>>::iterator begin, end;
std::vector<std::shared_ptr<Star>> stars;
} stars_x_, stars_y_;
次に、これらのコンテナーを並べ替えました。
// comparison objects
static struct SortX {
bool operator() (const std::shared_ptr<Star>& first, const std::shared_ptr<Star>& second)
{ return (first->position().x < second->position().x); }
bool operator() (const std::shared_ptr<Star>& first, const float val)
{ return (first->position().x < val); }
bool operator() (const float val, const std::shared_ptr<Star>& second)
{ return (val < second->position().x); }
} sort_x;
static struct SortY {
bool operator() (const std::shared_ptr<Star>& first, const std::shared_ptr<Star>& second)
{ return (first->position().y < second->position().y); }
bool operator() (const std::shared_ptr<Star>& first, const float val)
{ return (first->position().y < val); }
bool operator() (const float val, const std::shared_ptr<Star>& second)
{ return (val < second->position().y); }
} sort_y;
void Starfield::Sort() {
// clone original data (shared pointers)
stars_x_.stars = stars_;
stars_y_.stars = stars_;
// sort as needed
std::sort(stars_x_.stars.begin(), stars_x_.stars.end(), sort_x);
std::sort(stars_y_.stars.begin(), stars_y_.stars.end(), sort_y);
// set iterators to the outermost visible stars (defined by screen bounds)
// these are updated every time the screen is moved
stars_x_.begin = std::lower_bound(stars_x_.stars.begin(), stars_x_.stars.end(), bounds_[0], sort_x);
stars_x_.end = std::upper_bound(stars_x_.stars.begin(), stars_x_.stars.end(), bounds_[1], sort_x);
stars_y_.begin = std::lower_bound(stars_y_.stars.begin(), stars_y_.stars.end(), bounds_[2], sort_y);
stars_y_.end = std::upper_bound(stars_y_.stars.begin(), stars_y_.stars.end(), bounds_[3], sort_y);
return;
}
残念ながら、std::set_intersection の適切な比較関数や、イテレータを使用して手動で座標を比較できる方法を思い付くことができないようです。
私を正しい方向に向けてもらえますか？私の方法論や実装に関するフィードバックは大歓迎です。
御時間ありがとうございます！