Better streaming economy algorithm?

Question

Does anyone here have experience making games with streaming economies? I am working on a game and am looking for a better way to handle the economy. I feel like there must be a better algorithm than what I am using.

Background:

• ResourceBin objects contain resources
• Settlement objects contain ResourceBin objects
• Settlement objects have three queues of Building objects in arrays (Low, Medium, and High priorities)
• Building objects have a nextTick() method that accepts a ResourceBin and modifies it

Right now on every tick the Settlement class will loop through all of the Building arrays starting with High and working towards Low. On each Building object it calls the nextTick() method and passes its ResourceBin. After making sure that the transforms won't cause any Resource to become negative, the nextTick() method modifies the ResourceBin and exits. If any of its transformations would cause a Resource to become negative it just exits.

The issue with this is that the entire system depends heavily on the order in which the buildings are processed. I also can't have it proportionally affect the resource transformations if you are low on resources (like what is done in Total Annihilation).

Does anyone know how other games implement streaming economies? Is there a better way to do this?

Also let me know in the comments if a code example would be useful. I can pastebin one if need be.

Answer 1

This sounds a bit like a variation on the Knapsack Problem.

For this problem we have a set of items, each with a weight (resources needed) and a value (importance). Given a finite weight budget (resources held) we want to know what is the subset of items we can choose that fits into our budget while maximizing the subset's total value. Although NP-Hard, there are well-studied algorithms to solve this efficiently for modestly-sized problems.

The knapsack problem typically assumes that an item can only be taken or not - that there's no value in taking half of an item. If you can take a fraction of an item, and the value of the partial item is exactly proportional to the fraction of it that's taken, then there's a simple O(n log n) algorithm:

1. Sort the items in descending order of the ratio value / weight
2. Take complete items off the top of the list as long as you have enough budget remaining.
3. Once you can no longer take the next complete item in the list, take the largest fraction of it that you can.

However, it's not clear whether the value in your scenario follows this rule exactly. If the same buildings need resources every tick, then this would lead to high-bang-for-buck buildings taking the lion's share and starving everything else.

Maybe that's a good thing - maybe those buildings really are so important - it's hard to say without knowing more of your game design.

Think on this for a bit, and if you need a different way of divvying up resources, try editing your question to include a few example cases to sketch out the desired behaviour. (eg. "Given this many resources and the following buildings... the algorithm should give x resources to building A, y resources to building B...)