Space Partitioning for Broad Sweep Collision Detection Part 1 - GridsTechnical Design DocumentTechnical Design Document (cont’d)Broad vs Narrow SweepBroad sweep approachesSpace Partition GridGrid Cell Size IssuesGrid Collision TestObject UpdateSpace Partitioning for Broad Sweep Collision Detection Part 1 - GridsGame Design ExperienceProfessor Jim WhiteheadFebruary 11, 2009Creative Commons Attribution 3.0 creativecommons.org/licenses/by/3.0Technical 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 StarUMLBroad 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)Space Partition Grid• Subdivide space into a grid► Each cell in the grid holds a list of the objects contained in the cell► Objects that overlap cells are placed in multiple cells► One approach:class Grid{// The collision grid// Grid is a 2D array, where each element holds a list of IGameObjectList<IGameObject>[,] grid;int grid_cols; // # of grid columnsint grid_rows; // # of grid rowsint cell_x; // x width of each grid cellint cell_y; // y width of each grid cell…This is a relatively memory intensive approach.Grid Cell Size Issues• Grid too fine► Cell size similar to object size► Many objects will overlap cells► Slows update and collision checks• Grid too large► Few overlaps (good)► Larger number of n x n checks within a cell• Grid too coarse with respect to object complexity► Complexity of object geometry makes pairwise comparison too hard► Solution: make grid size smaller, objects broken up into smaller pieces• Grid too large and too fine► Can happen if object sizes vary widelyGrid too coarse (complexity)Grid too fineGrid Collision Test• Within each cell► Compare each object in cell with every other object in cell► Pairwise comparison, but only within cells// Simple cell compare – does twice as many compares as necessaryvoid cell_collide(int row, int col) {foreach (IGameObject g in grid[row,col]) {foreach (IGameObject h in grid[row,col]) {if (g == h ) continue;if (object_test(g,h) == true) {g.collided = true;h.collided = true;}}}}Object Update• When an object moves, it may change cell location• Need to compute cell(s) holding object at new location► May be more than one due to overlap• If new cell, add object to cell► This is O(1), since only adding to end of list• If leaving existing cell, need to remove from list► Naïve approach: O(# elems in cell), since need to traverse lists to find object to remove• A problem, since fast moving objects may mean large fraction of objects need to update each tick. Approaches O(n2)► Better approach: have each game object maintain pointer back to its location in list in each cell• But, requires you to write your own linked list
View Full Document
Unlocking...