Context:
I’m modeling repeated button presses for an incremental game. There will be buttons in-game set to press repeatedly. These buttons have:
- variable presses/sec speeds, or rates.
- variable “speed limits” (max presses/sec allowed).
- variable cooldown timers when the speed limits are exceeded.
- variable presses/press multipliers that amplify each press (not the same as multiplying the presses/sec value directly)
In practice, the game calculates in discrete time chunks (ticking). I need to determine exactly when during a tick the speed limit is first broken, so I can apply cooldowns precisely. (speed limit broken -> overheat and reset tally -> cooldown, rinse and repeat).
Some impl details:
To keep presses independent from the size of the tick calculation window, Presses are “aligned” to the next timestamp divisible by (1000/pressesPerSec), i.e. milliseconds per press.
For example, 4 presses/sec would align presses to timestamps % 250 = 0, e.g. … 9750, 10000, 10250, 10500, …
I am storing the repeating presses as press objects (pressObjs), containing the timestamp pressing starts, the timestamp pressing stops, and the presses/sec rate.
I intend for the presses/sec, cooldown timer, etc. to be taken to the extremes; think 10^1000 and 10^-1000. (Thanks break_infinity.js)
The problem:
I’ve reduced this to: Find the smallest timestamp x where f(x) = sum of ceiling functions > threshold
Each group of presses, defined by a pressObj, is effectively a piecewise function with ceiling operations. When multiple press objects overlap, I need to find when their sum first exceeds the speed limit.
Example:
A button is upgraded from 10 presses/sec to 14 presses/sec. The button has a presses/press multiplier = 2 and a speed limit = 25 presses/sec.
Press objects (pressObjs) are created every 210 ms starting at the timestamp 2500. There are a total of 12 press objects; The first six perform 10 presses/sec, and the second six perform 14 presses/sec.
There will be some “uneven behavior” to the running presses/sec tally as it transitions. It will cross the 25 presses/sec speed limit multiple times.
This Desmos visualization shows the limit is first broken around the timestamp 4285.71429. Likely approximating ≈ 30,000 / 7.
(In this example, because we see the limit is broken on the ninth press object, the last three press objects would not be created during the run of the program, unless cooldown time was tiny.)
My thought process:
Each press object effectively creates a piecewise function based on four breakpoints where its effect on the running presses/sec tally changes:
- repeated pressing starts — incrementing the running tally,
- repeated presses stop, or expire (happen over a second ago) at the same rate they are performed — plateauing the running tally,
- presses have stopped and the last presses begin expiring — decrementing the running tally,
- the last press has expired — tally is back to 0.
The pseudocode for constructing the piecewise function from a repeated press object:
tsStartPressing = pressObj.startPressingTimestamp
tsStopPressing = pressObj.stopPressingTimestamp
ppMs = pressObj.pressesPerSecond / 1000
mspp = 1 / ppMs
pressMul = pressObj.pressMul
// The four breakpoints
tsStart
tsPlateau = min( tsStop, tsStart + 1000 )
tsStartDecrease = max( tsStop, tsStart + 1000 )
tsEnd = tsStop + 1000
// The first performed press is aligned to the next timestamp divisible by milliseconds/press
tsAlignedFirstPress = ceil(tsStartPressing / mspp) * mspp
plateauTally = ceil((tsPlateau - tsAlignedFirstPress) * ppMs) * pressMul
// Breakpoints 1-2: Increment -- presses 'ramp up'
F_inc(t) = ceil((t - tsAlignedFirstPress) * ppMs) * pressMul
// Breakpoints 2-3: Plateau -- presses stop, or expire at the same rate they are pressed
F_plateau(t) = plateauTally
// Breakpoints 3-4: Decrement -- presses 'ramp down' as no more occur and they expire
F_dec(t) = plateauTally - ceil((t - (tsStartDecrease - tsStartPressing) - tsAlignedFirstPress) * ppMs) * pressMul
// Piecewise:
F(t) = {
F_inc(t) | tsStart <= t < tsPlateau
F_plateau(t) | tsPlateau <= t < tsStartDecrease
F_dec(t) | tsStartDecrease <= t < tsEnd
0 | else
}
My current approach:
After processing overlapping piecewise functions’ segments — summing plateau segments as constants, and cancelling out increment and decrement ceiling functions with equal presses/sec — I am left with ceiling functions with unequal presses/sec.
My current algorithm splits every ceiling function into many flat segments, which creates insanely many breakpoints when presses/sec values are large (e.g., 10^10 presses/sec). This becomes computationally expensive.
As a sanity check I put the above 10 p/s -> 14 p/s example into Mathematica to use its fancy Minimize, NMinimize, and ArgMin functions. (I can post the full Mathematica code if desired.) The results it produced were rather inconsistent. The best was 4293, not even close to 30,000 / 7 ≈ 4285.71429.
I know optimizing nonlinear or non-convex problems is very hard analytically. There are several posts on math.stackexchange.com regarding sums with floor()s and ceil()s, but none regarding the specific case of finding the smallest x that causes f(x) > threshold.
Question:
How can I efficiently find the first timestamp where the sum of the ceiling functions exceeds a threshold?
Alternatively, is there a better approach for modeling this game mechanic that avoids the ceiling function complexity entirely?
The core issue is that ceiling functions create discontinuous jumps, and their sum can exceed the threshold at any of these discontinuity points. I need an efficient way to check these critical points without evaluating every possible breakpoint.