# What kind of data structure to use for planetary populations?

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.

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
}
}

• How expensive in terms of processing is expanding an array to add a pointer? There will be wide variance in how many pops are on a given planet, ranging from one on a frontier colony to potentially hundreds on a trade hub. And if I left holes in the array, could those be filled by the first pointer to get added to the array afterwards, rather than expanding the array? I think this is how the "Add" function of arrays works in UE4/blueprint, but I'm not sure in this instance. – rideoutcolin Sep 26 '16 at 17:10
• Expansion will mean: - allocating memory for a brand new array which is larger than the original - copying each member of the original array into the new one (Although copying an address shouldn't be slow) - deallocating the memory for the original (maybe?) comparing this to the aforementioned linkedlist disconnection and connections which are essentially a series of assignments of addresses to pointers, suggests it will be much slower (haven't tested it yet). Yes, you can work with the holes, perhaps place nullptrs in the holes, this will indicate a free slot or one not be accessed – N.Vegeta Sep 27 '16 at 21:56
• You can time the array expansion process on your system. Based on how often you expect the expansion to happen, determine whether the overhead is tolerable. A vector will handle the expansion. – N.Vegeta Sep 27 '16 at 22:00
• Hmm, my gut instinct is that expanding/resizing the arrays will happen pretty frequently. I won't know for sure until I've got the prototype built, though. I may try it both ways while the code is still relatively simple. I'll update the original question with results after I get it working. – rideoutcolin Sep 28 '16 at 22:09
• When in doubt in C++ one should always use std::vector for data storage. It usually is faster than linked lists. If performance is a problem, measure and see if it is faster with lists in your use case. Surprisingly the performance of std::vector is often better suited than lists, even when modifying it often. – Skalli Sep 30 '16 at 15:54

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).

• I believe the equivalent data structure is also called a map in C++. – rideoutcolin Sep 26 '16 at 23:17