CSS 443 - Machine Problem #3

 

2D Searching with Quadtree Structure.

 

Assigning Date: May 12, 2003

Program Due Time: 2:30pm, May 28, 2003

Design Document Due Time: 3:40 pm, May 28, 2003

 

 

Objectives:

 

In this programming assignment we will practice two dimensional range searching data structures and algorithms we learned in the lectures. In particular, we will experience 2D searching with non-uniform adaptive grid support.

 

Approach:

You are to download the mp3_assignment.zip program framework from our course website. We want to pay attention to the T443CollectionStruct class.

 

1.        Constructor: Each time user specifies a new number of targets for the system, the constructor of T443CollectionStruct will be called. At this point, you are responsible to initialize your internal structure and make sure there are no memory leaks.

 

2.       BuildInternalStructure: After the user changes MaxHeight or MaxNumInCell, the BuildInternalStructure function will be called. At this point you are responsible to rebuild your quadtree structure to reflect the user specified parameters. After you are done building a structure, you must compute the statistics associated with the new structure and inform the game system via filling in the TstructureStatistics struct.

 

3.       DeleteCollidingObject: When user fires a cannon, this function will be invoked. At this point, you are responsible to search all necessary T443Objects in the game, and calling the necessary T443Object::IntersectWithObject() functions to determine if there is an intersection. You must record how many external (leaf), internal nodes, and the total number of IntersectWithObject() you have called and return this information to the rest of the game system.

 

 

Please note because you are part of a large games’ system, you must work with in the constraint of T443CollectionStruct class. T2dBound.h and T433Object.h are defined else where in the system, you are allowed to use these classes but not change them. As for T443CollectionStruct class, you are allowed to alter the VoidPointers into any other data type that occupies 4 bytes, but you cannot change any other public or private members of this class. In the mp4_assignment, I used a simple link list as the acceleration structure. From the sluggish response of the system when there are more than a couple of hundred targets, we know this is a very bad solution. You will fix my solution with a quadtree structure.

 

Note: this is kind of work in progress, the library I provide you in GameLib only compiles/links under Debug mode at this point. For this assignment, we will have to test our system in Debug mode only.

What to hand-in:

 

1.        Please refer to Programming Assignments section in our class syllabus for details. You should create a zip file with your FirstLastNameMp3.zip, containing the source code to all your implementations and copy it to \\Hermes\Classes\CSS443\mp3 before the deadline time (of 2:30pm).  Please remember that adding new public methods is fine, although these functions will not be called from the rest of the game system. If you change any existing public methods, your source will not compile with the rest of the games system. Please do not hand in dsw/dsp files, or any cpp/h files in the mp3_assignment that you did not use.

2.        Hand-in a design document on the due date before 3:40pm.  In this document please include the followings:

a.        Block and functional diagram describing the design and classes of your system.

b.       Pseudo code and worst-case run-time analysis of your implementation of statistic computing/collection routine.

c.        Worst-case memory requirement (Big-O notation) to support your 2D search structure.

d.       Pseudo code for DeleteCollidingObject. Please clearly indicate how you compute the number of internal and external nodes, in your search; and how you compute the total number of IntersectWithObject() you called.

 

Credit Distribution:

 

1.        Implementation:

a.        Correct and Efficient Creation                                                            10%

b.       Correct and Efficient Searching                                                         20%

c.        Proper support for changing quadtree parameters                         10%

d.       Correct statistics computation                                                           20%

e.        Correct support for changing number of targets                                            10%

f.         Correct support of draw tree                                                              10%

 

** WARNING **: it is extremely difficult to score partial credit if you cannot demonstrate searching your structure for any given cannon. If your implementation works some of the times, in general, 10pts will be deducted for specific types of mistakes (e.g. incomplete search results, crashing after searching, etc.).

 

2.        Design Documentation:                                                                                      15%

 

3.        Proper programming style.                                                                                 5%

 

 

 

Extra Credit:

 

You can get up to 5pt extra credit if, when draw tree is on, you change the color of the cells you have searched for each cannon.

 

 

 

BE WARNED! If your program does not compile, or if your implementations do not generate correct results, you WILL NOT GET ANY CREDIT. If you cannot search your structure for any input, you WILL NOT get any of the 75%. If your algorithm is inefficient, you will score a total of less than 50%. You have 2 weeks to work on this assignment, please plan accordingly, and start early.

 

 

 

This programming assignment contributes 15% towards your final grade for this course.