Now you should have a playable game. At this point we are just adding some extra touches. In this assignment you are going to write a different implementation of your priority queue that is more efficient than the one you wrote before. You will also write some code so that you can see this benefit.
Design
Remember that the design should put in comments for every class and method that tell two things. It needs to specify how the classes fit into the game play as well as give some implication as to what the methods are going to do to make that a reality.
Code
The code for this assignment is nicely broken into two parts. The first is just for you to write the new priority queue. You can create a new class called HeapPriorityQueue or something like that which also implements the PriorityQueue interface, then to use it just have your GameSetup create an instance of that. That part may be difficult, but it is fairly straightforward as to what you need to do. The second part has you writing code that will create a large number of entities to put on the priority queue so that you can vary the type of queue and the number of entities from the command line and test how the two implementations scale.
Unfortunately, this improved efficiency won't be visible with a small number of entities so you will make a change that will allow you to see the speed impacts with a larger number of entities. This will involve several steps. First, I want you to create a new GameEntity class which you can call something like DummyEntity because it isn't really going to do anything. It has to have all the methods of GameEntity, but you will only be using it with your priority queue so you only have to put small implementations of getUpdateTime and update in it. In update all you should do it store the time that was passed in and in getUpdateTime you should return that number plus something. You won't be adding this to your screen or use it in the editor so the other functions aren't really needed. I would like the value that you add to the update time to be a random integer between 1 and 10. To get this you can use the code int val=1+(int)(10*Math.random());. There are better ways to do this, but that works well enough. You should probably decide the interval to use in the constructor. Don't do it in the getUpdateTime() method.
Once you have your DummyEntity you need a way to easily get your program to put different numbers of them on the priority queue and to tell your code to use either the heap or list based priority queue. I would like for you to do this with command line arguments (you will need to pass those into GameSetup.constructVariables). Your code should take two arguments. The first argument will be either "heap" or "list". This tells you what type of priority queue to use. The second argument will be the number of entities that should be added to the priority queue. Remember that command line arguments are passed into main as an array of strings so you will have to convert the string number into an int to do this (Integer.parseInt). Your program should then create the proper number of DummyEntites and add them all into the priority queue. Don't add them to the screen or anything else.
Given this, you could just run the program with different numbers of entities and see when the program seems to start running slower. However, that isn't quite ideal. We'd like some numbers that we can really compare. To get the numbers, I want you to add some code into your Player's update method that prints timing information. In particular, I want you to print out how much time passed between 100 calls to your player's update method. You can get a long that has the time with the call System.currentTimeMillis(). If you are updating every tick then time%100 tells you if another 100 ticks have passed. You just need to store the time value for one call and print out the difference between that and the time at the next call and remember the new value for the next time.
Once you have this all working, you should test out both of your priority queue implementations with different numbers of entities. Start at something like 10 and go up by factors of 2-10 then work your way up to see how much time it takes for the different numbers of entities. In addition to submitting the code I want you to turn in a printed plot of the timing results showing how each queue type slows down as the number of entities is increased. In theory when the number of entities is large, you will see the time increase quadratically for the list based priority queue and a n*log(n) for the heap based one.