Common 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)TreesTree OperationsPoint QuadtreeC# Node RepresentationAdding object to treeFinding, removing object in treeDesign PatternsPublish/Subscribe ExamplePublish/SubscribePublish/Subscribe AdvantagesPublish/Subscribe DisadvantagesPublish/Subscribe ImplementationsDelegatesDefining and Using DelegatesObserver PatternProblem: Changing AI BehaviorStrategy PatternDesign PrinciplesHomeworkComputer Science – Game DesignUC Santa CruzCommon 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 memoryComputer Science – Game DesignUC Santa CruzCircle 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.Computer Science – Game DesignUC Santa CruzAxis-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}minmaxmincdxdyryrxCan easily be extended to 3DComputer Science – Game DesignUC Santa CruzAxis Aligned Bounding Box Intersection (min-max)•Two AABBs intersect only if they overlap on both axesa.max.x<b.min.xa.min.x>b.max.xa.min.x=b.min.xa.max.y<b.min.ya.min.y>b.max.ya.min.y=b.min.ybool IntersectAABB(AABB a, AABB b) {{ if (a.max.x < b.min.x || a.min.x < b.max.x) return false; if (a.max.y < b.min.y || a.min.y < b.max.y) return false; return true;}Computer Science – Game DesignUC Santa CruzAxis Aligned Bounding Box Intersection (min-width)•Two AABBs intersect only if they overlap on both axes-(a.min.x-b.min.x)>a.dx(a.min.x-b.min.x)>b.dxa.min.x=b.min.x-(a.min.y-b.min.y)>a.dy(a.min.y-b.min.y)>b.dya.min.y=b.min.ybool IntersectAABB(AABB a, AABB b) {{ int t; t=a.min.x-b.min.x; if (t > b.dx || -t > a.dx) return false; t=a.min.y-b.min.y; if (t > b.dy || -t > a.dy) return false; return true;}// Note: requires more operations than// min-max case (2 more subtractions, 2 more negations)Computer Science – Game DesignUC Santa CruzAABB Intersection (center-radius)•Two AABBs intersect only if they overlap on both axesb.c.x-a.c.x >a.rx+b.rya.c.x-b.c.x >a.rx+b.rxa.c.x=b.c.xb.c.y-a.c.y > a.ry+b.rya.c.y-b.c.y >a.ry+b.rya.c.y=b.c.ybool IntersectAABB(AABB a, AABB b) {{ if (Abs(a.c.x – b.c.x) > (a.r.dx + b.r.dx)) return false; if (Abs(a.c.y – b.c.y) > (a.r.dy + b.r.dy)) ) return false; return true;}// Note: Abs() typically single instruction on modern processorsComputer Science – Game DesignUC Santa CruzTrees•A tree is a data structure–Places contents into nodes–Each node has•Contents•Pointers to 0 or more other levels–Children are represented as referencesroota bcd45 755624 51A tree with 5 nodes (root, a, b, c, d).Root node has contents 56.Node a has contents 45, and two children, c and d.Node b has contents 75, and no children.Node c has contents 24, and no children.Node d has contents 51, and no children.// A simple tree node classClass Node { List<Node> children; // List of references to Nodes int contents;}Computer Science – Game DesignUC Santa CruzTree Operations•Adding a child–Create new node•n = new Node();–Add it to list of children of parent•parentNode.children.Add(n);•Removing a child–Find and remove child node from list of children•parentNode.children.Remove(childToRemove);•(childToRemove is reference to Node of child to be deleted)Computer Science – Game DesignUC Santa CruzPoint Quadtree•A tree where each node has four children–Each level represents subdividing space into 4 quadrants–Each node holds information about one quadrant–A deeper tree indicates more subdivisionsMX Quadtree Demohttp://donar.umiacs.umd.edu/quadtree/points/mxquad.htmlDemo both points and rectangles0 12 3root01 230 12 31.01.11.2 1.3root1 2301.0 1.1 1.2 1.3Computer Science – Game DesignUC Santa CruzC# Node Representation•quads is an array with four elements–Each element is a reference to a Node•Quad[0] – upper left, etc.–A recursive data structure•Nodes hold pointers to Nodes•Min[] is an array with four elements–Each element is upper left point of quadrant•Max[] holds lower right point of each quadrant•Level indicates how many levels down in the tree–Useful for bounding the depth of the tree class Node { Point min[4]; Point max[4]; int level; Node Quad[4]; // holds 4 quadrants List<IGameObject> objectList; // list of game objects in a Node}Quad[0] Quad[1]Quad[2] Quad[3]Computer Science – Game DesignUC Santa CruzAdding object to treeInsert(Node n, IGameObject g)•Iterate through all 4 quadrants of current node (n)–If at maximum depth of the tree•Add IGameObject to objectList and return–If AABB (bounding box) of IGameObject lies fully within a quadrant•Create child node for that quadrant, if necessary•Then call insert on that node (recursion)–Otherwise, AABB does not lie in just one quadrant•Add to contents list at this level•First call is Insert(root, g)–That is, start at root node for insertionsComputer Science – Game DesignUC Santa CruzFinding, removing object in treeFind(Node n, IGameObject g)•Iterate through all 4 quadrants of current node (n)–Check if AABB (bounding box) of IGameObject spans multiple quadrants•Yes: IGameObject is in this node. Return node.–At maximum level of tree?•Yes: IGameObject is at this level–If AABB (bounding box) of IGameObject lies fully within a quadrant•Call find on that node (recursion)•Removing object from tree–Found_node = Find(root,