Collision Detection ?

[clzola]

Na prvi pogled, ne izgleda toliko strasno. Uzecu sve objekte koje imam i provjeriti svaki sa svakim, medjutim to je u redu za mali broj objekata, ali ako je broj objekata veci, ovo stvara jako veliki problem i usporava citav rad aplikacije/igre.

E sad treba mi neki savjet ka nekom dobrom Algoritmu za Collision Detection. Mene je palo na pamet neko resenje da vodim racuna o daljini objekata izmedju sebe, mada to opet dodje na isto kao sto sam gore naveo ... :/

[Geomaster]

2D ili 3D? Quadtree za 2D ili octree za 3D mogu da smanje broj objekata sa kojima testiraš, tako da je kompleksnost O(log n), gde je n ukupan broj nodova.

[EclipsE]

Ne postoji savršen algoritam za collision detection, sve zavisi od toga šta ti tačno treba. Nisi rekao da li radiš 2D ili 3D, pa ću se baciti na 2D plane (iako se sve ovo može primeniti i na 3D).

Prvo izabereš način predstavljanja objekta. Uglavnom bi imao jedan veliki bounding box koji obuhvata ceo objekat čisto da ne bi gubio vreme na pixel perfect collision detection ako objekti nisu ni blizu jedan drugom:



Sada ideš kroz svaki objekat i proveravaš ga sa ostalima. Ali, kao što si primetio, ukoliko je broj objekata izuzetno velik, performanse mogu da opadnu drastično.

Grid

Postaviš "grid" preko aktivne igrive površine, podeljen u kocke, nešto slično ovom:



Kao što vidiš, time što si podelio svet na gridove, vidiš da je nemoguće da se ovi "igrači" dodirnu. Kada proveravaš za koliziju, proveravaš samo objekte koji pripadaju nekom gridu.

Quadtree

Još bolja solucija. Sličan princip kao sa gridom, samo što veliki "svet" podeliš na četiri kvadranta, pa posle objekata ubačenih u neki kvadrant, podeliš njega na još 4 itd.



Malo moraš više da se igraš ovde sa ubacivanjem objekata u kvadrante. Kao što možeš da vidiš na slici, onaj krug je u dva kvadranta. Takođe, svaki put kad se neki objekat pomeri, moraš da rekalkulišeš kom kvadrantu pripada.

Octree

Isto kao quadtree, samo imaš 8 child kvadranata.

Collision groups

Podeliš tela na grupe. Recimo, znaš da se jedna zgrada nikada neće sudariti sa drugom zgradom osim ako nisu zgrade koje se kreću... ali to je previše weird

Time bi recimo, ako praviš neki space shooter i imaš 1000 metkova od strane protivnika, eliminisao protivničke letelice i uštedeo mnoogo na proveravanju kolizije za koju ne želiš da se bilo šta desi.

Ne znam šta više da kažem nisi pitao ništa konkretno, pa si dobio veoma uopšten odgovor.

[clzola]

Treba mi za 2D. Izvinjavam se sto nisam napomenuo..

Hvala na odgovorima !! pokusacu ovo da implementiram

[Geomaster]

Jedna stvar na koju bi trebao da obratiš pažnju je ako radiš sa dinamičnim okruženjima tj. kad se objekti pomeraju: ne možeš svakog frejma jednostavno da proveravaš koliziju - moguće je da u trenutku t objekat nije bio u koliziji, isto i u t+dt, ali da je u nekom trenutku između "prošao" kroz neki objekat. Trebao bi da uzmeš ceo opisani volume tog objekta tokom frejma (gde nailaziš na neke nepreciznosti ako koristiš Ojlerovu integraciju pa bih ti preporučio nešto kao RK4) i da testiraš koliziju sa njim. Za sâm test kolizije možeš prvo da suziš broj objekata pomoću quadtree-a a zatim da testiraš koristeći Bentley-Ottmann algoritam koji ti nalazi sve preseke u O(n log n) vremenu, ili da jednostavno quadtree namestiš tako da jedan nod sadrži po jedan objekat (ili deo objekta) pa tu jednostavno da dobiješ logaritamsko vreme, doduše od broja nodova koji može dosta da varira ako ti terminating condition bude da samo jedan objekat bude u nodu. Ako imaš tile-based sistem ili nešto slično, overi ovo, jako lepo objašnjenje jako praktičnog pristupa.

[irreal]

sve validni i veoma bitni saveti, samo bi jos dodao jednu stvar koju mnogi previde.

recimo da imas 3 objekta koja mogu da budu u koliziji.

ako radis proveru u fazonu svaki sa svakim, obrati paznju da ako proveris objekat 1 i objekat 2 da li su u koliziji, pa onda proveris objekat 1 i objekat 3, zavrsio si sa objektom jedan.

kada predjes na objekat 2 ne treba da ga prvo uporedis sa objektom 1 pa sa objektom 3 vec samo sa objektom 3


odnosno, drugim recima, ako si proverio obj 1 i obj 2, proverio si i obj 2 i obj 1

znam da zvuci mnogo glupo, al kolko sam samo puta video da ljudi ovo ignorisu i rade duple provere bez veze!

