Food optimization algorithm (urban survival)

Hello,

Let's I have a set of characters in an urban survival game, each have a consumption rate per day based on age, weight, size and activity profile, express in Calorie.

Let's say I have a set of food, express as Calorie, but having component of nutrient such has carb, protein and fat, express as normalized unit, and serving ratio that express the minimal size of a portion relative to that unit. And each food as a cost per serving, which can change base on brand or packing size.

Given a balance of nutrient, such as 50%carb, 20% protein, 30% fat, per character. What's the best algorithm I could use, that select food according to their minimal serving, fill the character need in Calorie, and achieve the best balance of nutrient for the lowest price?

 

There're a few components to this. Obviously your own architecture takes preference over how I might imagine it, but let's say you have a class something like

Code (CSharp):

1. class FoodPortion
2. {
3.     public float carbCalories;
4.     public float proteinCalories;
5.     public float fatPerc;
6.     public float cost;
7. }

And as above, you've got a few needs for the character. Let's say they look like this:

Code (CSharp):

1. const float CALORIES_REQD_PER_DAY = 2000;
2. const float CARB_PERC = 0.5f;
3. const float PROTEIN_PERC = 0.2f;
4. const float FAT_PERC = 0.3f;
5.  
6. float myCurrentDailyCarbCount;
7. float myCurrentDailyProteinCount;
8. float myCurrentDailyFatCount;

We'll also assume in this instance that the EatFood function looks something like this:

Code (CSharp):

1. void EatFood(FoodPortion food)
2. {
3.     myCurrentDailyCarbCount += food.carbCalories;
4.     myCurrentDailyProteinCount += food.proteinCalories;
5.     myCurrentDailyFatCount += food.fatPerc;
6. }

What you want is to be able to evaluate based on different factors, and weight according to those. Stuff like the nutritional value to the character, the cost, as well other factors like the distance to the food (we don't want the character walking all the way across town because something was marginally cheaper than something right next to them. Or do we? That's where the weighting comes in).

For the nutrition value, the characters will want to keep track of what they need so that we can compare the benefits of a food portion.

Code (CSharp):

1. // 0 - 1 values
2. float myCarbNeedPerc;
3. float myProteinNeedPerc;
4. float myFatNeedPerc;
5.  
6. void EvaluateMyFoodNeeds()
7. {
8.     //Will be zero if we're full on carbs, or 1 if we have none
9.     myCarbNeedPerc = CALORIES_REQD_PER_DAY * CARB_PERC - myCurrentDailyCarbCount;
10.     myProteinNeedPerc = CALORIES_REQD_PER_DAY * PROTEIN_PERC - myCurrentDailyProteinCount;
11.     myFatNeedPerc = CALORIES_REQD_PER_DAY * FAT_PERC - myCurrentDailyFatCount;
12. }

Then, we can take a hypothetical food portion and output a float based on our requirements.

Code (CSharp):

1. float EvaluateFoodBasedOnNeed(FoodPortion food)
2. {
3.     EvaluateMyFoodNeeds();
4.     //Will return a smaller number if we don't need this or a larger number if we do
5.     float nutritionDesire = (food.carbCalories * myCarbNeedPerc + food.proteinCalories * myProteinNeedPerc + food.fatPerc * myFatNeedPerc);
6.     return nutritionDesire;
7. }

We can evaluate based on other factors too, like the aforementioned cost

Code (CSharp):

1. float EvaluateFoodBasedOnCost(FoodPortion food)
2. {
3.     //Will return a smaller number for a higher cost or a larger number for a lower cost
4.     float costDesire = (1f / Mathf.Min(food.cost, 1f));
5.     return costDesire;
6. }

We'll also want some weights for these evaluations based on how you want the behaviour to manifest itself. Do characters prefer cheaper, or more nutritious food? Will they travel for miles to eat a snack if it means they'll gain a better nutritional benefit? These can be easily tweaked, or even dynamic based on the characters resources. Ultimately you'll be adding up all these factors and simply choosing the best one for the character.

Code (CSharp):

