Tower Defense Requirements (Subject to change)
The first thing to do is to google for “tower defense” and play the game online for free. You can read up more about this game here: http://en.wikipedia.org/wiki/Tower_defense As always, if the program crashes at any point in the game play, the project grade will be zero. If you do not turn in your project by the deadline, the grade is also zero.

REQUIREMENTS

a) When the program first runs, a welcome window is shown. The welcome window should show texts containing the name of your game and your name. Furthermore, it prints a message telling the user to press the spacebar to begin the game. If the user closes the program, the program halts.

b) You have maximum freedom on designing the game. There are however several elements of the game that must be implemented.

c) When the game begins, in a square area of the game window, you see one path going from left to right. There is a “balloon entrance” on the left end of the line – balloons enter the game from. On the right end of the line, there is a “balloon exit” – balloon exit the game at this point.

d) The game play area should be a sufficient large square. It should at least be large enough to show >1000 balloons at the same time. This will ensure that you have thought through carefully on how to optimize the performance of your game.

e) There is a counter in the game window that tells you how many balloons have entered the “balloon exit”. (For instance you have have a “status bar” below the game play window for that).

f) The player can place towers in the game play area.

g) Each tower has a range, say a radius 100. (You can have towers of different ranges.) If a balloon is within range, the tower will show with a line from the tower to the balloon.

h) Each tower selects a balloon within range and fires at it. You can choose how the tower selects the balloon to destroy. For instance it can choose a random balloon in range, the closest one in range, the tower can account for the speed of the balloon, etc.

i) When a bullet (or whatever weapon) from the tower collides with the balloon, the balloon and the bullet both disappear.

j) Besides the above path pattern, you can have different ones, including cases where there are multiple entrances and exits.

k) As the game progresses, new paths are forms. The “grow” out of exist paths. For instance here's one that's growing:

k) You can either have paths growing randomly or according to some fixed pattern. I leave that to you.

l) When the growing path touches the edge of the game play area, it comes a balloon exit:

m) When the growing path touches a point on the path, it stops growing:

n) Balloons can travel on all paths, including new ones or growing ones.
o) You can have as many different type of balloons as you like, as many towers as you like, etc.

The important thing is to allow the game to run with a large number of balloons, a large entrance exit number of towers, a large number of path segments. (For instance you can have a mode where the player does not die.)

The elements that are important are:

i) Your game must allow the creation of any graph. You must use an efficient data structure to represent the paths.

ii) You must use some form of quadtree data structure for collision detection. To show that a quadtree is used, your program must allow the display of the quadtree (say when a button is pressed). In the status bar/window of your game, display relevant statistics of your quadtree such as number of nodes, height of the tree.

iii) Your balloons are smart: they can pick the safest paths (i.e., ones that will avoid towers as much as possible) to arrive at exits. The only really important thing is to use the data structures and algorithms in the above context. Therefore the only really important thing is that I want to see a graph for the paths (or whatever else you want to do such as a scene graph …) or some form of space subdivision tree for collision detection.
You are obviously not allowed to use existing code (from the web or books). You can read up  in general about graphs and trees (of course!) and reading pseudocode is perfectly OK.

iv) Games are soft real-time systems fighting for resources. Read up on priority queues and use it in your game. In your status bar/window, display statistics on the queue including average time usage for different type of objects.