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 DetectionLecture based on Real Time Collision Detection, Christer Ericson, Morgan Kauffman, 2005Game Design ExperienceProfessor Jim WhiteheadFebruary 9, 2009Creative Commons Attribution 3.0creativecommons.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 potentialto intersect, p•Narrow sweep►Perform p x p check of objectpairs that have potential tointersect•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 checkfor 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; // center int r; // radius }rcbool circle_intersect(circle a, circle b) { Point d; // d = b.c – a.c d.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 d int 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.y struct AABB { Point min; Point max;}// min.x<=x<=min.x+dx// min.y<=y<=min.y+dystruct AABB { Point min; int dx; // x width int dy; // y width} // | c.x-x | <= rx | c.y-y | <= rystruct AABB { Point c; int rx; // x radius int ry; // y radius}minmaxmincdxdyryrxstruct Point { int x; int y;}Can easily be extended to 3DAxis Aligned Bounding Box Intersection (min-max)•Two AABBs intersect only if they
View Full Document