２Dゲームでマップ上の近いものだけ判定する方法。

Question

提示コードですがmStageが一万要素ある為マップとプレイヤーやマップと敵などを最初から当たり判定していると負荷が大きく処理が重たいのですがどうすればマップ上でプレイヤーに近いものだけを当たり判定出来るのでしょうか？　提示画像のようなゲームの場合左上から当たり判定をしていると。１万要素のベクターを当たり判定していると重たくなるので近いものだけを判定させたいです。

質問内容　[ 近いものだけど判定する場合どういった手法で行えばいいのか？ ]

	std::shared_ptr<Stage> stage;			//ステージ

//エネミーとの当たり判定
void Stage::ColEnemy(std::shared_ptr<Enemy_Mng> enemy)
{
	//MapChip chip;
	for (std::vector<MapChip>::iterator itr = mStage->begin(); itr != mStage->end(); itr++)
	{
		 //chip = *itr;
		for (std::vector<Enemy>::iterator it = enemy->getEnemy()->begin(); it != enemy->getEnemy()->end(); it++)
		{
			//交差判定
			if (Box_Collision::Intersect(*itr->mCol, it->mCol) == true )
			{
				switch (itr->mCol->getObjectType())
				{
					//ブロック
				case StageObjectType::Block:
				{
					glm::ivec2 pos = itr->mCol->getPosition();
					it->FixPos(pos);	//座標を修正
					it->setMove_Rand();					//乱数を再設定
					it->setMovePixel();					//移動量をリセット
				}break;

					//レンガ
				case StageObjectType::Brick:
				{
					glm::ivec2 pos = itr->mCol->getPosition();
					it->FixPos(pos);	//座標を修正
					it->setMove_Rand();					//乱数を再設定
					it->setMovePixel();					//移動量をリセット

				}break;


				}
			}
		}
	}
}

//エネミーのバレットとの当たり判定
void Stage::ColEnemy_Bullet(std::shared_ptr<Enemy_Mng> enemy)
{
	//ステージ
	for (std::vector<MapChip>::iterator st = mStage->begin(); st != mStage->end(); st++) 
	{
		//エネミー
		for (std::vector<Enemy>::iterator itr = enemy->getEnemy()->begin(); itr != enemy->getEnemy()->end(); itr++)
		{
			//バレット
			for (std::vector<Bullet>::iterator b = itr->getBullet()->begin(); b != itr->getBullet()->end(); b++)
			{
				//交差判定
				if (Box_Collision::Intersect(b->mCol, *st->mCol) == true)
				{
					b->setPosition(b->getPosition());
					b->mIsMapHit = true;
				}
			}
		}
	}
}

Comments

[退会済みユーザー]

提示文章を修正しました。

[退会済みユーザー]

以前の質問の回答にも書きましたが、リリースビルドで問題ない速度になることから、1万件の判定自体が問題ではありません。

それでも、自、敵、それぞれの弾と計4回、1万件のループ回すなどは筋が悪い方法だと思います。
加えて、当たり判定のIntersectの箇所なども、getPosition、getSizeの呼び出しが多く、
コピーが多く発生するため、修正するほうがベターです。
あとはScrollも重かったので、1万件回している中の処理を見直すほうがいいと思います。

[fana]

入れ子のforの順番に関して，
mStage　に関するループを一番内側に入れるべきではないかな．

Answer 1

もしMapChipがすべて等間隔で並んでいるなら、BulletやEnemy の座標周辺のMapChipを簡単に取り出せるはずです。その周辺MapChipとだけ当たり判定すればよいのでは。
(画像から等間隔だと判断しましたが、そういうのは前提条件として質問文に書くべきです。)

たとえばMapChipが MAP_CHIP_SIZE 四方のサイズで、ステージが 100x100 で構成されているなら、座標 (x, y) の MapChip は (*mStage)[floor(x / MAP_CHIP_SIZE) + floor(y / MAP_CHIP_SIZE) * 100] ですよねたぶん。

Answer 2

どうすればマップ上でプレイヤーに近いものだけを当たり判定出来るのでしょうか？　提示画像のようなゲームの場合左上から当たり判定をしていると。１万要素のベクターを当たり判定していると重たくなるので近いものだけを判定させたいです。

「近い物」を列挙できるようなデータ構造なりを用意すれば良い，という話にしかならないような気がします．

マップの地形（ブロックみたいなの）の配置が２次元グリッド座標的であるならば，単純にはマップの地形を２次元の配列のような形で表現することもできるでしょう．
そのようなマップ情報のデータを，例えば

//横6 x 縦4 マスのマップ地形情報
const unsigned char Map[4][6] = { ... };

みたく保持しているとすれば，
ある対象に関する判定を行う際に，6x4=24マス全てをチェックせずとも，
「近い」範囲を絞り込んで，その範囲内のマスだけをチェックすることは簡単です．

//マップの一部分（x0～x1, y0～y1）だけを走査
for( int y=y0; y<=y1; ++y )
{
  for( int x=x0; x<=x1; ++x )
  {
    Map[y][x]に関する判定
  }
}

この場合，提示画像の戦車のようなサイズのキャラクターであれば，最大2x2=4マス程度の範囲だけのチェックで済むのかもしれません．

Comments

[退会済みユーザー]

ベクターを二次元にして今の座標割ることの画面のチップサイズである６４で割って。その数字をの場所とその数字の周りの数を比較すれば行けるのでしょうか？

[fana]

> ベクターを二次元にして

実際に２次元のデータ構造にせずともvectorの要素の走査範囲を絞り込むことはできるんじゃないかと想像しますが，
まぁそこはやりやすい形にすれば良いかと．

割ってどうのこうのという部分に関しては，意味合いはそんな話です．（具体的な算数部分はご自身で確認してください．）

[fana]

動的に場所が移動するオブジェクト間の判定（例えば，戦車と砲弾の当たり判定とか）に関しては，個数次第では総当たりでも速度的には問題ないかもしれませんが，
総当たりだと大量すぎて同様に重い！とかいう場合には，同じような考え方で判定を減らせばよいです．
（ゲーム全体の空間を適当に細かく区切って，各時刻で各オブジェクトがどの小空間にいるか，みたいな話．互いに遠く離れた小空間に属するオブジェクト間の判定はしなくていい）

[退会済みユーザー]

> 実際に２次元のデータ構造にせずともvectorの要素の走査範囲を絞り込むことはできるんじゃないかと想像しますが，

どういった情報をもとに行うのでしょうか？想像がつきません。

[fana]

vetorが１次元だとして，その中の要素の順序というのは，しっちゃかめっちゃかではなく，何らかのまともな順序になっているでしょうから，それに基づいて決定できますよね．

おそらく，
> //マップの一部分（x0～x1, y0～y1）だけを走査
することを考えたとき，
・y = y0
・x = x0 ～ x1
に相当する vectorのindexの範囲というのが算出できるでしょう．
同様に，
・y = y0+1
・x = x0 ～ x1
に相当する vectorのindexの範囲も算出できる…

…

・y = y1
・x = x0 ～ x1
に相当する vectorのindexの範囲も算出できる

といった感じに．