Introduction to Collision Detection Lecture based on Real Time Collision Detection, Christer Ericson, Morgan Kauffman, 2005AnnouncementsTechnical Design DocumentTechnical Design Document (cont’d)Collision DetectionKey to collision detection: scalingNaïve Collision Detection: n x n checkingBroad vs Narrow SweepBroad sweep approachesReducing Cost of Checking Two Objects for CollisionCommon Bounding VolumesCircle Bounding BoxAxis-Aligned Bounding Boxes (AABBs)Axis Aligned Bounding Box Intersection (min-max)Axis Aligned Bounding Box Intersection (min-width)AABB Intersection (center-radius)HomeworkIntroduction to Collision Detection Lecture based on Real Time Collision Detection, Christer Ericson, Morgan Kauffman, 2005Game Design ExperienceProfessor Jim WhiteheadFebruary 9, 2009Creative Commons Attribution 3.0 creativecommons.org/licenses/by/3.0Announcements• Homework #1, Revisited (Improved Design)► Due today► May turn it in to the box by my door by the end of the day► Also make sure you do electronic submission► See details on web site• Midterm exam► Aiming for return of exams on Wednesday► Will post answer key after class todayTechnical Design Document• Create a UML structure diagram for your game► Map out your design on paper, before writing code► Allows you to think about design decisions early► Due this Friday, February 13• In one or more UML diagrams, describe all of the classes and interfaces you will create for your project► For each class and interface, give• Class properties, methods, and variables► Show inheritance and containment relationshipsTechnical Design Document (cont’d)• Items that should be in your design ► input handling ► representation of game levels, if present ► player class ► enemy classes, including a container holding active enemies ► game object classes, including a container to hold them ► collision detection ► classes for drawing player, enemies, other game objects ► classes for handling audio ► menu system classes • Make sure TDD is consistent with game design► Are you missing anything?• Strongly recommend using a UML modeling tool► StarUML is free, has good set of features► http://staruml.sourceforge.net/en/ (see link on Tools page)Demonstration of use of StarUMLCollision Detection• Collision detection► Determining if two objects intersect (true or false)► Example: did bullet hit opponent?• Collision resolution (collision determination)► Determining when two objects came into contact• At what point during their motion did they intersect?• Example: Two balls needing to bounce off each other► Determining where two objects intersect• Which points on the objects touch during a collision?• Example: Pong: where ball hits paddle is important• Complexity of answering these questions increases in order given► If < when < whereKey to collision detection: scaling• Key constraint: only 16.667ms per clock tick► Limited time to perform collision detection• Object shapes in 2D games can be quite complex► Naïve: check two objects pixel-by-pixel for collisions• Many objects can potentially collide► Naïve: check every object pair for collisions• Drawback of naïve approach► Takes too long► Doesn’t scale to large numbers of objects• Approaches for scaling► Reduce # of collision pairs► Reduce cost of each collision checkChu Chu Rocket, DreamcastNaïve Collision Detection: n x n checking• Assume► n objects in game► All n objects can potentially intersect with each other• Conceptually easiest approach► Check each object against every other object for intersections► Leads to (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) checks► Done poorly, can be exactly n2 checks ► Example: 420 objects leads to 87,990 checks, per clock tickDemonstration of n x n collision checkingBroad vs Narrow Sweep• With many small objects in large playfield► Each object only has the potential to collide with nearby objects• Broad sweep► Perform a quick pass over n objects to determine which pairs have potential to intersect, p• Narrow sweep► Perform p x p check of object pairs that have potential to intersect• Dramatically reduces # of checksMushihimesamaBroad sweep approaches• Grid► Divide playfield into a grid of squares► Place each object in its square► Only need to check contents of square against itself and neighboring squares► See http://www.harveycartel.org/metanet/tutorials/tutorialB.html for example• Space partitioning tree► Subdivide space as needed into rectangles► Use tree data structure to point to objects in space► Only need to check tree leaves► Quadtree, Binary Space Partition (BSP) tree• Application-specific► 2D-shooter: only need to check for collision against ship► Do quick y check for broad sweepPoint Quadtree (Wikipedia)Reducing Cost of Checking Two Objects for Collision• General approach is to substitute a bounding volume for a more complex object• Desirable properties of bounding volumes:► Inexpensive intersection tests► Tight fitting► Inexpensive to compute► Easy to rotate and transform► Low memory useMegaman X1 (Capcom). White boxes represent bounding volumes.Common Bounding Volumes• Most introductory game programming texts call AABBs simply “bounding boxes”Circle/Sphere Axis-Aligned Bounding Box (AABB)Oriented Bounding Box (OBB)Convex HullBetter bounds, better cullingFaster test, less memoryCircle Bounding Box• Simple storage, easy intersection test• Rotationally invariantstruct Point {int x;int y;}struct circle {Point c; // centerint r; // radius }rcbool circle_intersect(circle a, circle b) {Point d; // d = b.c – a.cd.x = a.c.x – b.c.x;d.y= a.c.y–b.c.y;int dist2 = d.x*d.x + d.y*d.y; // d dot dint radiusSum = a.r + b.r;if (dist2 <= radiusSum * radiusSum) {return true;} else {return false;}}Compare Euclidean distance between circle centers against sum of circle radii.Axis-Aligned Bounding Boxes (AABBs)• Three common representations► Min-max► Min-widths► Center-radius// min.x<=x<=max.x// min.y<=y<=max.ystruct AABB {Point min;Point max;}// min.x<=x<=min.x+dx// min.y<=y<=min.y+dystruct AABB {Point min;int dx; // x widthint dy; // y width} // | c.x-x | <= rx | c.y-y | <= rystruct AABB {Point c;int rx; // x radiusint ry; // y radius}minmaxmincdxdyryrxstruct Point {int x;int y;}Can easily be extended to 3DAxis Aligned Bounding Box Intersection
View Full Document