0

What algorithm should I use, to simulate a continual stream of N increments each second — not writing a loop, but instead by timed-interval events, no more than M events per second?

I am implementing a incremental game, and the rate of increment for some resource Scrog has a widely-varying rate of increase. The system I'm using has an event timer, and that's the mechanism I want to use to generate the resource over time.

Design constraints

The inputs to this algorithm are: the effective rate of Scrog increase (e.g. “14 per second”, “578 per second”), and the lower bound of the period for each timer (e.g. “no smaller than 10 per second”, “no smaller than 100 per second”).

The outputs of this algorithm are: a small set of tuples (timer-interval, scrog-quantity), often just one tuple and typically no more than a handful, that when taken together will effectively produce the specified rate of Scrog increase per second.

  • I want to simulate anything from 1 increment every few seconds, all the way to trillions per second.

  • Incrementing the Scrog resource is to be done by constant integer amounts. I want to pre-calculate the amounts and not deal with fractions of the resource.

  • The events should be fired by repeating-interval timers.

  • The generated timer intervals should be as large as can be, to run the function as infrequently as we can. Given a specified rate of increase, I don't want a polling function that does useless “is it time yet?” checks; that was known before hand, this algorithm needs to set up timers to avoid polling.

  • The generated timer intervals should be larger than a specified minimum bound (“M per second”), while small enough to in aggregate simulate the steady rate “N per second”.

  • No state can be kept in a loop; instead, the algorithm must pre-compute a collection of timers that will each fire an “increment Scrog by n” event, periodically. The period of each timer, and the integer amount of Scrog produced by each timer, are then constant.

  • The events should fire steadily, simulating a continual flow; but not indefinitely often, so that the event handler is not overloaded.

  • It's acceptable if the algorithm only approximates the specified rate, within the tolerance of M-per-second.

So I am looking for a generic algorithm, that will simulate a continual flow of Scrog at whatever rate (N per second) is specified, by setting up repeating events at a small number of fixed intervals, each interval no more frequent than M per second.

Example: up to 10 events per second

If I limit the actual rate of events to no faster than 0.1 seconds (10 times per second), that would mean:

  • When the rate is “1 Scrog per 5 seconds”, the algorithm may produce the set { (5.0 seconds, 1 Scrog) }.
  • When the rate is “1 Scrog per second”, the algorithm may produce the set { (1.0 seconds, 1 Scrog) }.
  • When the rate is “7 Scrog per second”, the algorithm may produce the set { (0.143 seconds, 1 Scrog) }.
  • When the rate is “10 Scrog per second”, the algorithm may produce the set { (0.1 seconds, 1 Scrog) }.
  • When the rate is “500 Scrog per second”, the algorithm may produce the set { (0.1 seconds, 50 Scrog) }.

But I'm confused about how the algorithm should handle rates faster than 10-per-second, slower than hundreds-per-second.

  • When the rate is “14 Scrog per second”, the algorithm may produce the set { (0.1 seconds, 1 Scrog), (0.25 seconds, 1 Scrog) }, because events triggered with those intervals will result in 14 Scrog per second.

A simple arithmetic problem?

Stripped of the context of events, timers, etc. this boils down to me trying to take some numbers-with units, and produce other numbers-with-units.

So this is apparently a fairly simple (?) problem: Design a general algorithm which, given these inputs, and the above constraints, will produce those outputs.

