785 points by Taek on Aug 3, 2020 | hide | past | favorite | 131 comments

 Less than 48 hours after that video was published, OpenRCT2 patched their pathfinding algorithm to not prefer some directions more than others: https://www.youtube.com/watch?v=b-5aX2oLOgU.The GitHub commit message says it was just to mess up MarcelVos, the videomaker
 I found it very funny:
 And this comment both explains why it's the way it is, and proposes an improvement: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".
 It is a popular algorithm, especially because it's stateless, but it only works if the maze is simply connected, so a simple loop can cause it to fail.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.
 > It is a popular algorithm, especially because it's stateless, but it only works if the maze is simply connected, so a simple loop can cause it to fail.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.
 I think GP meant if there's an island in the middle, it won't work following that. But if you start from the entrance, it's fine.
 mcv on Aug 4, 2020 Also, the exit or entrance shouldn't be on that island in the middle. Bridges/tunnels connecting different points will also mess it up.It's a good algorithm within some very specific constraints.
 All of those things are conveniently excluded by the architectural constraint of using live hegdes as the construction medium: the maze must be planar, and the entrance and exit need to be at the outside to allow access. You can have secondary desinations in the interior that aren’t reachable this way, though.
 The hedge maze needn't be planar though, that's a faulty assumption. See Honey Pot Hill Orchard's hedge maze for a counterexample: https://www.honeypothill.com/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.
 Munksgaard on Aug 4, 2020 I'm not sure exactly what you're saying here, but if you're saying that the proposed algorithm will work for all mazes in RCT2, I think you're wrong: https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...
 OJFord on Aug 4, 2020 If the entrance were, the exit necessarily would be too; so it would work. (The island would be a corner of the maze, you'd just walk in, then left/right (according to hand) and out.
 peeters on Aug 4, 2020 How does one get to the island by keeping one hand on a wall? Wouldn't an island just be equivalent to a big empty area?
 As I said 'if you start from the entrance, it's fine'. The comment up thread that I interpreted that way (it wasn't my own) was in reply to a comment that sounded like you could start anywhere (e.g. attempt the maze in the right spirit and then give up and put your hand on any wall), not just at the entrance.
 Very true and thanks for clarifying.
 gpderetta on Aug 4, 2020 there is exactly an example of that in the github comment thread.
 liendolucas on Aug 4, 2020 I remember when I was a kid and going to my dad's office. They had Wolfenstein 3D installed and that would keep me occupied for the rest of the day. I remember my dad coming one occasion and exactly telling me that to make any progress if I was lost or blocked in one of the mazes.
 tapland on Aug 4, 2020 That would make guests follow some very strict paths, which would be much less realistic and would severely hamper any regular gameplay.
 Causality1 on Aug 4, 2020 That's a trope I always find irritating because it only applies to one type of maze: those where there are no freestanding paths, walls, or barriers.
 I think it still will work in those cases, as long as both entrance and exit is at the perimeter wall? And that it's the placements of those that determines if left-touching is a viable option. For instance, it doesn't matter if it there's a freestanding wall/loop, as one wouldn't reach that anyway.
 9nGQluzmnq3M on Aug 4, 2020 Canonical hedge mazes, like the ones in the games, typically don't have any of those.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.
 c17r on Aug 4, 2020 My Minecraft cave process was "torches to the right on the way in" so it's easy to backtrack
 hwc on Aug 5, 2020 This is why I always design 3-dimensional mazes.
 infogulch on Aug 3, 2020 It's always so wholesome when devs interact positively with 'exploit hunter' types. I wonder why it feels like that.
 Probably something to do with the "status games" definition of friendship from Impro. Friendly ribbing in a faux-antagonistic relationship may also come off as really healthy-looking, comfortable, and pleasant, for similar reasons, namely that you can't do that safely with people you aren't on good and (at least in some confined sense) equal terms with. So from the outside it's like vicariously being part of the everyday intimacy of a friendship.
 I like this perspective. It acknowledges that they are equal at least in that they both care about the game and express that by paying attention to all of its detail, even small defects.
 fsniper on Aug 4, 2020 Maybe because "exploit hunter" types are in fact doing QA for the developer?
 jansan on Aug 3, 2020 It actually is funny.
 Indeed!
 I was kind of hoping they'd change it to have an easter egg, if it determines it's likely in a left only hedge maze the path finding cheats and just walks to the exit.
 According to Youtube recommending a newer video by the same author, you can still build impossible mazes:
 orlp on Aug 4, 2020 That video is not correct, Marcel incorrectly assumes his relationship is still exponential, but it's an unbiased random walk now, which has an expected quadratic solve time.
 Taek on Aug 3, 2020 For a proper fix they would probably want the guest to remember places they had been previously and bias against those places.
 Real-life mazes are sorta known for not working like that: https://youtu.be/u9xvrbfyKGQ?t=425
 Well, you'd generally remember the last few turns you'd take. The longer the loop, the harder it is to detect. So the algorithm could do something similar - and it would also help with keeping the memory bound sane.
 egypturnash on Aug 4, 2020 There's a suggested fix for just this on the Github discussion. https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...According to their quick test, this will definitely result in guests solving mazes a lot faster.
 This approach appears to do something different, which is allow the guests to cheat - it relies on information a real maze solver would not have, including how close a tile is to the exit.
 Taek on Aug 4, 2020 Not going to break immersion for me if guests are casually cheating. It's nice to see:1. guests wandering around randomly - every part of the maze is regularly visited if the maze is busy2. guests being not hopeless at actually solving mazesIf 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.
 Oh, I agree with that, I especially wouldn't want to see a left hand rule solution, but my point was just that it's not just> remember places they had been previously and bias against those placesWhich 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.
 That change still leaves a small bias in the case where there are 3 directions to choose from. The effect is presumably small (I don't know how many bits are produced by scenario_rand()), but it would be assuming to try to figure out the maximum maze bias that is possible to extract from this.
 Oh, I didn't realize this was OpenRCT2, rather than the original RCT2. Do we know if the original game has this same oddity?
 I didn’t even know OpenRCT2 was a thing. I wish I’d discovered that at the start of the pandemic!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.
 simcop2387 on Aug 4, 2020 According to the next video from the youtuber, ye sit does.
 foota on Aug 3, 2020 It would be interesting maybe to design a system where people deviate a random amount from the optimal path.
 In the video, Marcel Vos essentially runs a monte-carlo simulation to try and figure out the growth rate of adding more elements to the maze. Though it is true-to-life, it's also very computationally inefficient.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/FglwpqbsPPrResults: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.
 This is probably a solvable number, and these 1.4 numbers are suspiciously close to the square root of two 1.41421...
 That was my thought as well, but I couldn't justify it being root 2 so I went with the number I got.
 For the simplest case you have a system of transitions`````` Start → Mid(1, ↑) prob: 1, time: 1? Mid(1,↑) → Start prob: ⅜, time: 3 Mid(1,↑) → End prob: ¼, time: 1 prob: ⅜, time: 3 `````` (not 100% sure about those times, here they are in units of the timesteps that a person spends to go from one square to another, so the 3 is “go to the left square, go to the middle square but coming from the left, go from here up/down having the normal orientation again”).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) `````` S being the average time from Start → End and T bring the average time from Mid → End. This can be solved to similarly find S = 28/5 = 5.6 timesteps.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.
 ironSkillet on Aug 3, 2020 Seems like you could come up with a recursive formula to compute the expected number of steps to reach hedge N. Along the lines of how you compute the expected number of coin flips to get K heads in a row. I'm too lazy to figure it out right now though, so there may be some nuance I'm missing.
 Isn’t this just a Markov process, shouldn’t we be able to calculate the exact waiting time?
 Yep, this is just a standard Markov process which should be easily solvable.
 Instead of running random simulations you could deterministically transport probabilities around an array, (or just set up a linear system whose solution gives the expected time).
 Doing a more sophisticated simulation, I think it's trending towards 1.4 exactly (42 to 43 is 1.400003). Idk how to prove it though.
 This assumes the code works exactly as described in the video. For old games, this has historically been false; it’s very, very hard to reimplement most game mechanics faithfully, often due to small corner cases that matter. Many gameplay mechanics are an emergent effect of bugs.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.
 Taek on Aug 4, 2020 The discrepancy is fully explained by variance. Some of the results that went into computing 1.424 had less than 20 samples, which is not enough to get a precise answer for such a highly variant task.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.
 Small nitpick with your code, you define a step to be both a forward/backward movement and going into the corner and coming back (which I would define as 2 steps because the person has to spend twice as long completing that). Also, you didn't use floats for the expected times. I have made both changes and added them here:
 Taek on Aug 4, 2020 Thanks for the changes! Interestingly enough, it seems to have had very little / no effect on the growth rate. Nice to have the precision in the outputs.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.
 I've seen this guy's videos before, and I'd imagine they'd have a fair bit of appeal to HN users who are familiar with Roller Coaster Tycoon. He manages to really get into the details are determine why things work they way they do.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.
 OpenRCT2, the open-source project that improves RCT2, has some of these features as well. It has a scenery picker and it also has a ghost train feature for rides under construction. It also makes it run much smoother on modern systems and introduces a keyboard shortcut for almost everything, although vanilla RCT2 also had quite a few already.
 Also, there's a basic line-of-sight system for scenery ratings, with lower ratings for haulers, employee-only paths, and employee-only buildings, so you actually have a reason to build walls and fake scenery to block views of the 'backstage' areas that haulers pass through.
 Planet Coaster is also great. It's more of a modern take on the theme park sim idea than a faithful recreation of the original. Kind of the Cities Skylines to RCTs Sim City.
 The fact that this is done on a computer with a PRNG is significant here. (unless the game sources entropy from the environment, which is unlikely)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.
 I've not looked at the source, but I doubt that each guest has a unique PRNG. It's more likely that there's one PRNG for the whole game, and so the behavior will depend as much on the number of guests in the park as anything else.
 jerf on Aug 4, 2020 This is true, and it'll extend the size of the loop past the naive "once around the PRNG". However, 10^20k years is so much larger that it's safe to guess that even if you do your best to extend the size of the loop based on the behavior I saw there (the park puts in a certain number of people which stays fairly constant), you still end up with too few states reachable to ever prevent looping.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.
 That's a pretty funny thought.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).
 Could be solved by re-seeding the PRNG once in a while. Probably after N samples were taken.
 Or the game could just use the OS equivalent of urandom, which adds environmental randomness to the pool when available. I'm pretty sure there's something similar on Windows...
 The way to get a closed form solution for the expected time is to note that there are 2N + 1 states. N states for each notch and each direction, and one "final" absorbing state for the end of the maze. You can write a matrix A where the transition probability between states i and j is given by Aij. Then A^n gives the distribution over states after n steps.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 ...) `````` I-A is called the "fundamental matrix" of the markov chain described by Aij.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...
 > Then A^n gives the distribution over states after n steps.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.
 A^n can be computed many ways, and it is not necessary to actually do any matrix multiplications. I think what you're referring to is diagonalizing the matrix A=PDP^1, then computing the matrix power of the diagonal matrix A^n = (PDP^-1)^n = P D^n P^-1.I just let numpy figure it out for me, but if you want an analytical solution something like that may be necessary.
 Fans will recognize that RCT is a descendant of Transport Tycoon, which was created by Chris Sawyer, who ported Frontier Elite 2 from m68k assembly to x86 assembly (and inserted an advert, visible in some spaceports, for “Chris Sawyer’s Transport Game”).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!
 This comment reveals the insight that 10^20k is equivalent to the number of different possible 64kB files
 8kB files actually.2^65536 is 64kiloBITS. Not bytes.
 If I’ve calculated correctly, the expected number of steps to pass n indents is75((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.
 Short version: Roller Coaster Tycoon has a random walk type maze solver, and you can create a maze which takes O(2^N) time to solve.
 Is it really O(2^N)? If so, how'd you determine that so quickly? I'd like that intuition.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?
 Let's pose the problem mathematically. Initial state is (0, forwards).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...
 Came here for this - I knew there must be an analytical solution involving Markov chains.
 tetha on Aug 3, 2020 I'm pretty sure this can be modeled with markov chains.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.
 ascar on Aug 3, 2020 I'm also absolutely not an expert on this (M.Sc. CS).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).
 Sure you can use Big O, just look at it as the expected runtime. For example, QuickSort is O(n^2) in worst case, but expected O(nlog(n)).
 For probabilistic algorithms, we can look at the worst-case-w.h.p runtime: that is, a randomized quicksort, although technically still having an "absolute" worst case of O(n^2), actually is considered to have a worst case of O(nlog(n)), with probability 1 - 1 / (n^c) when bounded by Chernoff, as shown here: https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lect...
 contravariant on Aug 3, 2020 Note that they likely messed up slightly, it'll be more or less exponential in some base but possibly not 2. However big O notation does require you to get the base correct (or at least provide an upper bound), you can't ignore it like you can ignore a multiplicative or additive constant.
 jchw on Aug 3, 2020 I think the key insights are:- 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); `````` and the opposite is straight forward, since the branches are 'constant time' - so it's more like a straight loop.
 In this instance, you're only concerned with the average case.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.
 jchw on Aug 3, 2020 Yep, sorry, it quickly became apparent after rereading this that the original analysis was not worst-case. I have revised my comment to also include how I view calculating the actual time complexity since I didn't actually do that initially.
 nitrogen on Aug 3, 2020 I'm not 100% confident in my explanation below, but maybe it's something like this, if we don't have prior knowledge of the asymptotic behavior of random walks: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).
 You can't drop constant multiplicative terms in an exponent - O(2^n) is not equivalent to O(2^(2n)) as O(4^n) \= O(2^n) (the first one grows a lot faster).
 You cannot drop constant terms from exponents in big-O notation.
 Note that calling it 2^O(N) (or Omega) would be more accurate, unless you stumbled upon a really lucky coincidence.
 Interesting, I'd never seen this kind of thing.
 titanomachy on Aug 3, 2020 Are there any functions f(n) ∈ O(n) such that 2^(f(n)) ∉ O(2^(n))? If not, then either statement is accurate.
 Yes, for example 2^(2n) ∉ O(2^(n)). Any function of a different linear coefficient. Big-O notation represents a bound by a constant factor (by modifying the exponent multiplier you get an exponential factor).
 Thanks, you're right of course.
 It's actually worse than a pure random walk - it had a clockwise bias which could be exploited to create travel asymmetries.The devs have since updated the game to remove the clockwise bias.
 Why does he take the fourth root to find the multiplier per indent? That was the only part where he lost me math-wise.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=RQGa0DPwes0Would 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.
 The multiplier of 4.11 was for a tile of length for the test mazes, which is actually 2 more tiles of maze. Every tile has 2 indents so one tile of length has 2*2=4 indents. Therefore we need to take the fourth root to go from the multiplier per tile of length to the multiplier per indent.
 Thanks! Great work here :)
 evanb on Aug 3, 2020 Making the maze longer by just one rule increases the number of indents by four. But, for his calculation the number of indents in the hindrance (it is valid to do it as a function of the number of tiles, instead, of you want) but the conversion rate (4:1) is in the power because it’s an exponential process.
 "If you want a new way to torture your guests, this is an excellent method".
 Hell is on Earth, and it's disguised as children's park building game.
 I WANT TO GET OFF MR BONES WILD RIDE