Jak elegancko napisać kod sprawdzający kolizje przedmiotu z kilkoma innymi?

Question

Mamy 2 wymiarową płaszczyzne na której klikając lewy przycisk myszy tworze kwadrat 100x100 pikseli. Chciałbym żeby stawiając każdy kolejny kwadrat program sprawdzał czy postawiony obiekt nachodzi na inny który już tam się znajduje. Kod który sprawdza czy kwadrat A nachodzi na kwadrat B wygląda mniej więcej tak

class kwadrat
{
public:
int x, y, wysokosc, szerokosc;
};

bool czyObiektyNaSiebieNachodza(kwadrat A, kwadrat B)
{
if( A.x + A.szerokosc > B.x &&
    A.x  < B.x + B.szerokosc &&
    A.y + A.wysokosc > B.y &&
    A.y < B.y + B.wysokosc )
return true
else return false;
}

I załóżmy że mam tablice dynamiczną w której jest n takich kwadratów i chciałbym dorzucić kolejny. Żeby sprawdzić czy jeden nie nachodzi na drugi muszę stworzyć pętle która najpierw sprawdza czy nowy obiekt nie wchodzi w kolizje z kwadratem pierwszym, drugim, trzecim, czwartym... I tak n razy, czyli mniej wiecej tak:

kwadrat A;
kwadrat* B;

B = new kwadrat[ n ]; //n to ilosc kwadratow

for( int i = 0; i < n; ++i )
{
if( czyObiektyNaSiebieNachodza( A, B[ i ] )
{
cout << "Kwadrat A nachodzi na jeden z kwadratow B";
break;
}
}

Teraz mając już wszystko co potrzebuje chciałbym żeby za pomocą lewego przycisku myszy stawiać nowy kwadrat wielkości 100x100 pikseli. I tutaj pojawia się problem, nie mam pojęcia jak to elegancko zapisać, jedyne pomysły jakie mam to stworzyć zmienną typu bool przed pętlą, nadać jej wartość "false" i jeżeli podczas wykonywania pętli okaże się, że A nachodzi na B, to nadać tej zmiennej wartość "true" i po wykonaniu pętli warunek "if( czyNachodzi == false ){postawKwadrat( A )}".

Myślałem też o czymś typu

for( int i = 0; i < n; ++i )
{
if( czyObiektyNaSiebieNachodza( A, B[ i ] )
{
cout << "Kwadrat B nachodzi na jeden z kwadratow A";
break;
}
else if( i + 1 == n )
postawKwadrat( A );
}

Ale obie opcje wydają mi się takie nie do końca ładnie zapisane. Są jakieś lepsze, prostsze, bardziej przejrzyste sposoby zaprogramowania tego?

Answer 1

I załóżmy że mam tablice dynamiczną w której jest n takich kwadratów i chciałbym dorzucić kolejny. 

Zamiast tablicy użyj kontenera std::vector (<vector>). Będziesz mógł wygodnie dodawać elementy:

kwadrat square; 
std::vector<kwadrat> squares(5); 

// ...

bool kolizja = false;
for (std::size_t i = 0; i < squares.size(); ++i)
{
	if (czyObiektyNaSiebieNachodza(square, squares[i]))
	{
		std::cout << "Kwadrat B nachodzi na jeden z kwadratow A";
		kolizja = true;
		break;
	}
}

if (!kolizja) 
{
	squares.push_back(square); // lub squares.emplace_back(std::move(square));
}

Sposób nr1 który opisałeś jest rozsądniejszy. Natomiast możesz użyć algorytmu std::find_if (<algorithm>) i lambdy żeby zmniejszyć ilość linii kodu:

bool kolizja = std::find_if(squares.begin(), squares.end(), [&](auto s) {return czyObiektyNaSiebieNachodza(square, s); }) != squares.end()
if (!kolizja) // <- tu można wstawić to ^
{
	squares.push_back(square); // lub squares.emplace_back(std::move(square));
}

PS. Warunek sprawdzania kolizji możesz skrócić od razu zwracając wartość:

bool czyObiektyNaSiebieNachodza(kwadrat A, kwadrat B)
{
	return
		A.x + A.szerokosc > B.x &&
		A.x  < B.x + B.szerokosc &&
		A.y + A.wysokosc > B.y &&
		A.y < B.y + B.wysokosc
	;
}

Comments

Ten sposób z std::find_if wygląda bardzo ładnie. A jak sytuacja z kolizjami  wygląda w takich bardzo dużych programach albo silnikach do gier? Tam też używają find_if?

---

Tak aczkolwiek można tworzyć własne funkcje żeby jej wywołanie nie było aż tak długie. Pamiętaj, że funkcja find_if znajduje pierwszy element dla którego obiekt spełnia predykat. Jeżeli go nie znajdzie zwraca iterator ustawiony za końcem tablicy/kontenera. Dlatego w kodzie jest != squares.end(). Sama implementacja może wyglądać tak: link. 

W silnikach gier używa się STL. Tak samo jak w różnych bibliotekach od sprawdzania kolizji.