But my abstract arithmetic isn't powerful enough. How should the algorithm be written so that it produces all these results, given only the constraints and the current effective Scrog rate?

  • Why not always fire the event at 0.1 seconds? Call it a tick. Increasing Scrogs at 0.2 per tick will produce nothing at first but in 5 seconds that gives you 1 whole Scrog. – candied_orange Jan 7 '18 at 2:43
  • @CandiedOrange, I have updated the question with the explicit constraint that the resource can only exist in integer amounts. – bignose Jan 7 '18 at 3:30
  • Oh fine. Then every tick add 20 Scrog pennies and when you have 100 Scrog pennies exchange them for a whole Scrog. Nothing but whole numbers all around. – candied_orange Jan 7 '18 at 3:32
  • The algorithm you're looking for is called a "digital differential analyser", and is the same algorithm that is used for drawing pixel-centred lines. An example implementation is Bresenham's line drawing algorithm. Consider how you'd draw the line of a graph where horizontal pixels represent your timer ticks, and vertical pixels represent your produced resources, and the correspondance with line drawing algorithms should become very clear. – Jules Jan 7 '18 at 16:42
  • It's really unclear what you're asking for, especially given your comments on doubleYou's answer, which I think correctly suggests that you should know what to award at any given time, so long as you know how much time has elapsed. You don't need an algorithm, per se, you just need a function and a way of giving that function a time period. – svidgen Jan 7 '18 at 22:32
2

Do not rely on loop frequency.

You have a Scrog accumulation rate associated with each Player. So, just put an awardScrogs() method and lastTimeSrogsAwarded property and invoke as-needed. No matter how often awardScrogs() is called, it should check lastScrogsAwarded and determine at invocation time how many that Player needs.

You can further control how Scrogs are awarded be adding minumumAwardAmount and/or minimumAwardPeriod. Your awardScrogs() will do nothing if the minimums aren't met. And, if you want to ensure Scrogs are awarded in particular groups sizes, add awardGroupSize for awardScrogs() to always round down to the nearest multiple of.

It could look something like this:

function awardScrogs() {
  var time = new Date.getTime();

  var period = time - this.lastTimeScrogsAwarded;
  if (period < minimumAwardPeriod) return;

  var potentialAward = period * scrogsAwardRate;
  var awardGroupCount = Math.floor(potentialAward / awardGroupSize);
  var actualAward = awardGroupCount * awardGroupSize;
  if (actualAward < minimumAwardAmount) return;

  this.scrogs += actualAward;
  this.save();
}

... or whatever.

You invoke it whenever you need to -- and no more often.

Call awardScrogs() either during object construction or immediately before you read the value from .scrogs and only then. If there's nothing to award, it very does nothing very quickly and without consequence. If there is a pending award, it's awarded immediately, all-at-once, just-in-time, and you're sure to have the most precise and up-to-date value every time.

For the purposes of maintaining an index or leaderboard, update those on a lengthier interval -- somewhere between 5 minutes and 24 hours. Keep that data separate to avoid having leaderboard traffic lock your Player rows. And, when you refresh it, call awardScrogs() on every Player.

  • Thanks. One reason I want to algorithmically determine the period, is to avoid running a very-frequent update check when that could be avoided. If the rate is known in advance to be less frequent than the fastest update check, then why waste cycles on a check that's more frequent than the current rate? That's the reason I want to set up timed events only at the intervals currently needed, and adjust those timers (with the same algorithm) only when the declared rate changes. – bignose Jan 8 '18 at 2:48
  • @bignose Sure. And the best way to do that is to make the update only when the value is needed... Let me add one clarification to my answer... – svidgen Jan 8 '18 at 3:38
  • What I mean is that I want to algorithmically determine, based on the declared rate of increase, how often to call a function — to set up a timer (or a handful of them) with a period as large as can be, because that can be determined ahead of time (no need to call a periodic function just to return early). This answer doesn't address that. – bignose Jan 8 '18 at 3:48
  • @bignose To be honest, part of the problem here is that your problem is really elusive. To me, the core problem you're describing seems super-trivial. I can't quite see what you're not seeing ... But, in essence, with this type of problem, I'm suggesting that you shouldn't be using an interval at all -- except maybe for the purposes of refreshing leaderboards or something. Other than that, each Player's scrogCount (or whatever) should be refreshed on-demand, just-in-time. And, you should be confident that the refresh will do nothing non-consequentially if there's nothing to do. – svidgen Jan 8 '18 at 3:52
  • @sviggen: Yes, if you think the problem as I've described it is trivial you probably understand it :-) It may even boil down to a simple matter of finding the right integer arithmetic to take the inputs (declared frequencies) and produce the desired outputs (tuples of (time-interval, scrog-amount)). – bignose Jan 8 '18 at 3:59