[chaami]

A možeš da koristiš već gotove biblioteke koje mogu sasvim lepo da ti završe posao. Imaš jako prostu biblioteku SDL_Collide koja je prilično ograničena a i vezana je za SDL. Sa druge strane imaš Flatland http://flatland.sourceforge.net/ koja već može da bude prilično korisna

[Geomaster]

^ To bi mu bila lakša varijanta, ali ja sam ipak za to da proba sam da uradi ovakve stvari. Mnogo će mu dobro doći to znanje kasnije.

[chaami]

^ Naravno, ali nije loše da analizira kako su to drugi uradili. Uostalom ni jedna od ovih biblioteka koje sam naveo nije kompletna. Što se 3D kolizije tiče za neke ozbiljnije stvari bi bilo previše naporno da sam razvijaš biblioteku. Odlična stvar je Bullet physics library http://en.wikipedia.org/wiki/Bullet_%28software%29

http://youtu.be/3Ilojin4vQ8

[clzola]

Hvala na odgovorima i savjetima. Gledao sam nesto ovaj QuadTree i razmisljao kako da ga implementiram... Ali ne znam kako bih ja drzao informacije o objektima koji se nalaze u tom kvadratu...

Da li da napravim ovakvu strukturu:

struct QuadTreeNode {
    std::list<Object*> m_objects;
    QuadTreeNode* ParentNode;
    QuadTreeNode* Childs; // Ovo bi bio niz.
    };

I onda da napisem funkcije koje bi dijelile ovaj nod na 4 manja i takodje provjeravala da li se objekat nalazi u kvadratu, i da li treba dalje dijeliti,kao i brisanje objekata iz liste... (cvora)

I da li se QuadTree Algoritam izvrsava svaki put kada se neki objekat pomjeri ... ?

[Geomaster]

// Pravougaonik
struct Rect
{
    Rect(float x1, float y1, float x2, float y2) : X1(x1), Y1(y1), X2(x2), Y2(y2) { ; }
    float X1, Y1, X2, Y2;
    
    Rect getIntersection(const Rect& other)
    {
        // ... podrazumevam da znaš ovo da iskodiraš
    }

    float getWidth() { ... }
    float getHeight() { ... }

};

// Pravougaoni deo nekog objekta
struct ObjectRect : public Rect
{
    Rect(float x1, float y1, float x2, float y2, Object* Parent) : X1(x1), Y1(y1), X2(x2), Y2(y2) { ; }

    Object* Parent;
};

struct QuadtreeNode
{
     // Delovi objekata unutar noda
     std::vector<Rect> ObjectRects;
     // Postoje li deca?
     bool HasChildren;
     // Pointeri ka 4 deteta
     QuadtreeNode*[4] Children;
     // Pravougaonik zahvaćen nodom
     Rect Area;
};

// Funkcija koja vraća true ako je zadovoljen terminating condition tj. uslov koji završava kreiranje quadtree-a
bool terminatingCondition(QuadtreeNode* Node) 
{ return Node->ObjectRects.size() < 2; }
// ili
{ return Node->Area.getWidth() * Node->Area.getHeight() < nekapovršina }
// ili nešto treće

void subdivideNode(QuadtreeNode *Node, const std::vector<Object*>& ObjectList)
{
    if (!terminatingCondition(Node))
    {
        QuadtreeNode* topLeft = new QuadtreeNode(), *topRight = new QuadtreeNode(), *bottomLeft = new QuadtreeNode(), *bottomRight = new QuadtreeNode();
        topLeft->Area = Rect(Node->Area.X1, Node->Area.Y1, Node->Area.X1 + Node->Area.getWidth() / 2.f, Node->Area.Y1 + Node->Area.getHeight() / 2.f);
        topRight->Area = Rect(Node->Area.X1 + Node->Area.getWidth() / 2.f, Node->Area.Y1, Node->Area.X2, Node->Area.Y1 + Node->Area.getHeight() / 2.f);
        // ... i tako dalje, i tako bliže ...

        Node->Children[0] = topLeft;
        Node->Children[1] = topRight;
        // (...)

        testObjectsInNode(topLeft, ObjectList);
        testObjectsInNode(topRight, ObjectList);
        // (...)

        subdivideNode(topLeft, ObjectList);
        // ... et cetera

    }
}

void testObjectsInNode(QuadtreeNode *Node, const std::vector<Object*>& ObjectList)
{
       for (std::vector<Object*>::const_iterator it = ObjectList.begin(); it != ObjectList.end(); ++it)
       {
             if (*it intersects with Node->Area)
             {
                    Node->ObjectRects.push_back(it->getIntersection(Node->Area));
             }
       }
}

Nije 100% tačno, ima malo pseudokoda, netestirano, ali samo kao ideja. Ne vidim na oči tako da ne zameri na nebulozama Što se tiče pomeranja objekata, ja bih u quadtreeu držao objekte koji se uopšte ili retko pomeraju. U suštini kada se objekat pomeri, brišeš ga iz svih nodova i onda kalkulišeš poziciju u O(log n) vremenu.