How to avoid cost comparison each and every frame?

Question

I'm toying around with a ticker(incremental game) for JavaScript.

The basic idea is that you have buttons that represent buildings, each building provides a certain amount of resource per 'tick'.

Each building can cost an arbitrary amount of resource types and amounts (a farm can cost wood, food and labor for example). The game is intended to have several dozens of buildings, units, technologies etc.

I would like to disable the buttons of buildings that you can't currently afford.

My concern: I prefer not to loop over every item and every cost within it to see if we have enough to build it every single tick (a tick is 50ms~).

Is there a 'smart' way that I missed that solves this issue without brute force?

EDIT : I decided to approve the answer that basically says "Just ignore the problem". The reasoning behind it is as follows :

1. Tests indicated that while the theoretical problem is interesting, it's of little consequence in a reality, the performance hit is extremely minimal.
2. This website is about solving problems, and as "sam hocevar" suggested, The answer needs to be as clear as possible(and the reason behind it).
3. While the answers are clever and very interesting to read as a theoretical background , they all address the "number of checks", while some answers reduce that number by some fraction, non actually mitigate the amount by any performance-altering number.
4. Following on 3, It seems that if you've come to a point where you need to implement any of the suggested, over-engineered, solutions to save performance, It seems that the gain from those solutions will be so minimal that performance will still be an issue even after implementation, making the entire game model not viable anyway.

TL;DR - If it doesn't work by ignoring the problem, it probably won't work with over-tweaking it either.

Answer 1

A boolean check is a very inexpensive thing. I wouldn't worry at all about performance costs. But there are two ways to go about this: Push or Pull. Either you 'pull' the data by checking every tick, or you 'push' the data by notifying buttons whenever a resource changes. For example, if your wood has increased, it fires an event to all buildings that need wood to be built and re-evaluates whether they can be built. The pull method is probably much easier and cleaner to implement, but the push will be less performance intensive.

Answer 2

Just recalculate your building-options at a bigger interval than your game-loop? You could just as well recalculate every 500, or even every 1000ms. The user won't care/notice if the building-options refresh with a slight delay.

All in all, this sounds a bit like premature optimization. I highly doubt you're going to have so many options to calculate that you'll be running into performance problems even if you update every 50ms.

Answer 3

Store your listeners in an ordered collection based upon their resource value - e.g. activate Factory Upgrade3 at 500 coins. Then every tick simply enable/disable any listener between the last tick's value and the current ticks value. By using an ordered collection you should be able to find this range of values very quickly.

1. Memory/CPU Efficient (only touch relevant items)
2. Real time - no delays to annoy players.

Of course, to echo earlier comments this sounds like a premature optimization at this point.

Answer 4

What is specific to javascript is that it has an overall high overhead when interpreted, and when (JIT) compiled, it will perform ok only with guessable types, simple loops, and using built-in functions, i think especially here about sort.
Sort your 'buildables' by each type of resource -this is done once, stored in separates arrays- (time vs space).
now each tick OR at a slower rate, but anyway every time the user spend resources, you just have to do a few for loops to tag the buildables with a boolean (using a boolean mask). for/while loops are so simple even javascript is fast with them.

Since i'm not sure i'm clear, here's some pseudo code :

// declared once (init)
var buildables = [ array of buildables with their resource requirements];
var resourceNames = [ 'water', 'gold', ... ...]
var sortedBuildables = [];
resourceNames.forEach(function(rn) {
            sortedBuildables.push(buildables.sort( 
                                         function(a,b) { return a[rn]-b[rn]; }  )); });
var resourceCount = resourceNames.length;
var allResourcesOkMask = (1<<resourceCount)-1;

Now when you need to check (every now and then OR when user spent resources)

var resourceValues = [ ... the amount of resource you have for each resource ...];
var lastResourceValues = new Array(resourceValues.length);

