NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Patrik Valkovič
Člen
Avatar
Patrik Valkovič:25.12.2013 16:19

Dobrý den, už nějakou dobu běhám na internetu a nemůžu nikde přijít na odpověď. Jak vypočítám kolize ve hře? Nejlépe vysvětlit na nějaké hře (pacman). Vím že si udělám kolizní mapu, poté do ní zasadím objekty, a jestli se budou dva překrývat, tak na ně zavolám kolizi. Tady jsem ale v koncích. Nevím co a jak zavolat, nebo jakou techniku k tomu použit.
Budu velmi vděčný za všechny rady. Diky :)

Odpovědět
25.12.2013 16:19
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
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...

Nahoru Odpovědět
25.12.2013 16:30
https://www.facebook.com/peasantsandcastles/
Avatar
Patrik Valkovič
Člen
Avatar
Patrik Valkovič:25.12.2013 16:34

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.

Nahoru Odpovědět
25.12.2013 16:34
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
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.

Nahoru Odpovědět
25.12.2013 17:17
https://www.facebook.com/peasantsandcastles/
Avatar
Vojtěch Pospíchal
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
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í.

 
Nahoru Odpovědět
25.12.2013 17:30
Avatar
Patrik Valkovič
Člen
Avatar
Patrik Valkovič:25.12.2013 17:35

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?

Editováno
Nahoru Odpovědět
25.12.2013 17:35
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
Michael Olšavský:25.12.2013 18:47

Znáš interface? To můžeš použít.

 
Nahoru Odpovědět
25.12.2013 18:47
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Michael Olšavský
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ů.

Nahoru Odpovědět
25.12.2013 18:53
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
Michael Olšavský:25.12.2013 19:00

Proč? Jako parametr bude objekt, který impletuje interface .

 
Nahoru Odpovědět
25.12.2013 19:00
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Michael Olšavský
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ě?

Nahoru Odpovědět
25.12.2013 19:26
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
coells
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
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):

  1. uděláš si dvě funkce pro detekci objektů:

funkce I) předběžná detekce kolize
funkce II) úplná detekce kolize

  1. 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)
  2. úplná detekce už dělá například detailní porovnání per pixel pro textury
  1. vytvoříš si jednorozměrné pole, do kterého si vložíš své objekty, u kterých detekuješ kolize
  2. objekty seřadíš v poli podle souřadnice X
  3. 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:

  1. 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
  2. předběžná detekce objektů - funkce prematureDetec­tion() - 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ů
  3. samotný algoritmus ve většině času poběží v lineárním čase s velice nízkou konstantou
  4. 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
 
Nahoru Odpovědět
25.12.2013 19:38
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na coells
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.

Nahoru Odpovědět
25.12.2013 19:47
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
coells
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
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.

  1. 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
  2. ghost se během update() pohybuje
  3. 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.

 
Nahoru Odpovědět
25.12.2013 20:09
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 13 zpráv z 13.