In this assignment you will explore how using a tree or a list to organize objects interacting in a simple 2D game affect performance as measured by the number of frames rendered per second.
You should begin by modifying your game from assignment 1 by creating a enum type and object for determining what data structure, list or binary search tree, should be used for collision detection. When the collision detection is set to use a list your game should function as it does for assignment 1. When the collision detection is set to use a binary search tree the program should create binary search trees from the game objects that use coordinates as search keys. It is not sufficient to create two separate programs. Also, you should write the binary search tree class and not use the classes in the standard library.
The binary search tree collision algorithm should begin by creating a binary search tree from the list of objects. The coordinates of the object determine it's location in the tree. In the general case there should be four binary search trees, one for each of the four sides of the objects' axis aligned bounding box. Each tree should be searched for objects that can potentially produce a collision. All objects that can produce a collision should be marked. On the search of the last tree only objects that are being marked for the fourth time are considered to produce a collision.
Your game should also include something new that improves the game in addition to the above requirement. Be prepared to demo your game in class on Wednesday including an asymptotic analysis of and the actual frame rate when using the list-based and tree-based collision detection algorithms.
Hand In: Tar and email your code to your instructor with a subject of cpsc220 assign 2 before class on Wednesday, September 23rd.