Detekce kolizí: Porovnání verzí

Smazaný obsah Přidaný obsah
JAnDbot (diskuse | příspěvky)
m {{Autoritní data}}
Tergas (diskuse | příspěvky)
Funkce návrhy odkazů: Přidáno 10 odkazů.
značky: editace z Vizuálního editoru editace z mobilu editace z mobilního webu Editační tipy Doporučeno: Přidaný odkaz
Řádek 1:
Ve [[Výpočetní geometrie|výpočetní geometrii]], [[Videohra|počítačových hrách]] a [[Počítačová simulace|fyzikálních simulacích]] označuje pojem '''detekce kolizí''' [[Algoritmus|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é [[Space partitioning|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á hra|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 [[pixel]]y, 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<sup>2</sup>). 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 [[Space partitioning|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.<ref>{{Citace elektronického periodika
| titul = 2D collision detection - Game development {{!}} MDN
| periodikum = developer.mozilla.org