1. void ChooseFood(FoodPortion[] allAvailableFoods)
2. {
3.     int bestFoodIndex = -1;
4.     float bestFoodValue = 0f;
5.     for (int i = 0; i < allAvailableFoods.Length; i++)
6.     {
7.         float foodValue =
8.             EvaluateFoodBasedOnCost(allAvailableFoods[i]) * COST_WEIGHTING
9.             + EvaluateFoodBasedOnNeed(allAvailableFoods[i]) * NUTRITION_WEIGHTING
10.             + EvaluateFoodBasedOnDistance(allAvailableFoods[i]) * DISTANCE_WEIGHTING;
11.         if (foodValue > bestFoodValue)
12.         {
13.             bestFoodValue = foodValue;
14.             bestFoodIndex = i;
15.         }
16.     }
17.     FoodPortion chosenFood = allAvailableFoods[bestFoodIndex];
18. }

TL;DR: It depends on the needs of your game. Usually you'll want some weighting to whatever factors you need that can be easily tweaked to affect behaviour. The choice algorithm just takes all these weights and decides which one is best overall.

 

Oh well, thanks for the long explanation, I got that part down, but you pointed to a weakness in my explanation.

Basically I want to find, not the best current food, but the "meal course" composed of a set of food portion such as it satisfies all the constrain. I'm not even sure how to actually express that lol.

Character aren't autonomous, they are handled by a manager, and it automatically create a diet for the day for the character. Cost are actual money too and distance or access are not factored (it's filtered by the set of food available), so it's more of a management survival game.

 

Ah right, so if I understand correctly, you want the manager to ensure everyone gets a full balance of nutrients and calories, but from multiple sources of food portions throughout the day, and optimized for cost?

Is food infinite, or is it a finite resource in the world per day?

 

The pool doesn't matter now, but I had somebody telling me it's call the Stigler diet problem, which is exactly what I want but the problem is that I only found math notation and not pure code, especially not c# lol

 

Is this for a game or are you trying to optimize your personal food intake?

I've read a lot of articles on nutrition, both pseudo-science and science based, and it's a really complicated topic. If you want to make a game around it, I think you need to greatly simplify and focus on the kinds of decisions the player will be making and evaluate if those will be fun. I have a hunch you are headed towards an overly complex simulation that will be very hard to understand and make good decisions on for players.

 

Edit: I added a Score function to the Food class which determines the value of the food based on 3 things:
How closely the macronutrients align with the desired ratios
How many calories the food has
How much the food costs
e.g. milk might satisfy all the macronutrient ratios, but not provide enough calories for the cost
The downfall of this method vs the random method is that you wont get any variety - some combination of the two methods might be a bit more interesting.
This could be made better by scoring the food based on the remaining fat/pro/carb calories rather than the total - might add this later on for fun

So I got a bit carried away and wrote a little console application to test out my theory which goes like this:

Take an array of food objects which have a name, protein per gram, fat per gram and carb per gram.
1. get all the foods from this array which meet the dietary requirements using LINQ
2. pick the food with the best score and add it to the meal plan
3. keep a count of the calories, fat, protein and carb added
4. repeat 1-3 until no foods meet the requirement

I ended up with this (I only have 5 foods defined):



Notice that it added a lot of lettuce at the end because the fat calories were fully allocated.
Also notice that the calories aren't quite the at the max which I defined as 1800 - this is because 1 macro has reached its limit and there are no foods in the array with zero protein/fat.
My code says to stop adding food if it will exceed the limits for a certain macronutrient - you could modify this to allow some leeway.
Given a larger variety of foods, I think this would be a pretty decent solution for a game.

Please note I just made up the nutrition values for the food.

