Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!
Werbeanzeige
Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »CBenni::O« (19.11.2012, 18:10)
Zitat
Space partitioning
The algorithm represented here uses space partitioning, which means it subdivides the screen into smaller regions. Each region then obviously contains a fewer number of objects. The collision checks for all the entities in the region (space garbage, alien spaceships, orks, whatever) are then performed by the brute force comparison – which is very efficient for a small number of objects.
Two other common spatial partitioning schemes are Binary Space Partitioning (BSP) and Quadtree/Octree Partitioning. All have in common that they recursively subdivide the space into smaller pieces. RDC however, does not construct a tree based structure and must be recomputed every frame. BSP and Quad trees on the other side are best used when precomputed since they are expensive to modify.
So first, we limit the number of collision checks by using spatial partitioning and second, we wrap each object in a bounding shape (e.g. bounding sphere) to quickly eliminate objects that aren’t colliding.
RDC has an average time complexity of:
While the number of tests using brute-force alone explodes, RDC method increases approximately linearly.
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »CBenni::O« (20.11.2012, 23:01)
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
/******************************************************************** created: 2011/06/29 created: 29:6:2011 20:07 file base: RDC file ext: h author: Marcus Finzel purpose: recursive dimensional clustering for fast collisions detection *********************************************************************/ #pragma once #define MAX_PAIRS 2000 #define MAX_BRACKETS 210000 // a pair of Objects class CPairs { public: CPairs(); CPairs(CUnknownObject* pObjA, CUnknownObject* pObjB); void Set(CUnknownObject* pObjA, CUnknownObject* pObjB); CUnknownObject* m_pObjA; CUnknownObject* m_pObjB; }; class CBracket { public: int KindOfBracket; int Value; CUnknownObject* pObj; private: }; int _cdecl CompareFunction(const void* el1, const void* el2); class CRDC { public: CRDC(); ~CRDC(); // run the RDC function to search collision pairs // pPairs hold the final pairs // pGroup is the current group of objects // pSubGroup hold the final groups // axis1 is the axis to analyze in this function (can be X_AXIS, Y_AXIS, INVALID_AXIS) // axis2 will be analyzed in recursive calls bool run(CPairs * pPairs, CGrowableArray<CUnknownObject*>* pGroup, int Axis1, int Axis2,bool bBruteForce); GET_SET_ACCESSOR(unsigned int, nCalls); GET_SET_ACCESSOR(int, nSubDiv); GET_SET_ACCESSOR(int, nCollisions); private: // find and add sorted open/close boundaries int FindOpenCloseBoundaries(int Axis, CGrowableArray<CUnknownObject*>* pGroup, CBracket* pBoundaries); void CheckIntersectionBF(CGrowableArray<CUnknownObject*>* pSubGroup); CPairs m_Pairs[MAX_PAIRS]; int m_nCurrentPairs; unsigned int m_nCount; // counter for brackets int m_nNewAxis1; int m_nNewAxis2; unsigned int m_nCalls; CBracket m_BracketList[MAX_BRACKETS]; int m_nCollisions; int m_nRunCall; int m_nSubDiv; }; |
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 |
/******************************************************************** created: 2011/06/29 created: 29:6:2011 20:07 file base: RDC file ext: cpp author: Marcus Finzel purpose: recursive dimensional clustering for fast collisions detection *********************************************************************/ #include "includes.h" int _cdecl CompareFunction(const void* el1, const void* el2) { if(((CBracket*)el1)->Value < ((CBracket*)el2)->Value) return -1; else if(((CBracket*)el1)->Value > ((CBracket*)el2)->Value) return +1; return 0; } CPairs::CPairs() { m_pObjA = NULL; m_pObjB = NULL; } CPairs::CPairs(CUnknownObject* pObjA, CUnknownObject* pObjB) { Set(pObjA,pObjB); } void CPairs::Set(CUnknownObject* pObjA, CUnknownObject* pObjB) { m_pObjA = pObjA; m_pObjB = pObjB; } CRDC::CRDC() { m_nCurrentPairs = 0; m_nCurrentPairs = 0; m_nCount = 0; m_nNewAxis1 = 0; m_nNewAxis2 = 0; m_nCalls = 0; m_nRunCall = 0; m_nCollisions = 0; } CRDC::~CRDC() { } bool CRDC::run(CPairs * pPairs, CGrowableArray<CUnknownObject*>* pGroup, int Axis1, int Axis2,bool bBruteForce) { if(pGroup->GetSize()*2 >= MAX_BRACKETS) return false; // is size of group less then 15, brute force is faster // if INVALID_AXIS the function is ready if((pGroup->GetSize() < 10) || (Axis1 == INVALID_AXIS) || (bBruteForce)) { CheckIntersectionBF(pGroup); } else { int nBracketCounter; nBracketCounter = FindOpenCloseBoundaries(Axis1, pGroup, m_BracketList); if(nBracketCounter < 0) return false; // sort brackets qsort(m_BracketList,nBracketCounter,sizeof(CBracket),CompareFunction); m_nCount = 0; // counter for brackets m_nNewAxis1 = Axis2; m_nNewAxis2 = INVALID_AXIS; CGrowableArray<CUnknownObject*>* pSubGroup = new CGrowableArray<CUnknownObject*>; // subdivide the group if possible and call recursively for(int i=0; i < nBracketCounter;i++) { CBracket* pBracket = &m_BracketList[i]; m_nCalls++; if(pBracket->KindOfBracket == OPEN) { m_nCount++; pSubGroup->Add(pBracket->pObj); } else { m_nCount--; if(m_nCount == 0) { // found end of a cluster group, take subgroup and call recursively // get last object for check (-1, because array begins on 0 CBracket* pLastBracket = &m_BracketList[nBracketCounter-1]; if(pBracket->pObj != pLastBracket->pObj ) { // reconsider all other axis if(Axis1 == X_AXIS) { m_nNewAxis1 = Y_AXIS; } else if (Axis1 == Y_AXIS) m_nNewAxis1 = X_AXIS; } // next call run(pPairs, pSubGroup, m_nNewAxis1, m_nNewAxis2,bBruteForce); // clear subGroup pSubGroup->RemoveAll(); } } } SAFE_DELETE(pSubGroup); } m_nCurrentPairs = 0; return true; } int CRDC::FindOpenCloseBoundaries(int Axis, CGrowableArray<CUnknownObject*>* pGroup, CBracket* pBoundaries) { if(Axis == INVALID_AXIS) return -1; CUnknownObject* pTempObj = NULL; CBracket* pTempBracket = NULL; CRect2D* pBoundingRect = NULL; int nBracketCounter = 0; for(int i=0; i< pGroup->GetSize();i++) { // get object pointer pTempObj = pGroup->GetAt(i); if(!pTempObj) continue; ////////////////////////////////////////////////////////////////////////// // create new brackets ////////////////////////////////////////////////////////////////////////// // get bounding rect pointer pBoundingRect = pTempObj->GetBoundary(); // settings for OPEN bracket if(Axis == X_AXIS) { // OPEN Bracket pBoundaries[nBracketCounter].Value = (int)pBoundingRect->x0; // CLOSE Bracket pBoundaries[nBracketCounter+1].Value = (int)pBoundingRect->x1; } else if(Axis == Y_AXIS) { // OPEN Bracket pBoundaries[nBracketCounter].Value = (int)pBoundingRect->y0; // CLOSE Bracket pBoundaries[nBracketCounter+1].Value = (int)pBoundingRect->y1; } // OPEN Bracket pBoundaries[nBracketCounter].KindOfBracket = OPEN; pBoundaries[nBracketCounter].pObj = pTempObj; nBracketCounter++; // CLOSE Bracket pBoundaries[nBracketCounter].KindOfBracket = CLOSE; pBoundaries[nBracketCounter].pObj = pTempObj; nBracketCounter++; m_nCalls++; } return nBracketCounter; } void CRDC::CheckIntersectionBF(CGrowableArray<CUnknownObject*>* pSubGroup) { CRect2D *rc1, *rc2, rcResult; int nSize = pSubGroup->GetSize(); CUnknownObject* pSenderObj; CUnknownObject* pReceiverObj; if(pSubGroup) { // loop through array for(int a=0; a< nSize; a++) { pSenderObj = pSubGroup->GetAt(a); // if (pSenderObj->GetbCollide()) // continue; // loop through array for(int i=0; i< nSize; i++) { pReceiverObj = pSubGroup->GetAt(i); m_nCalls++; // skip same object if((!pReceiverObj)||(pReceiverObj == pSenderObj)) continue; //TODO: 06.12.2011 // if(pReceiverObj->GetKernel()->GetbAlive()) { if(pReceiverObj->GetbCollide()) continue; } rc1 = pSenderObj->GetBoundary(); rc2 = pReceiverObj->GetBoundary(); if(GetLength(pReceiverObj->GetvecPosition()-pSenderObj->GetvecPosition()) < ballNS::BALL_SIZE) //if(M3D::Intersect(rcResult, *rc1, *rc2)) { pSenderObj->SetbCollide(true); pReceiverObj->SetbCollide(true); pSenderObj->SetpKollPartner(pReceiverObj); pReceiverObj->SetpKollPartner(pSenderObj); //GetGameApp()->GetObjectManager()->SendMessage(pSenderObj, pReceiverObj, OM_COLLIDE); //GetGameApp()->CallGrafikDevice()->DrawTextLine(0,300,300,0,M3DCOLOR(1,1,1,1),"Collide"); //m_Pairs->Set(pSenderObj,pReceiverObj); m_nCurrentPairs++; m_nCollisions++; //GetGameApp()->CallGrafikDevice()->CallSpriteManager()->RenderQuad(M3DVector(rcResult.x0,rcResult.y0,0),16,16,m_pCol); // if (m_nCurrentPairs>=MAX_PAIRS) // break; } else { pReceiverObj->SetbCollide(false); pSenderObj->SetbCollide(false); pSenderObj->SetpKollPartner(NULL); pReceiverObj->SetpKollPartner(NULL); } }// end second loop }//end first loop }// end if(subGroup) } |
Werbeanzeige