Detekce kolizí

Ve výpočetní geometrii, počítačových hrách a fyzikálních simulacích označuje pojem detekce kolizí algoritmy pro zjištění kolize dvou objektů, tj. zda existuje průsečík dvou daných těles.

Detekce kolizí je základním prvkem 3D a 2D počítačových her. Bez ní by například postavy mohly procházet zdmi a jinými překážkami.

Pro urychlení výpočtu se obvykle používá metody zvané dělení prostoru.

Úvod do problematiky

Ve fyzické simulaci se provádějí experimenty, jako je hraní kulečníku . Fyzika odrážení kulečníkové koule je dobře známa. Úvodní popis situace by byl proveden s velmi přesným fyzikálním popisem kulečníkového stolu a míčků a jejich počátečními polohami. Vzhledem k síle aplikované na bílou kouli (pravděpodobně v důsledku toho, že hráč zasáhl bílou kouli svým tágem), chceme vypočítat trajektorie, přesný pohyb a případná konečná místa všech koulí pomocí počítačového programu . Program pro simulaci této hry by sestával z několika částí, z nichž jedna by byla zodpovědná za výpočet přesných dopadů mezi kulečníkovými koulemi. Malá chyba v jakémkoli výpočtu způsobí drastické změny v konečné poloze kulečníkových koulí. Videohry mají podobné požadavky, s některými zásadními rozdíly. Zatímco počítačová simulace potřebuje simulovat fyziku reálného světa co nejpřesněji, počítačové hry musí simulovat fyziku reálného světa přijatelným způsobem, v reálném čase a robustně. Kompromisy jsou povoleny, pokud je výsledná simulace uspokojivá pro hráče hry a nenarušuje jeho herní zážitek.

Detekce kolizí ve 2D hrách

Ve hrách se často pro detekci kolizí objektů používají zjednodušené geometrické tvary, jednak se u nich kolize detekuje jednodušeji a zároveň to šetří výpočetní výkon. V některých případ je potřeba detekovat kolizi opravdu přesně a pak se místo zjednodušených tvarů, které v podstatě aproximují tvar objektu, používá takzvaná pixel-perfect kolize, která detekuje kolizi pomocí jednotlivých pixelů.

Kolizním tvarům, přiřazeným nějakému objektu za účelem detekce kolizí, se často říká například hitbox nebo collision box případně bounding box. Nejčastěji se jako tvar používá obdélník, i když kolize není přesná na pixely, tak je to většinou dostatečně přesné a hráč si toho často ani nemusí všimnout, ale záleží na konkrétní situaci. Mezi další používané tvary patří například kružnice nebo  trojúhelník a pro složitější tvary i konvexní mnohoúhelník (polygon).

Optimalizace

Je velice neefektivní se neustále snažit detekovat kolize všech objektů se všemi ostatními objekty ve scéně či v prostoru.  Asymptotická složitost tohoto přístupu je O(n²). Proto se obvykle detekování kolizí rozděluje na dvě fáze.

První fáze, takzvaná broad fáze má za účel zjistit, jaká množina objektů může být v kolizi. Za tímto účelem se využívají metody pro rozdělení prostoru. K tomu se často využívá datových struktur jako je například Quadtree, Octree, R-tree nebo Spatial Hashmap. Potom co se vyberou objekty, které by mohly být v kolizi, jelikož se nachází například ve stejné části rozděleného prostoru, následuje takzvaná narrow fáze. V této fázi dochází už přímo k detekci kolizí mezi jednotlivými objekty, za pomoci různých metod, které jsou dále popsány.^[1]

Metody detekce kolizí

Kolize dvou kružnic

Asi nejjednodušší je detekování kolize dvou kružnic. Jestli se kružnice dotýkají nebo dokonce překrývají zjistíme snadno a to tak, že porovnáme vzdálenost středů kružnic se součtem poloměrů obou kružnic.  Pokud je vzdálenost středů kružnic menší nebo rovna součtu jejich poloměrů, pak nastala kolize. Níže vidíme ukázkový kód (kód se nezabývá problematikou porovnávání čísel s plovoucí čárkou).

	private void DetectCollision(Circle c1, Circle c2) {
		var dx = c1.X - c2.X;
		var dy = c1.Y - c2.Y;
		double distance = Math.Sqrt(dx * dx + dy * dy);
		if (distance <= c1.Radius + c2.Radius) {
			// kolize detekována
		}
	}

Osově zarovnané obdélníky(Axis-Aligned Bounding Boxes)  

