Diskuze: Výpočet kolizí
Luboš Běhounek Satik:25.12.2013 16:30
Podle typu hry a situace - pokud je to třeba pacman, tak zjistíš, kdo s kým kolidoval - pokud strašidlo se strašidlem, tak nic neřešíš, pokud pacman s puntíkem, nastavíš mu stav, že může žrát strašidla, pokud strašidlo s pacmanem, tak podle toho, v jakém je pacman stavu - buďto zavoláš konec hry (prohrál) a nebo zavoláš akci, kdy pacman sežral strašidlo...
To mě napadlo jako první, ale potom bych musel ve složitějších hrách, kde je objektů (druhů koliz) více, dělat každou kolizi zvlášť pro každý objekt. Takže jestliže by hra měl 10 objektů, tam se každý objekt může setkat s tím druhým, takže implementovat 100 kolizí se mě nezdá jako 2x vhodný způsob.
Luboš Běhounek Satik:25.12.2013 17:17
Jinak to bohužel nejde.
Nemusíš samozřejmě řešit 100x100 typů kolizí, pokud opravdu nemají všechny objekty se k sobě chovat různě, ale můžeš si objekty rozlišit do skupin, takže to pak zredukuješ na pár skupin - třeba hráč a nepřítel, hráč a tečka, hráč a bonusový objekt apod.
Vojtěch Pospíchal:25.12.2013 17:30
Zkus si objekty roztřídit do Tagů. V případě kolize kontroluješ jen s jakou skupinou Tagu objekt kolidoval. To ti kód především zpřehlední.
A jak se to řeší v kódu? Všechny objekty, které se můžou podílet na kolizi budou mít nějakou přetíženou funkci, kde budou postupně všechny jiné objekty?
class pacman {
void kolize(duch x);
void kolize(puntik x);
void kolize(stena x);}Nebo se to řeší nějakým jiným způsobem?
Patrik Valkovič:25.12.2013 18:53
Ale z toho stále vyplývá že budu mít ve třídě jednu metodu několikrát přetíženou pro každý druh kolize. Nebo se to řeší nějak jinak mimo tyto objekty? Neříkám že by to takhle nešlo, ale rád bych věděl jak se to řeší prakticky u velkých projektů.
Michael Olšavský:25.12.2013 19:00
Proč? Jako parametr bude objekt, který impletuje interface .
Patrik Valkovič:25.12.2013 19:26
Interface IColision
{
void kolize(IColision druhyObjekt);
public string typObjektu;
}
class nejakyObjekt : IColision
{
//nejakyMetody
public string typObjektu="hrac";
void kolize(IColision druhyObjekt)
{
//zde se musim stejne rozhodnout na jakou akci budu reagovat
if(druhyObjekt.typKolize=="stena")
this.vratitSeZpet();
else if (druhyObjekt.typKolize=="duch")
this.zemrit();
//atd
}
}
//zbytek kodu programu
//propocitani kolizi
kolizniPole [] pole=new kolizniPole[pocetPoli];
foreach(jednoPolicko policko in pole)
{
if(policko.jsouPritomnyDvaObjekty())
{
IColision prvniObjekt=policko.getPrvni();
IColision druhyObjekt=policko.getDruhy();
prvniObjekt.kolize(druhyObjekt);
druhyObjekt.kolize(prvniObjekt);
}
}Takto nějak bych to řešil právě teď, je to správně?
coells:25.12.2013 19:38
Řeší se to různě a záleží na tom, u kolika objektů se kolize
detekuje. Tyto algoritmy jsou hlavní částí herních enginů a jejich
rychlost bývá klíčová.
Jakkoliv hezký je design virtuální metody pro detekci, kterou si každý
objekt implementuje sám, můžeš to udělat pro řádově jednotky až
desítky objektů. Pokud jich je více, není to dobrý způsob, protože je to
velice pomalé.
Jeden způsob, jak implementovat velice rychlou metodu detekce kolizí, která bude fungovat i pro tisíce objektů (ve 2D):
- uděláš si dvě funkce pro detekci objektů:
funkce I) předběžná detekce kolize
funkce II) úplná detekce kolize
- předběžná detekce pouze porovná souřadnice X obou objektů a zjistí, jestli je vůbec možné, aby ke kolizi došlo, např: abs(A.x - B.x) <= (A.width + B.width)
- úplná detekce už dělá například detailní porovnání per pixel pro textury
- vytvoříš si jednorozměrné pole, do kterého si vložíš své objekty, u kterých detekuješ kolize
- objekty seřadíš v poli podle souřadnice X
- rychlý algoritmus na detekci:
for (int i = 0; i < objectArray.length; i++)
{
for (int j = i + 1; j < objectArray.length; j++)
{
if (!prematureDetection(objectArray[i], objectArray[j]))
break;
if (!fullDetection(objectArray[i], objectArray[j]))
break;
// KOLIZE mezi objectArray[i], objectArray[j]
}
}Tenhle postup má několik výhod:
- objectArray si můžeš udržovat průběžně, takže ho není třeba neustále třídit, vložení a odstranění prvků do setříděného seznamu lze dělat v očekávaném konstatním čase
- předběžná detekce objektů - funkce prematureDetection() - umožňuje rychlé zjišťování kandidátů, protože ne vždy tě zajímají přímo kolize, ale občas stačí seznam kandidátů
- samotný algoritmus ve většině času poběží v lineárním čase s velice nízkou konstantou
- nezapomeň, že tahle funkce poběží na 60FPS 60x za sekundu, pokud má pole 1000 prvků s velkou pravděpodobností častých kolizí, mohl bys mít detekce v řádu miliónu prvků za sekundu, takže sem patří řada dalších optimalizací podle chování enginu a hry
Patrik Valkovič:25.12.2013 19:47
Děkuji, to je velmi dobrá odpověď.
Nicméně tu zůstává otevřená otázka, co dělat po zjištějí kolize?
Výše jsem napsal jednu možnost, ale zdá se mi těžkopádné se rozhodovat
podle typu kolize (zvláště když třeba bude 100 druhů kolizí). Navíc,
kdybych přidal novou kolizi, musel bych všechny objekty znovu projet a
připsat ji tam.
coells:25.12.2013 20:09
Nedokážu si představit situaci, kdy by bylo 100 druhů kolizí. Většinou jich bude několik málo. A pokud u kolize různých objektů má program reagovat různě, pak je, samozřejmě, musíš všechny zpracovat.
V případě pac-mana by nebylo ani 5 typů objektů a 2 typy kolizí. Kvůli rychlosti se pak používá spíše vector execution (aka delegates). Takže objekt bude mít metodu update(), kterou si registruje do hlavního enginu. Engine pak volá update() před každým vykreslením framu. Objekt se potom chová autonomně a stará se sám o sebe.
- pac-man během update() otestuje svůj pohyb, případně se pohne a zjistí své kolize s ostatními objekty (points nebo ghosts), pokud došlo k výjimečné situaci - kolizi, informuje nadřazený engine
- ghost se během update() pohybuje
- points (to, co pac-man žere) může po čase zmizet, takže update() může testovat životnost
No... a to je v podstatě celé. Algoritmus, který jsem uvedl v předchozím příspěvku, se dá použít i tady, a když pac-man testuje své kolize, bude to provedeno v konstatním čase.
Zobrazeno 13 zpráv z 13.