Complexity of simulating idle games (pt1) An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical implementation is in the form of a &quot;tick loop&quot;, where resources update say once per second, generally increasing.
But many games can implement an &quot;offline mode&quot; where instead you can exactly calculate any number of ticks in one step. For example if you were producing 1000 cookies/second, and you come back after 1 hour, you've produced 3.6 million cookies exactly--no need to simulate all 3600 ticks. Then the player can reduce the update rate on screen, or come back to the game in 5 hours without running a program continuously. (Aside: many real games offer an &quot;offline mode&quot; which does NOT exactly match what would happen playing the game for the same length of time, but here I'm asking about exact simulation).
I am trying to figure out for which idle games an it's possible to efficiently compute many ticks in one step (&quot;offline mode&quot;).
In a typical idle game (think &quot;cookie clicker&quot;), you have a bunch of resource generators, and each one generates some resources each tick. For example, maybe you have a cookie stove, which produces 5 cookies/tick. And you could also have a generator factory, which produces 1 cookie stove/tick.

For each resource, it produces some fixed list of resources each tick. Let's say we just have a list of what each resource produces each tick.

A resource costs something to buy. This is actually irrelevant for the simulation--buying is only a player action, and can't be done automatically.

A problem input will be a set of starting resources, and a number of ticks to simulate. Output should be the resources after that number of ticks.

If there are no cycles, an offline mode is definitely possible. The number of each resource is a linear (if it is not produced by anything else), quadratic (if it is produced by a linear resource), etc. So it's always a polynomial, which is easy to calculate.


My first question: is this still easy if we allow cycles, ex a &quot;general purpose factory&quot; that produces both general purpose factories, and cookies?
Second question: is this easy if we allow simple &quot;autobuy&quot;? Ex. convert 1000 cookies into a cookie factory, and buy as many as possible, on each game tick.
If it's easy, show how to do it. If it's hard, prove it!
As you have said in your question, non-cyclical resource production is easy to simulate, but let's describe the simple case before seeing how it impacts the answer. For our cookie-bakery scenario, this is the setup:
$$
t_i=0,\ t_f=100 \\
C_i=567,\ C_{cpt}=0,\ C_{bpt}=0 \\
B_i=10,\ B_{cpt}=2,\ B_{bpt}=0
$$
The above describes the initial state of our game, we currently have 567 cookies and 10 bakeries. It also describes the production statistics, how much each resource produces per tick. For us, cookies produce nothing and bakeries produce 2 cookies per tick. How do we find how many cookies there are when the time is up?
$$
C(t_f)=\int_{t_i}^{t_f}\frac{dC}{dt}dt+C_i=2567
$$
This function will calculate how many cookies have been produced by time $t_f$. In our simple case, $\frac{dC}{dt}$ is easy to calculate:
$$
\frac{dC}{dt}=B_{cpt}B(t)=20
$$
Since there are no new bakeries being generated, the number of bakeries is constant $B(t)=B_i$.

Question 1
The trouble begins when the resource production contains cycles. That is to say, $\frac{dC}{dt}$ is dependent on $C(t)$ itself. We have entered the realm of differental equations. For an example, here is a tweaked setup where cookies can also asexually reproduce every tick:
$$
t_i=0,\ t_f=100 \\
C_i=567,\ C_{cpt}=1,\ C_{bpt}=0 \\
B_i=10,\ B_{cpt}=2,\ B_{bpt}=0
$$
Now the rate of change for cookies looks like:
$$
\frac{dC}{dt}=B_{cpt}B(t)+C_{cpt}C(t)\text{ where }C(0)=C_i
$$
For our case, this is a linear first-order differential equation, our integrating factor is:
$$
\mu(t)=e^{-C_{cpt}t}
$$
Plug it into the differential equation form:
$$
C(t)=\frac{B_{cpt}B(t)}{-C_{cpt}}+ce^{C_{cpt}t}
$$
Find our constant $c$ by checking the initial condition:
$$
C(0)=\frac{B_{cpt}B(0)}{-C_{cpt}}+ce^0=C_i \\
c=C_i+\frac{B_{cpt}B_i}{C_{cpt}}
$$
Plug it back into our original equation:
$$
C(t_f)=\frac{B_{cpt}B(t_f)}{-C_{cpt}}+\bigg(C_i+\frac{B_{cpt}B_i}{C_{cpt}}\bigg)e^{C_{cpt}t_f} \approx 1.58\times 10^{46}
$$
The asexual reproduction of cookies produces substantially more cookies than just bakeries, but keep in mind the cookie population is essentially doubling every time plus new cookies are being produced by bakeries.
This method can be extended for larger cycles instead of just self cyclical, but it requires higher order differential equations.
Note: Since we are just evaluating an exponential function, it is extraordinarily efficient, $O(1)$. However, this solution adapts the mathematics of population growth estimates to fit this discrete system and will only produce an approximation. Depending on how many timesteps are required to simulate, it may be preferable to spend more time computing an exact result.

Question 2
Automatic buying is quite a bit more difficult to achieve because the functions showing resource counts are no longer smooth and continuous.

This graph shows the cookie production assuming starting with one bakery &amp; zero cookies and buying another bakery every thousand cookies. The period of the function decreases with time because more and more bakeries are added to produce cookies. An estimation could be created by fitting a function to the period, but I do not know of a method to exactly count the number of bakeries and cookies without checking each timestep.