# 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 "tick loop", where resources update say once per second, generally increasing.

But many games can implement an "offline mode" 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 "offline mode" 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 ("offline mode").

In a typical idle game (think "cookie clicker"), 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 "general purpose factory" that produces both general purpose factories, and cookies?

Second question: is this easy if we allow simple "autobuy"? 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!

• note: will post pt2 after this one resolves, about similar idle games based around resource conversion (ex use 2 wood to make 1 fence) instead of just generating things out of nothing – Zachary Vance Nov 1 '20 at 21:57
• For the autobuy scenario the number of factories will grow exponentially. This makes explicit simulation "efficient" since the size of the output is comparable to the number of simulation steps. – Tom van der Zanden Nov 3 '20 at 21:55
• Tom, this is a valid point. I'm happy to use the RAM model here where add, mult, print are all constant time for integers, which removes that problem and makes analysis easier, at the cost of some realism. – Zachary Vance Nov 4 '20 at 0:48

## 2 Answers

Yes. It can be solved efficiently. You can denote the state of the system at any point by a vector $$x \in \mathbb{N}^n$$, where $$n$$ is the number of resources and $$x_i$$ counts how many items of the $$i$$th resource you have.

Your system gives you linear equations that relate $$x'$$, the state after one tick, to $$x$$, the state before the tick. For instance, if $$x_1,x_2,x_3$$ denote the number of cookies, cookie stoves, and cookie stove factories, respectively, then we have $$x'_1 = x_1 + 5 x_2$$, $$x'_2 = x_2 + x_3$$, $$x'_3 = x_3$$. Collect all of these linear equations into a linear system $$x' = Mx$$, so the matrix $$M$$ represents the generation process.

Now the state after $$t$$ ticks of offline operation is given by $$x' = M^t x$$. So, you can use efficient algorithms for matrix exponentiation (e.g., repeated squaring). They will let you compute $$M^t$$ in $$O(n^3 \log t)$$ time, after which you can compute $$x'$$ from $$x$$ in $$O(n^2)$$ time. (One can get further speedups: it is possible to compute $$M^t$$ in $$O(n^3 + n \log t)$$ time using an eigenvector decomposition.) This is very efficient and will let you handle trillions of ticks with no problem. It also gives you an exact answer.

• Just adding a comment for any future readers that matrix exponentiation can be done faster than $O(n^3 log t)$ time, for example in $O(n^3 + n log t)$ time by finding eigenvectors. – Zachary Vance Nov 4 '20 at 0:18
• @ZacharyVance, oh, good point, thank you! – D.W. Nov 4 '20 at 1:24

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

• This is outstanding - but beware that you have a discrete system, and differential equations are a continuous approximation to a discrete system, so this might give you only an approximate solution, rather than an exact one. – D.W. Nov 3 '20 at 22:09
• Noted, I've left an edit with your advice – Zackatoo Nov 3 '20 at 23:05