Cornucopia of Consumption

Food

Let's talk about food! In Cultura, one of the big aspects is the economy: collecting resources, building goods and then consuming those goods. One of the biggest and earliest ones you have access to is food and its primary benefit is health. There are two big ratings, health and happiness. Health affects reproduction rate and also prevents sickness. Happiness affects emigration and rebellions. So how does food work?

A person consumes food once a day (rather than three meals a day plus snacks like real life). Based on their previous number of meals they get a health bonus. This is calculated at the end of each day. This goes toward reproduction if the person is a parent in a family with at least one male and one female parent. If not, then it does nothing other than add to the health score of a land region.

The health score of a land region is important because a low score below the required amount can result in sickness or worse an outbreak of plague. You don't want plague.

So what kind of food and what kind of bonus?

The health bonus is based on the total number of material types eaten. There are three item types available in Cultura during the paleolithic age: grain, fruit/vegetable and meat. Each item type has eight material types. Therefore the maximum paleolithic bonus is twenty four. The number of meals tracked is seven. Therefore a person must eat foods that contain more than three types of materials each to get the full bonus.

For example, a person eats wheat bread for six days and then eats a berry pie (blackberry and strawberry). This person ate wheat, blackberry and strawberry in the past seven days. The total bonus is three health.

How to Code

So how do we record the information in the code? Right now a Unit class contains no information about what the unit ate in the past number of days.

Let's start with this:

• Let d be the number of days to track
• Let m be the number of materials across all item types
• Let n be the population

Circular Array

Blogs aren't exactly the best place to display this kind of analysis but let's run with it for now. What if we tracked what a person ate with a circular array?

Complexity

• Add: O(d * m)
• Check Score: O(1)
• Memory: O(d * sizeof(Item))

During add we put in an Item into the circular array. We then have to run through all previous items to see if the item contains materials that do not exist and thus adds health. If we overwrite a previous entry, then we must do the same. We check the materials of the overwritten item, run through all items and see if it is still satisfied otherwise reduce the running count of health bonuses.

Memory usage is the size of the circular array with pointers to Item objects.

Hashmap of Counters

Alternatively we can use a simple hashmap of counters which allows us to use the readily available std::unordered_map where the key is the material id and the value is a counter. Each day the health score is checked the counter is decremented. Upon reaching zero the entry is removed.

• Add: O(m)
• Check Score: O(m)
• Memory: O(d * sizeof(int))

We can see that for add, every material that exists in the food being eaten will then reset the counter in the hashmap. During check score, we must run through the whole hash map and decrement counters and count. The memory usage is a hash map of counters which are integers.

Analysis

Add: Well we do the same amount of add as check score per unit; once a day in the game. If we set d = 7 and m = 24 then Circular Array has roughly 168 operations in worst case scenario while Hashmap has 24 operations in worst case scenario.

Check Score: For circular array it keeps a running count of health bonus so it has 1 operation in worst case scenario. For hashmap, it must go through the whole hash map and thus is 24 operations.

Memory: For circular array we have to keep the Item objects around because we have to keep track of what the person ate. An Item object is far larger than an integer. With d = 7, we have 7 Item objects for a circular array. With the Hashmap we have, with m = 24, 24 integers and then the cost of a hashmap. Assuming that an Item is larger than 3 integers, it's likely the circular array takes up more memory. An Item object is most definitely larger than 3 integers if you were wondering.

Given this analysis I think I will go with a hashmap. It is quicker to implement and I'm not seeing much gain from the circular array (except that it's cool).