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 an 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 possibly see this benefit. This added code will give you a very large "map". If you are using the screen editor, it will write a function that takes the vector that gets read in and starts copying elements in it so that you have many duplicates of the same screens it will also connect those screens with links. If you aren't using the screen editor, but generating your own screens instead, then you will have to write code that can generate the screens and connect them with links. It will also need to put moving entities on them since that is the primary objective of this program. We want you to have a LOT of moving entities that are getting added to the priority queue at many different times so you can hopefully see efficiency differences.
Design
The design for this assignment will include UML class diagrams for the classes that you will write. It should also include text descriptions of your implementation of the GUIs that you create. It will also include all of the classes that you wrote for the earlier assignments.
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. For the priority queue this doesn't have to be very extensive. For the generation is should be much more so. The idea here is that you will write a function that you can pass the Vector of screens to and an integer for how many screens to add. What it produces should be a connected set of all the screens you created plus the original ones. I would recommend that you put them all in that Vector. So for your design you need to think of how you are going add links and make sure that everything is connected. Remember that adding links probably doesn't make sense for all of your blocks.
Again I recommend that this be submitted by putting the files generated in Together in a new directory that will be visible on the web and send me a link.
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, then to use it just have your GaemSetup 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 make the "map" of your game extremely large and makes it so you will have a lot of entities that really test the new priority queue implementation.
We will talk about heaps in class before the assignment is due. You will be implementing the same PriorityQueue interface but with a different data structure backing it up. This part of the code should be straightforward once you have seen the heap. The reason for doing this is that it is more efficient than a sorted linked list.
Unfortunately, this improved efficiency won't be visible with a small number of entities, or if your entities update every tick which is what many of you are doing. As some of you have seen, you almost have to do that for some intereactions which is unfortunate, but just for "fun" you will put some code in this time that makes it so that doesn't happen in some situations.
In your GameSetup constructor you will add a call to a function that takes the Vector of screens you have and an integer for how many to add. If you aren't using the screen editor then that vector might start off blank and you will need extra code that generates screens. The call to this should go between where you read in screens and where you run through all of them adding entities to the queue. If you are loading screens, that function will pick a screen from the vector and make a copy of it that gets added to the vector. You might have to add a copy constructor to your screen implementation in order to do this. The function should also set some links, somewhat randomly, that go to that screen from one or more of the other screens in the vector and back. That way you get a graph of screens that are connected, even if the connections aren't logical. Once you have added the proper number of entities the function returns and the rest of the setup goes along as normal.
For speed testing I'd also like you to do something else. Most moving entities in your game probably update every tick. When you can see them this is probably required. However, when they are off the screen it isn't really needed. For that reason, and to help test the heap based priority queue, I want you to add into the update method of your moving entities, code so that they will look through all the entities in their screen and see if the player is with them. If the player is not with them, they should make it so that their next update time is randomly selected to be a value between 1 tick in advance and many ticks from now. How large that needs to be depends on your game a bit, but since this is just for testing, I think it would be good if the number you use is something like 100. This might cause bugs when a player enters a new screen, but I don't want you to worry too much about that for this assignment. You can change it back later.
Once you have this all working, you should test out both of your priority queue implementations with different numbers of screens (and therefore different numbers of entities). Try to get numbers of entities between 1,000 and 1,000,000. The latter might be difficult for RAM reasons, but you can see how far you are able to go. Obviously, if you put more moving entities on each screen fewer screens will be required. Test both priority queues with the different numbers of entities and the window small to see if you can tell if there is any difference in performance between the two. Let me know when you can see that speed difference.