Jedná se o další jednoduchý případ, kdy dva obdélníky (mohou být i čtverce) jsou osově zarovnané, tedy nemají žádnou rotaci. Detekce kolize probíhá na základě kontroly pozice opačných hran jednotlivých obdélníků. Princip je znázorněn v ukázce kódu níže.

	public void DetectCollision(Rectangle r1, Rectangle r2) {
		if (r1.X <= r2.X + r2.Width && //je levá hrana r1 NALEVO od PRAVÉ hrany r2?
			r1.X + r1.Width >= r2.X && //je PRAVÁ hrana r1 NAPRAVO od LEVÉ hrany r2?
			r1.Y <= r2.Y + r2.Height && //je HORNÍ hrana r1 NAD SPODNÍ hranou r2?
			r1.Y + r1.Height >= r2.Y) { //je SPODNÍ hrana r1 POD HORNÍ hranou r2?
				// kolize detekována!
		}
	}

Kružnice  a osově zarovnaný obdélník

Pokud máme obdélník, který je osově zarovnaný dle osy x a osy y a není tedy nijak zrotovaný, je detekce kolize mezi kružnicí a tímto obdélníkem poměrně jednoduchá. Dle pozice kružnice vůči obdélníků testujeme danou hranu. Tedy například, pokud je kružnice nalevo od obdélníku, testujeme průnik kružnice s levou hranou obdélníku.  Analogicky to platí i pro další polohy kružnice. Pokud by ale obdélník nebyl osově zarovnaný, je nutné použít složitější metody detekce kolizí, lze použít například teorém separace os (SAT theorem).

public Boolean DetectCollision(Circle c, Rectangle r) {
	//pomocné proměnné pro nastavení, které hrany se budou testovat
	float testX = 0;
	float testY = 0;

	// která hrana je nejblíže?
	if (c.X < r.X)                 testX = r.X;      // budeme testovat levou hranu
	else if (c.X > r.X + r.Width)  testX = r.X + r.Width;   // budeme testovat pravou hranu
	if (c.Y < r.Y)                 testY = r.Y;      //budeme testovat horní hranu
	else if (c.Y > r.Y + r.Height) testY = r.Y + r.Height;   //budeme testovat spodní hranu

	// vzdálenost k nejbližší hraně
	float distX = c.X - testX;
	float distY = c.Y - testY;
	double distance = Math.Sqrt( (distX * distX) + (distY * distY) );

	// pokud je vzdálenost menší než poloměr, došlo ke kolizi
	if (distance <= c.Radius) {
		//kolize detekována
		return true;
	}
	return false;
}

Teorém separace os

Tento teorém se využívá pro detekci kolizí konvexních polygonů. Zjednodušeně řečeno, teorém říká, že dva konvexní polygony se nepřekrývají(nekolidují), pokud mezi nimi existuje přímka(osa), na které se projekce obou polygonů nepřekrývají.  Představte si, že vezmete pochodeň a posvítíte ze strany na jednotlivé objekty, ty pak vrhají stín. A pokud se vám povede najít úhel, ze kterého je mezi stíny objektů mezera, pak objekty nekolidují.^[2][3]

Následující kroky popisují princip teorému separace os. Tyto kroky lze poměrně jednoduše převést do kódu.

1. Vybereme hranu a spočteme její normálový vektor, ten představuje osu, na kterou budeme provádět projekci.
2. Provedeme projekci každého bodu na nalezenou osu.
3. Provedeme projekci všech bodů druhého polygonu na nalezenou osu.
4. Zkontrolujeme, zda se, projektované "přímky" na osu, překrývají.

Pokud nalezneme alespoň jednu osu, kde není překryv, můžeme algoritmus ukončit s tím, že ke kolizi nedošlo. Pokud bychom ale měli situaci, kdy ke kolizi došlo, algoritmus by musel otestovat všechny osy, aby mohl říct, že kolize opravdu nastala. Detekce je přesná, ale algoritmus funguje jen pro konvexní polygony.  Je ale možné použít  pro složitější tvary více menších konvexních útvarů, kolizní tělo se nemusí skládat jen z jednoho objektu.  Tedy používání více kolizních těl není nic zvláštního, například postava ve hře může mít kolizní tělo pro samotnou postavu, ale zároveň je potřeba, aby šlo detekovat i kolizi, zda meč udeřil nepřítele, proto je nutné přidat kolizní tělo i meči.^[3]

Reference