Anyway, here's the code if you want to take a look. Let me know if you have any questions.

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Text;
5. using System.Threading.Tasks;
6.  
7. /// <summary>
8. /// Defines a food and it's nutrients
9. /// </summary>
10. class Food
11. {
12.     public Food(string name, float grams, float carbsPerGram, float proteinPerGram, float fatPerGram, decimal price)
13.     {
14.         Name = name;
15.         CarbsPerGram = carbsPerGram;
16.         ProteinPerGram = proteinPerGram;
17.         FatPerGram = fatPerGram;
18.         Grams = grams;
19.         Price = price;
20.     }
21.     public string Name { get; private set; }
22.     public float CarbsPerGram { get; private set; }
23.     public float ProteinPerGram { get; private set; }
24.     public float FatPerGram { get; private set; }
25.     public decimal Price { get; private set; }
26.  
27.     public float Grams { get; private set; }
28.  
29.     public float GetCalories()
30.     {
31.         return CarbCalories() + ProteinCalories() + FatCalories();
32.     }
33.  
34.     public float CarbCalories() { return CarbsPerGram * 4 * Grams; }
35.     public float ProteinCalories() { return ProteinPerGram * 4 * Grams; }
36.     public float FatCalories() { return FatPerGram * 9 * Grams; }
37.  
38.     public float Score(float carbPercent, float fatPercent, float proteinPercent)
39.     {
40.         //calculate the food balance by checking the difference between the actual macro calories and the wanted percentage
41.         float nutrientBalance = GetCalories();
42.         nutrientBalance -= Math.Abs(CarbCalories() - GetCalories() * carbPercent);
43.         nutrientBalance -= Math.Abs(FatCalories() - GetCalories() * fatPercent);
44.         nutrientBalance -= Math.Abs(ProteinCalories() - GetCalories() * proteinPercent);
45.         return GetCalories() + nutrientBalance / (float)Price;
46.     }
47.  
48. }
49. class Program
50. {
51.  
52.     static void Main(string[] args)
53.     {
54.         //All available food
55.         var foods = new Food[]
56.         {
57.                 new Food("Apple", 100, 0.1f, 0.05f, 0f, price: 1M),
58.                 new Food("Porkchop", 150, 0.01f, 0.2f, 0.15f, price: 4M),
59.                 new Food("Egg", 50, 0f, 0.05f, 0.2f, price: 0.5M),
60.                 new Food("Lettuce", 80, 0.01f, 0f, 0f, price: 2M),
61.                 new Food("Bread", 30, 0.33f, 0.05f, 0.05f, price: .2M)
62.         };
63.  
64.         float proteinRatio = 0.3f;
65.         float fatRatio = 0.2f;
66.         float carbRatio = 0.5f;
67.  
68.         //Variables to keep track of the allocated macronutrients
69.         float maxCalories = 1800;
70.         float calorieCount = 0;
71.         float maxProtein = maxCalories * proteinRatio; //0.5f = carb ratio
72.         float proteinCount = 0;
73.         float maxCarb = maxCalories * carbRatio; //0.5f = carb ratio
74.         float carbCount = 0;
75.         float maxFat = maxCalories * fatRatio; //0.5f = carb ratio
76.         float fatCount = 0;
77.  
78.         var mealPlan = new List<Food>();
79.  
80.         var rand = new Random();
81.         //Breaks when no more food can be allocated
82.         while (true)
83.         {
84.             //calculate the remaining macronutrients
85.             float remainingCalories = maxCalories - calorieCount;
86.             float remainingProtein = maxProtein - proteinCount;
87.             float remainingCarb = maxCarb - carbCount;
88.             float remainingFat = maxFat - fatCount;
89.  
90.             //Select foods that fit with our current diet
91.             var allowedFood = from food in foods
92.                               where food.GetCalories() <= remainingCalories
93.                                     && food.CarbCalories() <= remainingCarb
94.                                     && food.ProteinCalories() <= remainingProtein
95.                                     && food.FatCalories() <= remainingFat
96.                               select food;
97.  
98.             if (allowedFood.Any())
99.             {
100.                 //var chosenFood = allowedFood.ToArray()[rand.Next(allowedFood.Count())];
101.                 var chosenFood = allowedFood.OrderByDescending(x => x.Score(carbRatio, fatRatio, proteinRatio)).FirstOrDefault();
102.                 mealPlan.Add(chosenFood);
103.                 calorieCount += chosenFood.GetCalories();
104.                 proteinCount += chosenFood.ProteinCalories();
105.                 carbCount += chosenFood.CarbCalories();
106.                 fatCount += chosenFood.FatCalories();
107.             }
108.             else
109.             {
110.                 //No food matches requirements so DONT EAT ANYMORE
111.                 break;
112.             }
113.  
114.         }
115.  
116.         Console.WriteLine($"Meal Plan ***************");
117.         Console.WriteLine($"Cost: ${mealPlan.Sum(x => x.Price)}");
118.         Console.WriteLine($"Calories: {calorieCount}");
119.         Console.WriteLine($"Calories from protein: {proteinCount}");
120.         Console.WriteLine($"Calories from carbs: {carbCount}");
121.         Console.WriteLine($"Calories from fat: {fatCount}\n");
122.         Console.WriteLine("Foods:\n");
123.         foreach (var food in mealPlan)
124.         {
125.             Console.WriteLine($"Food: {food.Name} \t Calories: {food.GetCalories()} \t Price {food.Price} \t Score: {food.Score(carbRatio, fatRatio, proteinRatio)}");
126.         }
127.  
128.  
129.     }
130. }
131.