sortedBuildables.forEach(
   function(sorted, resourceIndex) {
      var resourceValue = resourceValues[resourceIndex];
      var lastResourceValue = lastResourceValues[resourceIndex]; 
      if (resourceValue != lastResourceValue) {
        var resourceName = resourceNames[resourceIndex];
        var resourceMask = 1 << resourceIndex;
        var buildable = null;
        var i=0;
        while((buildable = sorted[i]) && (buildable[resourceName]<resourceValue))                         
               {
                 buildable.mask |= resourceMask;
                 i++; 
               }
        while ((buildable = sorted[i])) 
               {
                 buildable.mask &= !resourceMask;
                 i++; 
               }
        }
      }
      lastResourceValues = resourceValues.slice(0);
);

now for each buildable, knowing if you can build it is the result of this test :

if (buildable.mask == allResourcesOkMask) --> button enabled.

While still brute force, this algorithm should work much faster in JS than even any smarter (tree/...) algorithm, given the js overhead : nothing is faster in js than doing plain for/while loops cruching integer numbers.

Answer 5

In most games, just run the loop every time. The cost of checking every bloody button you could ever press is way less than the cost of rendering a single button onscreen. GameAlchemist's answer should be more than enough for anything you actually want to do.

However, if you want better than brute force, you will want to take advantage of temporal consistency. On average, the set of enabled/disabled buttons doesn't change very much. All you have to do is prove that it hasn't changed much, and you're set.

Put all of your upgrades into an ordered structure for each resource, along with their prices. I'm going to talk to using an array, but any structure would do. One tiny change: invert all the prices. 500 minerals should become -500 minerals. Why? It could work either way, but the specific named algorithms tend to have specific meanings, and if I do this silly optimization, they correctly handle the case where I have exactly 500 minerals and want the build option to be enabled.

