What kind of data structure to use for planetary populations?

Question

I am in the process of building out the prototype for my space strategy game, which is focused on empire building type gameplay.

One of the most important elements of the game are the various planets and the population groups on them. I have looked at Unity and Amazon Lumberyard before settling on Unreal Engine 4 to build the prototype on, but I am not sure what the best way to store information about the populations and planets are.

For now, planets are a class of object and store their characteristics as variables (no issue there). The problem arises with the populations, as each distinct group of population will have unique characteristics (i.e. species traits, faction alignment, education level) and game objects that they have possession of (weapons, armor, industrial machinery, trade goods).

What would be the most efficient way to tie the objects owned by the population to them, and to tie the population group to their planet of residence, such that I could compute things like:

For Faction X, on Planet Y, what is the product of their population's (Education x Industrial Machinery x Planet Mineral Rating)?

I considered implementing Population as a struct stored inside the Planet class, but that seemed problematic if I needed to move the population to a transport ship and then to a different planet, or add new groups of population during runtime.

Answer 1

Potentially, a planet may need to host more than one population. Your Planet class could use a linkedList of Population instances.

Let's assume you choose a Singly LinkedList

Relocating a population from a planet would simply involve:

• locating the population instance in the linked list (fast) [^1]
• removing the population instance from the source planet's linked list (fast)

• inserting the population to front of the destination planet's linked list (fast)

  [^1]: If a planet can have many populations, then the search will be fast if you use a map to track the location of a population instance in the linked list to avoid having to traverse the whole Linkedlist in the worst case. If a planet has a small maximum number of inhabitant populations, you probably won't need the map.

Alternatives: Planet class has member array (or vector) of pointers to its populations. In this case migration can be made to be fast (you're simply moving a pointer to a new array/vector), but if the array size is exceeded you'll have to bear the cost of the growing vector or expanding the array.

Further, if you don't mind having holes in the array or vector, removing a population from the planet can be done quickly. However, if holes are undesired then you'll bear the cost of shifting the array elements to cover the holes.

Other options probably exist, but these might be simple enough to meet your needs

Finally, if your populations know which planet/ship they reside on, then you can update this following a change i.e.

class Population{
    Location* currentLoc;
    void migrate(Location* destination){
        bool isMigrated=currentLoc->migrate(this,destination);
        if(isMigrated) currentLoc=destination;
}


class Planet{
    forward_list<Population> inhabitants;
    bool migrate(Population* populationA,Location* destination){
 //removes populationA from the linkedlist of inhabitant populations and    
 //inserts it into the linkedlist of the destination planet or ship
//returns true if migration successful
     }
}

Answer 2

I've got a 4X game of my own; it's written in C#, so forgive my ignorance of C++ terminology!

What I use is a Dictionary<Race, long> as a property of my colonies to store the population of those colonies. I don't know what you call a Dictionary in C++, but in Java it's called a Map, in Python it's called a dict, and in Perl it's called a hash.

The Race object stores all the characteristics of any particular race of aliens on the colonies, such as their mining aptitude and their reproduction rate.

If I want to put some population on a transport ship, then, I simply deduct it from the associated dictionary entry on the colony, and add it to the dictionary entry of the transport ship's population storage in its cargo (first checking that the dictionary entry exists and creating it if necessary).