home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / COLLISIO.TXT < prev    next >
Internet Message Format  |  1995-12-20  |  19KB

  1. Date: Mon, 27 Jun 1994 21:43:13 -0400
  2. From: Tom Moertel <thor@telerama.lm.com>
  3. Subject: Collision Detection - How?
  4.  
  5. Date: Mon, 4 Jul 1994 23:24:15 -0400
  6. Subject: Typo fixed with 2K(K-1) expansion
  7.  
  8. Many people have requested copies of my collision detection code.  I 
  9. suspect that it's of general interest for the readers of this 
  10. newsgroup, so I'm posting the code here along with a discussion 
  11. of the techniques it uses.  Please accept my apologies for the length 
  12. of this posting.
  13.  
  14. The code was written in C++ on a Macintosh, but I've endeavored to 
  15. keep the collision detection code close to ANSI C.  Porting it 
  16. should be a 30 minute affair.  The testing-timing harness is C++- 
  17. and Macintosh-specific, so it will take, say, an hour longer to 
  18. port that, if you feel so inclined.
  19.  
  20. OVERVIEW
  21.  
  22. Here's how the code works, roughly speaking.  The screen is divided 
  23. into "sectors," defined by a regularly-spaced grid.  All objects 
  24. (e.g., sprites) are placed into the appropriate sectors as determined 
  25. by the objects' upper-left corners.  Then the objects in each sector 
  26. are tested for collision with one another, taking advantage of the 
  27. observation that overlapping objects will usually be classified into 
  28. the same sector.  This isn't always the case, however, and the code 
  29. therefore makes well-behaved translations of the grid to ensure that 
  30. all collisions will be detected and that no false collisions will be 
  31. reported.
  32.  
  33. NOTES
  34.  
  35. The first thing to do when you get the code is to look at the 
  36. declaration of the "obj" structure.  It represents an on-screen 
  37. object.  For convenience's sake, I've made all my objects 30x30.  That 
  38. way I can define the x and y data members to be the upper-left corner 
  39. of an object's bounding rectangle, and when I need the lower-right, I 
  40. calculate it by adding 30 to x and y.  (That's the way I'd do it in a 
  41. shoot-'em-up, too.  Each class of objects would have a different size 
  42. associated with it.  E.g., for a bullet I'd add, say, 8 instead of 30 
  43. because they're smaller.)
  44.  
  45. I keep all the objects in a linked list, where the obj_link member is 
  46. the link between objects.  The sector_link is especially important.  
  47. It is used to keep all the objects in a sector in a single linked 
  48. list.  That's a key to making this collision detection technique 
  49. work quickly.  Placing each object in its containing sector takes O(1) 
  50. time, with a low constant, to boot.
  51.  
  52. With that in mind, here's an overview of the implementation:
  53.  
  54.     iterate four times, shifting the sector grid between iterations
  55.         place objects into the appropriate sectors
  56.         for each sector
  57.             check for collisions among its objects
  58.  
  59. You may find it interesting that I've chosen to repeat the entire 
  60. sectorization and per-sector collision checking process four times.  
  61. That's how I get around the problems associated with overlapping 
  62. objects that are placed into adjacent sectors.  Instead of testing for 
  63. collisions with objects in adjacent sectors, I just shift the entire 
  64. sector grid and repeat the process.  Before you accuse me of being 
  65. insane for this "four-shifts" business, you should know that it's 
  66. asymptotically 20 times faster than testing the adjacent sectors, and 
  67. about 40 times faster for the most common "real world" cases.  If 
  68. you're interested in my analysis, it's near the end of my notes. 
  69. Uninterested readers may feel free to skip it.
  70.  
  71. A side effect of the multiple iterations is that the same collision 
  72. will sometimes be reported more than once.  For example, if you have 
  73. two objects directly on top of each other, they will both be placed in 
  74. the same sector and detected as having collided, regardless of how the 
  75. sector grid is shifted.  The result: this particular collision will be 
  76. reported four times.  This isn't a big concern, and there are trivial 
  77. ways to sidestep the issue, but I think I'd be remiss if I didn't 
  78. point it out.  I'd hate to have people screaming because particular 
  79. bullets were packing four times the expected wallop, hurling their 
  80. innocent spaceships into oblivion.
  81.  
  82. ANALYSIS:  FOUR-SHIFTS vs. ADJACENT-SECTORS
  83.  
  84. Before you begin thinking that this shift-and-repeat technique is 
  85. terribly inefficient, consider the alternative, checking adjacent 
  86. sectors.  Let's say you've got a sector in the middle of the screen; 
  87. call it S.  Objects in S could collide with objects in adjacent 
  88. sectors, so you'd have to include all eight of them in your collision 
  89. testing of S.  How does that affect running time?
  90.  
  91. Assume that objects are randomly distributed over the screen and that 
  92. there are on average K objects in each sector.  Recall that to test 
  93. for collisions in each sector, we use a brute-force technique that 
  94. requires n(n-1)/2 rectangle intersection operations (check it) for n 
  95. objects.  Now we can compare the four-shifts method with the 
  96. test-adjacent-sectors method.
  97.  
  98. * Four-shifts method: each sector is checked by itself, at a cost of 
  99. K(K-1)/2 rectangle tests, but the process is repeated 4 times.  
  100. Consequently, the cost to entirely check a sector is 4 * K(K-1)/2 = 
  101. 2K(K-1) = 2K^2 - 2K.
  102.  
  103. * Adjacent-sectors method: Each sector is checked only once, but its 
  104. eight neighboring sectors are included in the check.  Define L = 
  105. (1+8)K be the average number of objects in these 9 sectors.  So the 
  106. cost per sector is L(L-1)/2 = (9K)((9K)-1)/2 = (81K^2 - 9K)/2.
  107.  
  108. Now, let's calculate the ratio of the two methods' expected 
  109. number of rectangle tests:
  110.  
  111.             cost of adjacent-sectors   (81K^2 - 9K)/2
  112.         R = ------------------------ = --------------
  113.               cost of four-shifts         2K^2 - 2K
  114.  
  115. Note that the limit of R as K -> Infinity is 20.25.  Asymptotically, 
  116. then, the four-shifts method is about 20 times faster than the 
  117. adjacent-sectors method.  Admittedly, it's unlikely you'll have an 
  118. infinite number of objects on the screen.  That fact begs the 
  119. question, how much faster is the four-shifts method for the more 
  120. common cases in which there are, on average, one, two, or three 
  121. objects in a sector? Answer: For one object, it's *much* faster; for 
  122. two, 38 x faster; for three, 30 x faster.
  123.  
  124. The four-shifts method needs to perform *no* tests when there's only a 
  125. single object in a sector---a very common case.  The adjacent-sectors 
  126. method, on the other hand, needs an average of 36 tests to handle the 
  127. same situation.
  128.  
  129. THE CODE
  130.  
  131. Here it is.  Enjoy.  And, let me know how it works on your 
  132. platform.  If you port the testing-timing harness, please send me 
  133. the timing results.
  134.  
  135. The code is broken into sections.  They are, in order:
  136.  
  137.     front matter        introductory comments
  138.     declarations        defines constants and parameters
  139.     test code           testing/timing harness (Mac specific)
  140.     sector code         code that puts objects into sectors
  141.     helpers             functions that are used by intersection code
  142.     intersection code   uses sector and helper code to determine
  143.                         object intersections and, hence, collisions
  144.  
  145. ======= begin
  146. // Sector-based collision detection routines &
  147. // timing code.
  148. //
  149. // Tom Moertel 21-Jun-94
  150. //
  151. // Results for a 25 MHz 68040 Macintosh (not
  152. // exactly a screamer) and an 80 MHz PPC 601
  153. // Power Macintosh 8100 (this one screams):
  154. //
  155. //                          tests/s
  156. //   object count        -68K-  -PPC-
  157. //
  158. //        0               611   7640
  159. //       50               340   4020
  160. //      100               189   2060
  161. //      200                81    788
  162. //
  163. // where a "test" is defined to be a complete
  164. // check of all objects, determining for each
  165. // object whether it is involved in a collision
  166. // (and if it is, with what other object).
  167. //
  168. // NOTES
  169. //
  170. // For this job I made all objects 30x30, but
  171. // the code will work for arbitrarily-sized
  172. // objects, with the restriction that objects
  173. // are smaller than half of kSectorSize.
  174. //
  175. // This code is far from optimized.  I didn't
  176. // even bother to run it through a profiler.
  177. // With a little work, it could probably be
  178. // twice as fast.
  179. //
  180. // LEGAL STUFF
  181. //
  182. // Feel free to use this code in your own
  183. // projects, but please give me credit.
  184. //
  185. // Copyright 1994 by Tom Moertel
  186. // moertel@acm.org
  187. //
  188. // PORTING
  189. //
  190. // Most of the "real" code is portable C++,
  191. // but the testing code uses some Mac-
  192. // specific calls, namely Microseconds()
  193. // and a few graphics and windowing calls.
  194. // To port to the timing code to your platform,
  195. // redifine Clock_us() to return the current
  196. // state (count) of a fast internal clock in
  197. // microseconds.  The Macintosh drawing
  198. // code will automaticaly compile out on
  199. // non-Mac platforms, so if you want pretty
  200. // pictures, you'll have to roll your own.
  201.  
  202. #include <iostream.h>
  203. #include <string.h>
  204. #include <stdlib.h>
  205. #include <math.h>
  206.  
  207. #if defined(macintosh) || defined(__MWERKS__)
  208. #include <Types.h>
  209. #include <Quickdraw.h>
  210. #include <Windows.h>
  211. #include <Events.h>
  212. #include <Timer.h>
  213. #endif
  214.  
  215. // define compilation parameters
  216.  
  217. #if defined(__MWERKS__) || defined (__SC__)
  218. #define BRAIN_DEAD_INLINING     // define this to declare "hot"
  219. #endif                          // functions as macros instead
  220.                                 // of C++ inline functions
  221.  
  222. // define test parameters
  223.  
  224. enum
  225. {
  226.     kMaxObjects     = 200,      // more than you're likely to need
  227.     kRectSize       = 30,       // each object is 30 x 30 pixels
  228.     kTBase          = 1000000L, // timing is in microseconds
  229.     kTestLength     = 30*kTBase,// 30 seconds per experiment
  230.     kCycleLength    = 50        // inner timing loop cycles 50 times
  231. };
  232.  
  233.  
  234. // types
  235.  
  236. #if defined(powerc) || defined (__powerc)
  237. typedef int scalar;         // fast integer type
  238. #else
  239. typedef short scalar;       // fast integer type
  240. #endif
  241.  
  242. // sprite object
  243.  
  244. struct obj
  245. {
  246.     scalar  x, y;           // coords
  247.     obj*    sector_link;    // link in sector list
  248.     obj*    obj_link;       // link in obj list
  249.     // ... other members ...
  250. } ;
  251.  
  252.  
  253. // module-scope globals
  254.  
  255. static obj      gObjects[kMaxObjects];
  256. static Boolean  gCollisionArray[kMaxObjects];
  257.  
  258. // forward declatations
  259.  
  260. static void _DetermineCollisions();
  261. static void _ShowLastIteration(scalar numObj);
  262. static void _RandomizeObjects(scalar numObj);
  263. static void _RunExperiment(scalar numObj, Boolean drawQ=false);
  264.  
  265. //==================================================================
  266. // test code
  267. //==================================================================
  268.  
  269. // returns a long representing a count of internal clock "ticks"
  270.  
  271. #if defined(powerc) || defined (__powerc)
  272. inline long Clock_us() { return TickCount() * (kTBase/60); }
  273. #else
  274. long Clock_us()
  275. {
  276.     static UnsignedWide base;
  277.     static Boolean initQ = true;
  278.     if (initQ)
  279.         Microseconds(&base), initQ = false;
  280.     UnsignedWide x;
  281.     Microseconds(&x);
  282.     return (x.lo - base.lo);
  283. }
  284. #endif
  285.  
  286. void main()
  287. {
  288.     srand((unsigned int) Clock_us());
  289.  
  290.     cout << "Collision testing..." << endl;
  291.     
  292.     _RunExperiment(  0, false);
  293.     _RunExperiment( 50, false);
  294.     _RunExperiment(100, false);
  295.     _RunExperiment(200, true ); // draw this one
  296. }
  297.  
  298. static void _RunExperiment(scalar numObjects, Boolean drawQ)
  299. {
  300.     if (numObjects > kMaxObjects)
  301.         return; // too many
  302.  
  303.     cout << (int) numObjects << " objects: ";
  304.  
  305.     long    endTime     = Clock_us() + kTestLength;
  306.     long    iterations  = 0;
  307.         
  308.     while (Clock_us() < endTime)
  309.     {
  310.         // don't count initialization time
  311.     
  312.         {
  313.             long t0 = Clock_us();
  314.             _RandomizeObjects(numObjects);
  315.             endTime += Clock_us() - t0;
  316.         }
  317.     
  318.         // test/timing loop
  319.         
  320.         scalar i;
  321.         for (i = 0; i < kCycleLength && Clock_us() < endTime; i++)
  322.             _DetermineCollisions(), iterations++;
  323.     }
  324.     
  325.     long totalTime = kTestLength + Clock_us() - endTime;
  326.     
  327.     if (drawQ)
  328.         _ShowLastIteration(numObjects); // draw results
  329.     
  330.     cout << (int) iterations << " in " << (int) totalTime
  331.          << " us:  ";
  332.         
  333.     float usec = totalTime;
  334.     float iter = iterations;
  335.     
  336.     cout.precision(2);
  337.     cout << usec/iter << " us/iter, "
  338.          << ((float)kTBase)*iter/usec << " iter/s" << endl;
  339. }
  340.  
  341. //==================================================================
  342. // sector code
  343. //==================================================================
  344.  
  345. #define CEILING_DIV(x, y) ( ((x)+(y)-1) / (y) )
  346.  
  347. // define constants
  348. //
  349. // Note that to work properly, kSectorSize must be greater
  350. // than twice the length of the largest side of any
  351. // object's bounding box.  E.g., if your objects are
  352. // 30x30, then the sector size should be > 60 -- 64 would
  353. // be an excellent choice.
  354.  
  355. enum {
  356.     kSectorSize     = 64,   // length of a sector's side in pixels
  357.     kLog2SectorSize =  6,   // log2(kSectorSize): for shifting
  358.     
  359.     kScreenWidth    = 640,
  360.     kScreenHeight   = 480,
  361.     
  362.     kNumXSectors    = CEILING_DIV(kScreenWidth, kSectorSize) + 1,
  363.     kNumYSectors    = CEILING_DIV(kScreenHeight, kSectorSize) + 1,
  364.     kNumSectors     = kNumXSectors * kNumYSectors
  365. } ;
  366.  
  367. // define a module-scope array of linked list heads,
  368. // one for each sector
  369.  
  370. static obj* gSectorArray[kNumXSectors][kNumYSectors];
  371.  
  372.  
  373. // call this routine to place all objects into the
  374. // appropriate sectors
  375. //
  376. // (assumes all objects are kept in a linked list and
  377. // GetMyFirstObject() returns the head of this list)
  378.  
  379. extern obj* GetMyFirstObject();
  380.  
  381. static void UpdateSectors(register scalar xoff, register scalar yoff)
  382. {
  383.     // reset the sectors' linked lists
  384.     
  385.     obj** theArray = (obj**) gSectorArray; // for 1-D access
  386.     for (scalar i = 0; i < kNumSectors; i++)
  387.         *theArray++ = NULL;
  388.     
  389.     // put each object in its sector's linked list.
  390.     
  391.     for (obj* o = GetMyFirstObject(); o != NULL; o = o->obj_link)
  392.     {
  393.         // get the list head for the sector in which o resides
  394.     
  395.         register obj** thisSectorListHead =
  396.             &gSectorArray [ (o->x + xoff) >> kLog2SectorSize ]
  397.                           [ (o->y + yoff) >> kLog2SectorSize ];
  398.         
  399.         // add o to this sector's linked list
  400.         
  401.         o->sector_link = *thisSectorListHead;
  402.         *thisSectorListHead = o;
  403.     }
  404. }
  405.  
  406.  
  407. //==================================================================
  408. // helpers
  409. //==================================================================
  410.  
  411. // Draw an object (rectangle).  If the object is involved
  412. // in a collision, it is drawn as a rectanglular outline;
  413. // otherwise it's drawn as a solid gray rectangle.
  414. // [Macintosh specific]
  415.  
  416. static void _DrawObject(obj* o, Boolean collidedQ)
  417. {
  418. #if defined(macintosh) || defined(__MWERKS__)
  419.  
  420.     static Pattern myBlack = { 0xff, 0xff, 0xff, 0xff,
  421.                                0xff, 0xff, 0xff, 0xff };
  422.     static Pattern myGray  = { 0xaa, 0x55, 0xaa, 0x55,
  423.                                0xaa, 0x55, 0xaa, 0x55 };
  424.     Rect r;
  425.     SetRect(&r, o->x, o->y,
  426.             o->x + kRectSize, o->y + kRectSize);
  427.  
  428.     PenPat(collidedQ ? &myBlack : &myGray);
  429.     
  430.     if (collidedQ)
  431.         FrameRect(&r);
  432.     else
  433.         PaintRect(&r);
  434.  
  435. #endif // macintosh
  436. }
  437.  
  438. // conciliate skeptics by showing them that the
  439. // code did, indeed, work properly
  440. // [Macintosh specific]
  441.  
  442. static void _ShowLastIteration(scalar numObjects)
  443. {
  444. #if defined(macintosh) || defined(__MWERKS__)
  445.  
  446.     Rect rBounds = { 0, 0, kScreenHeight, kScreenWidth };
  447.     OffsetRect(&rBounds, 0, GetMBarHeight());
  448.     WindowPtr wind = NewWindow(nil, &rBounds, "\p", true, plainDBox,
  449.                                WindowPtr(-1), false, 0);
  450.     GrafPtr savePort;
  451.     GetPort(&savePort);
  452.     SetPort(wind);
  453.     
  454.     for (scalar i = 0; i < numObjects; i++)
  455.         _DrawObject(&gObjects[i], gCollisionArray[i]);
  456.     
  457.     while (!Button())
  458.         ;
  459.     
  460.     SetPort(savePort);
  461.     DisposeWindow(wind);
  462.  
  463. #endif // macintosh
  464. }
  465.  
  466. static scalar _RandScalar(scalar max)
  467. {
  468.     return (((unsigned long) max) *
  469.             ((unsigned short) rand())) / (RAND_MAX+1);
  470. }
  471.  
  472. static void _RandomizeObjects(scalar numObjects)
  473. {
  474.     obj* o = gObjects;
  475.  
  476.     for (scalar i = 0; i < numObjects; i++, o++)
  477.     {
  478.         o->x        = _RandScalar(kScreenWidth-1);
  479.         o->y        = _RandScalar(kScreenHeight-1);
  480.         o->obj_link = o + 1;
  481.     }
  482.     
  483.     (--o)->obj_link = NULL;
  484. }
  485.  
  486.  
  487. //==================================================================
  488. // intersection code
  489. //==================================================================
  490.  
  491. obj* GetMyFirstObject() { return &gObjects[0]; }
  492.  
  493. // local helpers
  494.  
  495. static void _ClearCollisionArray();
  496. static void _UpdateCollisionArray();
  497.  
  498. // determine all collisions
  499.  
  500. static void _DetermineCollisions()
  501. {
  502.     _ClearCollisionArray(); // erase the slate; no collisions yet
  503.  
  504.     scalar shift = kSectorSize / 2;
  505.     
  506.     // We need to try four differnt "shifts" of the
  507.     // sector grid to detect all collisions.  Proof of
  508.     // why this is so is left as an excercise for the
  509.     // reader.  (Hint: consider an analogous 1-D case.)
  510.     
  511.     UpdateSectors(    0,     0),    _UpdateCollisionArray();
  512.     UpdateSectors(    0, shift),    _UpdateCollisionArray();
  513.     UpdateSectors(shift,     0),    _UpdateCollisionArray();
  514.     UpdateSectors(shift, shift),    _UpdateCollisionArray();
  515. }
  516.  
  517. // "hot" functions that are used in inner loops
  518.  
  519. #ifdef BRAIN_DEAD_INLINING
  520.  
  521. #define _Abs(a) ((a) < 0 ? -(a) : (a))
  522.  
  523. #define _IntersectQ(o1, o2)                     \
  524.             (_Abs(o1->x - o2->x) < kRectSize && \
  525.              _Abs(o1->y - o2->y) < kRectSize)
  526. #else
  527.  
  528. inline scalar _Abs(scalar a)
  529. {
  530.     return a < 0 ? -a : a;
  531. }
  532.  
  533. inline scalar _IntersectQ(obj* o1, obj* o2)
  534. {
  535.     return _Abs(o1->x - o2->x) < kRectSize &&
  536.            _Abs(o1->y - o2->y) < kRectSize;
  537. }
  538.  
  539. #endif // BRAIN_DEAD_INLINING
  540.  
  541.  
  542. static void _ClearCollisionArray()
  543. {
  544.     memset(gCollisionArray, 0, sizeof(gCollisionArray));
  545. }
  546.  
  547. static void _CalcCollisionsInSector(obj* objList);
  548.  
  549. static void _UpdateCollisionArray()
  550. {
  551.     for (scalar x = 0; x < kNumXSectors; x++)
  552.         for (scalar y = 0; y < kNumYSectors; y++)
  553.             _CalcCollisionsInSector(gSectorArray[x][y]);
  554. }
  555.  
  556.  
  557. // We've got the head of the linked list for a 
  558. // sector.  Let's see if there are any objects
  559. // in it that are involved in collisions.
  560. //
  561. // Use the plain, old O(n^2) technique to compute
  562. // the collisions in this sector.  If the grid size
  563. // was appropriately chosen, n should be very small;
  564. // in many cases it will be 0 or 1, obviating
  565. // collision tests altogether.
  566.  
  567. static void _CalcCollisionsInSector(obj* objList)
  568. {
  569.     if (objList == NULL || objList->sector_link == NULL)
  570.         return;
  571.  
  572.     for (obj* o0 = objList; o0->sector_link; o0 = o0->sector_link)
  573.         for (obj* ox = o0->sector_link; ox; ox = ox->sector_link)
  574.             if (_IntersectQ(o0, ox))
  575.                 gCollisionArray[ o0 - gObjects ] =
  576.                 gCollisionArray[ ox - gObjects ] = 1;
  577.     
  578.                 // Note that at this point we know object o0
  579.                 // collided with object ox, so we could use that
  580.                 // information to, say, determine what kind of
  581.                 // explosion is appropriate.  Here, however, I
  582.                 // just toss the information away.
  583. }
  584. ======= end
  585.  
  586. Regards,
  587. Tom Moertel                          Interests:  Software Engineering,
  588.                                                  Symbolic Mathematics,
  589. MSA, CSG Technologies Division                   Algorithms,
  590. thor@telerama.lm.com                             Itchy-Scratchy Theory.
  591.  
  592.  
  593.