On the first iteration, we have to do some slower prep work. We take the number of minerals we have (let's say 249), and invert it to -249. Now if we treated this -249 as a lower_bound, and looked at the part of the ordered array that was equal or greater than this negative number, we'd have the list of everything that is enabled at first (its cost is closer to 0 than the amount of resources we have). Likewise, if we take an upper_bound operation, we'd look at the part of the ordered arraythat was less than this negative number, we'd have the list of everything that is disabled at first (its cost is further from 0 than the amount of resources we have).

The weirdness with negative numbers should be meaningful with an example where we have exactly 500 resources:

 -900   -500   -400   -200  -100    prices of each item (inverted)
        -500                        actual resources (inverted)
       |------------------------|   values for which -500 is a lower bound
|------|                            values for which -500 is an upper bound

You could absolutely word the logic differently and avoid all this silly negation. However, by doing it this way, you can use a lot of existing routines for dealing with bounds in sorted arrays. At least as far back as C++, the definitions of lower_bound and upper_bound have been defined such that lower_bound includes the value you're searching for, while upper_bound excludes it.

That was a lot of work, however, after frame 1, we can start using some temporal consistency to save time. We need to save off the current enabled/disabled state and resource count before we increment resources. Then we can compare the new resources against the old. If the new resources are higher, we are going to try to enable more states. If the new resources are lower, it means we spent resources last tick, and we need to disable more states.

So what states are going to change? It's easy really. Let's handle the increasing resources case first. If we negate the resources, like we have to to work with this structure, this means our resource number is going more negative. If we do a lower_bound based on this resource number, we'd get a part of the ordered array which should be enabled, just like before. However, this time, we also know that everything above the previous frame's lower_bound is already enabled, so we don't need to re-notify them. We only have to notify what's in between. Let's look at this on a number line. I'm intentionally making it jump a lot, from 300 resources to 500 so we can show the algorithm at work. Typically this jump would be a lot smaller.

 -900   -500   -400   -200  -100    prices of each item (inverted)
                   -300             old resources: 300 (inverted)
                     |---------|    values for which -300 is a lower bound
                       EN    EN     Enabled resources in previous frame
        -500                        new resources: 500 (inverted)
       |-----------------------|    values for which -500 is an lower bound
         EN      EN    EN    EN     Resources which need to be enabled
       Notify  Notify               Buttons that need notification because
                                    they were not enabled before, but are
                                    enabled now.

Likewise, if we're decreasing resources this frame, we need to disable buttons. Everything which was under the upper_bound of the previous frame were things that we know were properly disabled already. Everything under the upper_bound of this frame are things we need to disable. Thus, we should notify everything which is under the new upper_bound but stop when we see the old upper_bound because that was already handled. As an example, let's do the opposite of the previous example. Let's go from 500 resources to 300.

 -900   -500   -400   -200  -100    prices of each item (inverted)
        -500                        old resources: 500 (inverted)
|------|                            values for which -500 is an upper bound
         EN      EN    EN    EN     Enabled resources in previous frame
                   -300             new resources: 300 (inverted)
|------------------|                values for which -300 is a  upper bound
                       EN    EN     Resources which need to be enabled
       Notify  Notify               Buttons that need notification that
                                    they are no longer enabled

Phew. I told you its easier to just run the loop every time, but this will run faster than brute force. First off, because we're operating on an ordered array, lower_bound and upper_bound are O(log n), rather than the O(n) of the brute force approaches. Second, we're only sending notifications to the minimum number of buttons possible.

If you want to have more than one type of resources, keep an ordered array for each resource separately. Have each object which manages your buttons keep track of how many resources it needs which are unsatisfied by the current resources. On notification that you have enough of a resource, decrement this "unsatisfied" count by 1. on notification that you no longer have enough, increment this "unsatisfied" count by 1. Now you only really have to worry about the transition from 0 (fully satisfied, enabled) to 1+ (not satisfied, disabled).

Lots of work, but that'll keep your runtime costs as low as they can possibly go! If you have a few hundred buttons, and a few dozen resources for each, that may be the trick that takes you from "runs too slow to play" to "fun to play!" Maybe if you're going for hard-realtime 60Hz, this might help. The only way to tell is to profile. There's a lot more upkeep involved than with the brute force method, and depending on how well javascript optimizes, that might hurt more than it helps. However, this is scaleable, so when you want to have 100,000 buildings with 50 resources each, updating every millisecond, on the dot, this might be the ticket you need. It's also quite parallelizable in many steps, not that that matters much for javascript.

Answer 6

I assume these buttons need not be available at the exact same frame as the player gathers enough resources to buy them.

If that assumption is true, you can divide your list of buttons into four or five lists, and iterate over each of them on a different frame. For disabling, you should still check every frame, or do a second check when the user clicks the button, to prevent the user from taking advantage of that extra frame to click again.

Pseudocode:

buttons = [{costs:{lumber:10, gold:30}} ...]
buttonParts = divideArray(buttons, 4)
currentPart = 0

onUpdate():
    currentPart = currentPart+1 % buttonParts.length //every frame process next list, looping back to 0
    for btn in buttonParts[currentPart]:
        canEnable = true
        for {resource: costAmount} in btn.costs:
            if PLAYER_RESOURCES[resource] < costAmount:
                canEnable = false
                break //exit resources loop if any resource is not enough
        if canEnable:
            btn.enable()

Answer 7

checking each button before drawing it will be simplest and cheap enough for sane number of buttons.

if resources grow at constant speed (that is, unless new building is built, every tick player gains same amount resources), this algorithm might be worth considering is there is a lot of things to update:

have priority queue.
number your ticks.
disable all buttons.
for each button:
  has enough resources?
    mark as enabled.
  else:
    compute when there will be enough resources.
    put it in priority queue, with priority=tick number when to enable.
each frame:
  for each button in priority queue with priority==current tick number:
    mark as enabled.
    remove from queue.
when player clicks any enabled button:
  build building or whatever.
  disable all buttons.
  clear the queue.
  repopulate queue and enable buttons as in initialization.

there might be a way to do less work when player builds something (possibly with queue for every resource kind), but algorithm would be even more complicated.