Collision detection, sortiranje objekata

Stručne teme
1

Pozdrav, odmah bi htio naglasiti da sam proučavao malo podjelu prostora na particije i metodu da se radi collision detekcija samo između objekata koji se nalaze u istim particijama. No nešto mi nije jasno.
Recimo da imamo 1000 objekata.
Razumijem da se tim pristupom izbjegava brute force petlja koja uspoređuje svaki objekt sa svakim (znači eliminirali smo 1000x1000 provjeru)…no svejedno postoji petlja koja mora proći kroz 1000 objekata i pogledati jeli isti u određenoj particiji. To je dakako manja petlja, no svejedno mi se čini suvišna …ili krivo razmišljam o tom djelu.

Mogao bi isti problem svesti na totalno drugačiji primjer. Recimo da imamo arkadu gdje colission detection treba provjeravati samo između glavnog lika (miki) i ostalih objekata te arkade. Neka je opet 1000 objekata.
Nema mi smisla provjeravati kontakt sa onim objektima koji su na kraju levela, ako je miki na početku levela i jako udaljen od tih nekih objekata. No kako znati koji objekti su blizu mikija bez provjere?

Jedna logika mi nalaže da u levelu 1 sigurno neću provjeravati kontakt s objektima koji se pojavljuju tek u levelu 2.
Logično, jer će se ti objekti iz levela 2 tek stovoriti kad level 2 započne.
No ako promatramo situaciju samo na razini levela 1, onda bi isto tako udaljene objekte mogao svrstati u neki array koji će imat smisla provjeravat tek kad se miki probliži određenom djelu levela?

2

Podijeli si level na dijelove, u multidimenzionalni array. Kako se krece samo provjeravas u kojem je dijelu i onda loopas objekte u tom dijelu. Odredi si koliko max objekata zelis u dijelu pa si po tome odredi kolki su tu dijelovi…

znaci array( array(#objekti u dijelu 1), array(#objekti u dijelu 2)…)

Tako ces si smanjiti loopove drasticno…

3

To mi vrijedi dok su objekti statični ili dok se kreću u nekom ograničenom intervalu. No što ako je njihova pojavka moguća bilo gdje u levelu koji promatramo?

4

Jednom si pogledaj ovu knjigu. Potraži je možda u knjižnici (NSK će je sigurno imati ako si u Zg).

Pa da, detekcija kolizije nije računski trivijalna.

Ako si se odlučio za podjelu prostora na particije, BSP stablo (binary space partitioning), onda ćeš pravokutnik scene staviti kao korijen stabla. Razdijelit ćeš ga u dva pravokutnika pravcem paralelnim se nekom od dvije osi pravokutnika. Ta dva nova pravokutnika su djeca ovome. Recimo da predmete koji su u jednom pravokutniku-djetetu vežeš uz jedan čvor, a predmete koji su u drugom pravokutniku-djetetu uz drugi čvor. Koliziju između tvog junaka i predmeta trebaš provjeravati samo s predmetima koji su u istom pravokutniku-djetetu u kojem je junak. Time si, ako su svi predmeti uniformno distribuirani, broj predmeta s kojima trebaš vršiti provjeru smanjio duplo. U stvarnosti ovo ide u više razina stabla i složenije je, ali to je osnovna ideja.

U načelu, kod svakog bi iscrtavanja trebao graditi ovo stablo iznova, odatle tih tvojih 1000 provjera. Ali uoči da su to provjere spada li neki objekt u neki pravokutni prostor, što se u ovom slučaju zapravo svodi na provjeru presjeca li pravac objekt, što je računski znatno jednostavnije nego dobra provjera kolizije između dva nepravilna objekta. Ali u ovisnosti o pravilima igre, tj. o tvoj znanju o mogućnostima gibanja predmeta i likova broj potrebnih provjera možeš reducirati. Npr. ako je objekt statičan, tijekom cijele razine će se nalaziti u istoj particiji, zar ne? Ako se giba po pravcu, konstantnom brzinom može preći samo u susjednu particiju.

Međutim, jednostavno je neusporediv algoritam složenosti O(n2) i algoritam složenosti O(n). Ako ti je i ovaj potonji prespor, odabrao si krivi programski jezik za grafiku. Ipak se, mislim, u JavaScriptu ili PHP-u još uvijek ne programira interaktivna grafika, čak niti ona 2D. Ili?

Google:

  • binary space partitioning
  • octree
  • scene graph
  • bounding volume

Ako se radi o 2D grafici, vjerojatno postoje značajna pojednostavljenja ovog problema. Nekada se 2D grafika temeljila na spriteovima gdje je detekcija kolizije vršena maskom. Svi “neprozirni” dijelovi lika se označe s 1, prozirni su nule. Preklapanje dva takva spritea je stvar puke operacije AND nad nizom bitova, što je ekstremno brzo. Ali općenio, u 3D svijetu, detekcija kolizije jest računski zahtjevan problem.

Google:

  • sprite collision detection

Napominjem da sam ja laik u području grafike, ovo su samo neki pabirci što sam ih skupio sa strane.

1 Like
5

Heh, nisam uopće čuo do sad za sprite collision…super da ima tako nešto :smile:
U svakom slučaju, hvala puno na opsežnom odgovoru!