For one of the final projects in my Algorithm and Data Structure class (CSCI 1933 at the University of Minnesota - Twin Cities campus), my friend and I came up with data structures that we learned to conquer all of the worlds in the universe from a game simulation that was implemented by the professor. Essentially, you and your opponent are competing to see who can gain the most population, as well as other planets. You can win by sending additional populations (by bus shuttles) to attack all the worlds that are owned by your enemies.
Video by August Eggers
For our strategy, we conquer the neutral planets (planets that are not yet owned by anyone) as soon as the game starts so that our population grows quickly. If an enemy planet is trying to take control of our specific planet, we would send shuttles to that specific planet immediately. If our current planet’s population overcomes the enemy planet’s population, our shuttles are ready to be sent to take control of the enemy planet. If our planet is under attack, it is flagged as seekHelpPlanets to make sure our other planets send enough people to take back that specific planet.
Our data structure uses
1. Queue: We retrieve and sort the neighboring edges by distance. The smallest distance goes first in the queue, while the largest distance gets to be last, so we can travel and gain more population quickly. A queue is appropriate for this because we can add (enqueue) and remove (dequeue) things easily without worrying about indexes. We also use the queue as a priority to make sure neutral planets can be taken control of rapidly.
2. HashMap: We use the seekHelpPlanets Hashmap to see if our planets need any help. In the getAllNeighborsShortestDistance method, we use a HashMap to store the neighboring planets and the distance away from the source planet. We use Hashmap because it is easy to access and we can use the Hashmap iterator to use both the value and the key to easily look planets up.
3. List: We set myEnemies to the IVisiblePlanet list to store all of our enemy neighbors on each of our planets. We use a list because we don’t need to sort the elements in them; we just need to iterate them through so that our planets know who and where to attack. In addition, we use powerfulPlanets to store all the planets that get a lot of population size from our surrounding planets and iterate through them to attack the enemy’s planet.
Looking back, I have learned the usefulness of using different types of data structures. While learning more techniques every day, I wish I could have done something with Graphs, such as using Dijkstra’s Algorithm (shortest paths) to beat the enemies’ team. I have also learned that working with another person helps me learn new ideas as well as helps me develop my skills when working in a real future company.