0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 1) Figure out the total amount of resources needed by every building. 2a) If there's enough resources, give each building what it needs. 2b) If there aren't enough resources, figure out what proportion of the needed resources are available, then give every building that proportion of what it needs. \$\endgroup\$ – immibis Sep 26 '16 at 23:55
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This may well work. This looks like the greedy algorithm yes? I can't believe I'd never run into the knapsack problem coding before. It looks like it is relatively common. From Wikipedia: "A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem." \$\endgroup\$ – Zell Faze Sep 27 '16 at 1:54
  • \$\begingroup\$ I made an implementation of this in PHP for anyone who is interested. I know this question is tagged C++11, and I will be implementing in that, but I know PHP better, so I wanted to sketch it out in that first. pastebin.com/NBDqNnhQ \$\endgroup\$ – Zell Faze Sep 27 '16 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.