A ride that takes 10^20k years to complete in Roller Coaster Tycoon 2 [video]
youtube.com
youtube.com
The GitHub commit message says it was just to mess up MarcelVos, the videomaker
For solving mazes, here's the most popular algorithm:
Touch the wall or hedge with the hand nearest to it, left or right. Keep that same hand touching the wall and keep walking. This may take you on a horribly long route, but it will eventually get you out.
[...]
Rather than doing complete randomness when choosing directions, I think it would be actually better to assign an strategy for each player (once they enter the attraction), setting their default direction to "always clockwise" (as it was before this PR) or "always counter-clockwise".
https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...
A simple mechanism that would also make it more interesting would be for wall following to flip handedness at random intervals. That is, the guest would start off by following the wall with his left hand, and then after some random number of steps, start following with his right hand.
If we’re talking about mazes where the entrance and exit are both on the perimeter wall, those points must be connected by that wall and the algorithm is guaranteed to be successful.
It's a good algorithm within some very specific constraints.
The trick used in the github issue cited by the other reply is a similar idea, but the change in y axis value is applied to the exit rather than throughout the maze, via a tunnel from the center.
FWIW, I taught my kids to use "right-following" when exploring caves in Minecraft, and it works pretty even though its randomly generated "mazes" (caves) can and do loop in on each other etc.
According to their quick test, this will definitely result in guests solving mazes a lot faster.
1. guests wandering around randomly - every part of the maze is regularly visited if the maze is busy
2. guests being not hopeless at actually solving mazes
If the guest makes progress opaquely by sometimes cheating, I'm really not going to notice as a player.
On the other hand, some of the other solutions presented here (like using the left hand rule) would make the mazes a lot less interesting to watch.
> remember places they had been previously and bias against those places
Which is something a real maze solving algorithm could do. The linked solution might do that, but mainly it works by cheating (effectively, implementing "gravity" pulling guests towards squares that it knows are closer to the end). That might be just fine for the purposes of making a video game, but it doesn't seem like the sort of approach you were talking about.
I loved Transport Tycoon and have clocked up nearly as many hours on OpenTTD as I had on the original DOS game. I did also have RCT but sadly never had the time to play it as much when it was new.
Based on the logic presented in the video, I wrote a program that does a more efficient simulation, so that we could get a better estimate of the growth rate. Note that my simulation estimates a guest always takes the exact same amount of time to make 1 step, and there may be incorrect edge cases in my simulation.
In my simulation, I attempt each size of make 50,000 times and record the average number of steps it took to complete a maze of each size 1-25.
https://play.golang.org/p/FglwpqbsPPr
Results:
<output truncated for ease of viewing>
20 size: 9966 steps (1.397 growth)
21 size: 14057 steps (1.410 growth)
22 size: 19738 steps (1.404 growth)
23 size: 27372 steps (1.387 growth)
24 size: 38660 steps (1.412 growth)
25 size: 54266 steps (1.404 growth)
Marcel estimated a growth rate of 1.424 per added indent, and my larger sample simulation estimates a growth rate of about 1.4, slightly smaller but very much in a similar ballpark.
Start → Mid(1, ↑)
prob: 1, time: 1?
Mid(1,↑) → Start
prob: ⅜, time: 3
Mid(1,↑) → End
prob: ¼, time: 1
prob: ⅜, time: 3
There seem to be two ways to do this. First you could determine the average time to leave the park by pumping 1 person into the park every timestep until it reached a steady-state where one person was leaving the park, then just count how many people there are in the park. Assuming steady state, you do not need to use travel times to calculate that exactly 1.6 people occupy Start and 1.6 occupy Mid, with 0.6 making the journey back and 0.4 making the fast journey out and 0.6 making the slow journey out. These two slow journeys taking time 3 can be viewed as having (3–1)•0.6 occupation, or 1.2 people in each, so the total is 1.2 + 1.2 + 1.6 + 1.6 = 5.6 people in the park, so this should be the number of timesteps.
Or if you prefer a straight calculation it is S where
S = 1 + T
T = ⅜(3+S) + ¼(1) + ⅜(3)
I think the former approach is going to be theoretically easier to understand when you are asking, “I want to convert End to Mid(n+1, ↑) and introduce a new End and also a node Mid(n, ↓), how does adding these three nodes change the system?”
In fact I think to solve it you will want to always calculate three different flows. I have only given you one of them, a steady state where one person arrives in Start and then they leave out of End. The other one is that they arrive in Mid(n–1, ↑) at a steady rate and then leave out of End at that same rate. And finally there is the flow where they arrive in Mid(n–1, ↓) at a steady rate and then leave at the same rate. [I think Mid(0, _) is just Start here.]
If I have those three populations/average travel times then I have a way to add those 3 nodes to the system at each stage and this gives me a recurrence which can calculate the thing exactly.
I would need to think a bit about how to program all of that.
The small discrepancy of 1.424 vs your 1.41 is worth digging into. It might have a surprising reason. Or you might be right. Games are simulations, and simulations have emergent behaviors when you throw in a time dimension.
That doesn't necessarily mean that my simulation is perfect (and, another commentor has made an improvement on it!), but it does mean that this evidence alone is not enough to suspect the simulation.
Run with 5 million iterations per size:
15 size: 2514.4287536 steps (1.413 growth)
16 size: 3543.3930332 steps (1.409 growth)
17 size: 4986.7099864 steps (1.407 growth)
18 size: 7008.892906 steps (1.406 growth)
19 size: 9834.1058896 steps (1.403 growth)
20 size: 13806.3093036 steps (1.404 growth)
Also seems like it converges to a value below sqrt2, which doesn't surprise me. The function that drives the behavior just doesn't feel like it would end up on an irrational number for a growth rate.
If you are nostalgic for RCT2, I'd suggest trying Parkitect on Steam. It feels like an updated version of RCT2. It sorta lets you play the game with rose tinted glasses on.
There are a few things I think it does better:
* A lot of modernization stuff: better OS support, keyboard layout support, clamping of input for multi-monitor users, steam workshop support, fewer obvious pathfinding issues, removing a few abusable strategies, etc.
* The hauler system. Shops no longer conjure product from the ether. A new worker type, haulers, have to deliver it to the back of the store.
* Janitors need to drop off garbage in trash chutes.
* Guests don't like seeing park infrastructure (eg haulers, employee paths, break rooms). It's not hard to hide this, if you don't feel like putting effort in.
* An option to copy a decoration item under the cursor. It is nice if you want to design a new building to match an existing on.
* Live previews of how your ride will work as you are building it.
The PRNG has finite state. This means that it must be cyclical. This cycle of of states will manifest in a guest which will either loop infinitely without progressing into the maze. Or it will manifest in a guest which will progress a fixed, finite number of steps into the maze before the state of the PRNG cycles.
Therefore the guest either never completes the maze, or the guest completes the maze in time O(n * 2^k) where k is the number of bits of state in the PRNG and n is the number of inlets.
Assuming a roughly 4Hz update rate, 10^20k years is around 10^2.5trillion iterations.
The PRNG has fewer than 2048 bits (being very conservative), and with (let's round way up) 100 patrons exploring the same let's say 256 slots or so [1], you can encode an additional byte per patron, but you're still a long, long ways away from coming even close to the size where it's even close. That gets you a very generous 2^4608 (approx 10^1387) states you can reach, which isn't anywhere near close to the number of random iterations we can guess this will take. So it's safe to say the simulation as a whole will still loop, even with the state beyond the PRNG itself.
Note you have room to add a looooooooot more state in to my estimates before it's even remotely close. There's nowhere near enough bits available to encode things and avoid loops.
[1]: The number they can explore is not relevant, it's the number they will explore. I'm also naively assuming each of the 256 is equally likely, which is false, but is also a best case for this analysis. In reality the patrons tend to encode much less than that as they are much more likely to be towards the front of the maze.
Even a Mersenne twister won't be enough to represent 10^20,000+ states that'd be needed to complete just one maze run.
At a minimum, you need a PRNG with 100,000+ bits... or a 12.5kB+ state machine for your PRNG before you had a decent chance of one NPC finishing the maze. I don't think any modern PRNG has such state (most states cap out at 64-bits or 128-bits these days, because there's no feasible simulation that'd use all those RNGs. Mersenne Twister was probably the last "old style" PRNG algorithm that tried to make a huge cycle-length with a large-state).
It's been a while since I've done this, but I think the solution is something like the last index in the vector
E[steps] = (I - A)^-1 * (1, 1, 1, 1 ...)
EDIT I wrote some numpy to verify that this solution matches the empirical growth rate of 1.4 found in the video: https://gist.github.com/mgraczyk/7917a3322f65fe60fa333da7936...
Because its an A^n kind of problem, is this a good time to use Eigenvectors?
I'm kinda bad with my Linear Algebra. Just kinda checking myself if I'm following the concept.
I just let numpy figure it out for me, but if you want an analytical solution something like that may be necessary.
Frontier used a “Scaled Word” datatype to represent the vast interstellar scale of the game, and according to [0] this had a range of 2^65536 ≈ 10^20k.
So there’s something relevant to compare the size of the maze solving time to!
2^65536 is 64kiloBITS. Not bytes.
75((7/5)^n − 1)/4 − 7n/2 for left indents,
7n/2 − 29(1 − (5/7)^n)/4 for right indents,
2n²/3 + 2n for unbiased indents.
The constants vary depending on exactly how exactly you count steps and account for edge effects. (I’ve assumed that each indent starts at the middle of a 1 unit section of the main path, and goes 1 unit to the side and 1 unit back.) But the asymptotics are definitely Θ((7/5)^n), Θ(n), and Θ(n²), respectively.
I do ok at big-O reasoning, but in this case turning probabilities into big-O eludes me.
In the video, there's an opposite maze which biases the guests to walk towards the exit, making it much easier to solve. What's the big-O of that version?
- only the most significant (in terms of exponentially) factor(s) matters for big O (i.e. if you have a linear factor, the constant time factor is ignored)
- You have to determine whether you are talking worst case or average case or best case. Assuming average case I’d guess the opposite maze is O(n) because the time expands linearly with number of segments.
(Disclaimer: I am not formally educated in computer science, so admittedly I am not up to snuff on the mathematical side of things. Hopefully I am close enough here.)
edit: Oops, I failed to actually cover any time complexity calculation at all. I do not know if my approach is correct, but here's how I view the original:
def walk_path(n):
// probability of _not_ recursing is (1/n^2)
// probability of _recursing_ is (1 - 1/n^2)
// likelihood of recursing doubles with n
// therefore, the average case of this loop is O(2^n)
for (i : 0 -> n)
if (random() < 0.5)
walk(); // = O(1)
else
// Ignoring the actual walking on the branch, we just pretend we turn around directly.
for (j : i -> 0) // = O(n/2)
walk();
return walk_path(n);
Worst case is infinite: you just always take the path back in the direction of the entrance, and never even get past the first inlet.
Best case is O(n): you always take the path forward.
The measured values are empirically exponential with a factor of 1.424 per indentation. If we assume that as an upper bound (which I don't think is quite right), then we have O(1.424^N) where N is the number of indentations.
Any exponent can be written in terms of any other base by multiplying by a constant. Since we often use base 2, we can choose to rewrite it in base 2 as O(2^(K*N)), where K is approximately 0.51.
Constant terms can be ignored in big O notation, so we can just drop the K to get O(2^N) (I am less sure about dropping a constant within the exponent).
State (0, *) transitions to (1, forwards)
For k > 1, state (k, forwards) transitions to (k+1, forwards) with 5/8 probability and to (k-1, backwards) with probability 3/8.
For k > 1, state (k, backwards) transitions to (k+1, forwards) with 1/8 probability and to (k-1, backwards) with probability 7/8.
My intuition is that this very much resembles a biased walk so it should take exponential time. But there is the "momentum" to take into account.
Edit: It looks like we can use https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...
Your vertices would be (x, y, f), f being facing.
Edges are along the lines of (x, y, 0) - (x+1, y, {0,1,2,3}\1); (x, y, 1) - (x-1, y, {0,1,2,3}\0); (x, y, 2) - (x, y+1, {0,1,2,3}\3); (x, y, 3) - (x, y-1, {0,1,2,3}\2).
Probabilities are modeled in the video and need to be rotated 4 times for the four facings.
After that, I just don't recall my eigenvector calculation anymore. It feels like a good markov exercise, though.
I would argue using Big O here is wrong and Landau symbols are not well defined on Markov chains/probabilistic turing machines. The point of Landau symbols is to give asymptotic bounds of functions with N approaching a certain value (usually positive infinity). My intuition says that the runtime of a probabilistic turing machine isn't necessarily a function tho (i.e. a deterministic association between any N and time(N)).
Google wasn't really helpful on complexity theory of Markov chains and based on the research papers that pop up it seems far enough away that I would avoid using Big O in this scenario.
Probabilistic turing machines even seem to have their own complexity classes (https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine).
Related: https://en.wikipedia.org/wiki/Big_O_notation#Multiple_uses
The devs have since updated the game to remove the clockwise bias.
I wanted to ask if RCT2 was Turing complete, but looks like the same person made a video demonstrating this: https://www.youtube.com/watch?v=RQGa0DPwes0
Would love to see the Game of Life implemented in it!
As a fan of RCT2 in my youth, absolutely loved this. This is some of my favorite type of content to find on HN.
I appreciate that a "proper" pathfinding algorithm like A* would not be feasible given the number of guests but maybe taking into account what the guest sees ahead of them would already make it quite a bit more realistic?
You could weight the probabilities for each direction by the square root of the length of the path or something like that. And if you can see the exit set p=0, if you can see the exit set p=1.
I'm sure it would still be easy to fool though - just build very long indents and make sure the entry/exit are not visible until the last moment.
More realistic would be observing that the entry and exit are on the outer edge and the maze is simply connected, so a trivial left-hand rule [1] will solve the maze in linear time. On its own pretty boring. You could ad some randomness to make it interesting. But would it still have linear expected solving time if you do that?
[1]: https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_fo...
If you still want randomness, give the people a chance to follow the signpost or move randomly, but bias it towards following the signs the longer they've been in the maze.
This should scale pretty well, at the expensive of requiring a one-time recomputation whenever the maze is altered.
Instead of randomly picking from the 4 sides, pick one from the set of legal moves.
For each 'dead end unit' there are four states the character can be in after having just taken a step, s = {forward, backward, inside, facewall}. Let us look at the Markov chain transition probabilities if we are in state (n,s).
- (n,forward) has a 3/4 chance of going to (n,inside) and 1/4 chance of going to (n+1,forward).
- (n,backward) has a 1/4 chance of going to (n,inside) and a 3/4 chance of going to (n-1,backward).
- (n,inside) has a 100% chance to go to (n,facewall).
- (n,facewall) has a 50/50 chance of going to (n+1,forward) and (n-1,backward).
- (0,s) always goes to (1,forward) for any s.
- (N+1,forward) always goes to itself, it is an absorbing state.
If we build up the transition matrix of the above, ensuring that any absorbing state is at the end (we only have one absorbing state), we can take matrix Q as the rows/columns that don't interact with the absorbing state. Then the sum of the first row of (I - Q)^(-1) gives us our mean absorption times.
The code: https://gist.github.com/orlp/0c5fc7264f02e3d211d42da643163bb...
The results (in format N, expected time to solve, ratio with last):
1 5.6 5.6
2 13.439999999999998 2.4
3 25.816000000000003 1.9208333333333338
4 44.542400000000015 1.725379609544469
5 72.15936000000002 1.6200150867488055
6 112.22310400000002 1.555212019618799
7 169.71234560000005 1.5122763455197248
8 251.59728384000005 1.4824925255172479
9 367.63619737600015 1.4612089278745692
10 531.4906763264004 1.445697350043086
11 762.2869468569604 1.4342433100158898
12 1086.8017255997447 1.4257121023530763
13 1542.5224158396427 1.4193227518003906
14 2181.9313821754995 1.4145216690337734
15 3078.503935045701 1.4109077674002157
16 4335.105509063981 1.408185794311686
17 6095.747712689574 1.406135952157193
18 8562.046797765406 1.404593365952747
19 12016.265516871565 1.4034337583867995
20 16853.571723620193 1.4025631923626152
21 23627.200413068273 1.4019105742407632
22 33111.68057829557 1.4014220897699503
23 46391.35280961381 1.401057028800373
24 64984.29393345935 1.400784628983539
25 91015.8115068431 1.4005816790136818
26 127461.33610958033 1.400430694396402
27 178486.4705534125 1.4003185279649442
28 249923.05877477748 1.4002353119531679
29 349935.6822846886 1.4001736534444356
30 489954.75519856386 1.4001280235262301
31 685982.8572779896 1.4000942944210868
32 960423.6001891854 1.400069389489103
33 1344642.0402648596 1.4000510191544548
34 1882549.2563708038 1.400037482094484
35 2635620.7589191245 1.400027515880301
36 3689922.2624867745 1.4000201849980958
37 5165945.767481486 1.4000147970596988
38 7232380.0744740805 1.4000108402222013
39 10125389.504263714 1.4000079365298022
40 14175604.1059692 1.4000058071840076
41 19845905.94835688 1.4000042467325944
42 27784329.92769964 1.4000031039147403
43 38898124.898779504 1.4000022674651564
44 54457439.25829131 1.4000016556067978
45 76240480.76160783 1.400001208283035
46 106736740.266251 1.4000008814215148
47 149431504.9727514 1.400000642702783
48 209204176.96185198 1.4000004684420466
49 292885919.1465928 1.4000003412933768
50 410040359.6052299 1.4000002485609422
It would be neat to have a ride that somehow makes use of these diodes to do something interesting beyond delaying people.
Then you have begun your journey.
First, using Taek's notation for the maze with the correction that entering and leaving an indent results in 2 steps rather than 1. The resulting set of equations are:
X_{0,f} = X_{1,f} + 2.5
X_{0,b} = X_{1,f} + 3
X_{k,f} = 0.625 X_{k+1,f} + 0.375 X_{k-1,b} + 2.5
X_{k,b} = 0.875X_{k-1,b} + 0.125 X_{k+1,f} + 1.5
X_{n,f} = 0.375 X_{n-1,b} + 2.5
Where the first index is the index of the current indent. Thus, n must be at least 1 but the first indent occurs at entry 0. The second index is the direction the maze goer is traveling in.
From here, we can easily get the growth rate of 1.4 which is 0.875/0.625 or more intuitively the ratio of momentum pushing you backwards vs. pushing you forwards. This is the root of the exponential growth.
Finally, I believe there is no "closed form" solution but this will be the solution of the linear system X = AX+b for the A and b shown above. I am able to convince myself that there is no nice solution because having the two dimensions (position and direction of travel) makes it impossible to rearrange the above equations and make a clever change of variable to make the telescoping sum look nice. To see this, realize that each term relies on 2 things and one those things doesn't rely on the first term.
Finally, here is some Python code that implements this:
"""
import numpy as np
n = 25
A = np.zeros((2n+1, 2n+1)) b = np.zeros((2n+1, 1))
# Setup A: the first n+1 entries will be the forward index and the last n entries will be the backwards movement
b_shift = n+1
## X_0
A[0,1] = 1 A[b_shift,1] = 1
## X_k
for k in range(1,n):
# foward movement
A[k,k+1] = 0.625
A[k,k-1+b_shift] = 0.375
# backward movement
A[k+b_shift,k+1] = 0.125
A[k+b_shift,k-1+b_shift] = 0.875
A[n,n-1+b_shift] = 0.375
# Setup b
## X_0
b[0,0] = 2.5 b[b_shift,0] = 3
## X_k
for k in range(1,n): b[k,0] = 2.5 b[k+b_shift,0] = 1.5
## X_n
b[n,0] = 2.5
X = np.linalg.inv(np.identity(2n+1)-A) @ b
print(f"The number of steps from the beginning is for {n} cutouts: {X[0,0]}")
"""