0

Special cases aside, you'll either have to deal with fractional Scrogs or fractional seconds - or both.

Fixed Period, Varying Intervals

From a purely conceptual perspective, it might make more sense to just reduce the ScrogMiningPeriod that it takes to create one more Scrog. Wait for that interval and increment the ScrogCount. In practice, this is not a good idea for several reasons.

  • You probably won't have a multi-trillion Hertz computer, so you cannot achieve that rate. Of course, your OS will already put a much more restrictive limit on this rate.
  • Even if you could increment the value in periods of ns or µs, it's a complete waste of computing resources.

Because you cannot make the mining interval small enough to keep a fixed increment, it makes sense to keep the mining period fixed, and deal with varying increments. This way, you only have to deal with one varying factor.

Aside: You should set the period just small enough for your users to perceive updates as continuous. A few times per second should be more than enough.

Fractional Increments

Because you may want to increment Scrogs by less than one per interval, you will have to deal with fractional Scrogs. Pick a sufficiently fine-grained Scrog-unit (e.g. 1/1000) and make all your calculations in this unit.

As your counter needs to deal with trillions of new scrogs per second, you'll need a big counter-variable anyways. So a few more orders of magnitude should not make such a big difference.

Rounding Errors

If you need high accuracy over the long run, you can make sure that the mining rate produces an exact interval amount after each period. If that's not an option, you can define a mining table based on the rate, i.e. obtain a slightly different amount every xth interval.

For example, if you want to add 1 Scrog every second, and you've chosen your mining interval to be 1/3 second, and you're calculating in 1/1000 Scrogs, then your table could be [333, 333, 334].

Note that this is more theoretical, because the timers won't be that exact anyways.

Integral Scrog Alternative

There's an obvious alternative (actually two - see below) that I've overlook previously. It doesn't make things easier, though, but perhaps you'd prefer this approach.

You want to mine a scrog after a certain time interval has passed (call it P). So conceptually, you'd like to do sleep(P); scrogCount++; in a loop.

Because that's not possible with a trillion scrogs per second, we want to make the mining period longer and offset this by mining more than 1 scrog at a time. So we get a mining rate R=S/P where S is the number of scrogs mined per interval.

The updated algorithm would be sleep(P); scrogCount += S.

Slow Mining If P is larger than some threshold value - call it 0.25ms - then we can simply set S=1 and use that algorithm.

Fast Mining Otherwise, we need to multiply S and P by some factor until P reaches or surpases the threshold.

The problem is that we want to keep S integral and make P an integral ms-value. If we have a really odd mining period, this may cause P to become relatively large, so that it seems we're not mining anything at all for a while and then get a gigantic batch.

This can be handled by calculating values for S and P that almost produce the desired rate R, and then adding the missing scrogs on every xth iteration, as described above.

Direct Calculation

Depending on the rest of your app, the easiest way to do this may be to just calculate the current number of scrogs at any given moment. Instead of simulating scrog creation in the background, you could just calculate the current scrogCount based on the mining rate, the previous scrog count and the time passed since then.

This has the advantage of being the most accurate (since timers won't necessarily fire when you expect them to).

  • This seems to be re-stating some of the constraints; I don't see how this provides an answer though. Can you update this to describe the algorithm you are proposing? – bignose Jan 7 '18 at 17:43
  • I've mainly tried to explain why it would just make the most sense to deal with fractional scrogs. I've tried to structure the argument a bit better. Additionally, I've included two alternative approaches which you might deem more useful. – doubleYou Jan 7 '18 at 19:48

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.