OpenRCT2 Changed the Maze Pathfinding Algorithm

[@PimStoit]

"This is just to mess up MarcelVos". I love the devs.

[@porsche911sbs]

they must love him, great quality tester for them

[@KamikazeCommie501]

Yeah right. Marcel spends time researching and making a video about a cool thing he found, and the OpenRCT2 devs instantly try to 'fix' something that didn't need to be fixed, just so the video that probably took Marcel longer to make than the devs took fixing the code would be wrong. Now MarcelVos has a video only a few days old that's obsolete.

[@Dimitri88888888]

@@KamikazeCommie501 I think you are overthinking this.

[@PimStoit]

@@KamikazeCommie501 The video isn't obsolete, however. First and foremost because the problem had historically existed and the video documents it, and secondly because it was only fixed in OpenRCT2. The problem still exists in the original game, which is the version most people are familiar with.

[@MarsCorporations]

@@KamikazeCommie501 How is that a bad thing? If a dev would notice me finding bugs and the dev fixes them, I would be proud because I am the reason the game got a bit better.

[@AposineYT]

"Only ran the game for one thousand years"

[@spork217]

Making progress

[@johnfoltz8183]

The maze never ends.

[@WDC_OSA]

For me, it was Monday

[@brantnuttall]

Yeah, that made me laugh

[@PROPLAYEN]

No he sped up time

[@KaedennYT]

They made the update specifically to spite you. That's some clever trolling right there.

[@Kalvinjj]

And literally mention it

[@Manticore_007]

Or is it the other way around? Marcel trolling the devs.

[@Goldenblade14]

Marcel Vos: "Mazes are broken." OpenRCT2: "Here's an update that fixed the mazes." Vos: *"But are they though?"*

[@DarkOmegaMK2]

"LET'S FIND OUT!"

[@ruediix]

Yep I was just coming here to show the fix: I know the fix I would use: Randomly select counterclockwise or clockwise after initial failure.

[@Gelikafkal]

@@JuliJaneMusic its not about solving the maze as efficiently as possible. Have you ever seen real humans running through a maze? They forget that they were at a specific intersection and check dead ends multiple times. Some of them even get lost entirely. A random selection is much more realistic than any graph based approach.

[@pbnetto]

*Vsauce music starts*

[@Manticore_007]

@@pbnetto thank you! I heard the music too!

[@PaulFisher]

On the first video I was going to ask “is this real-life years or in-game years?” But then I realized: at this scale, it simply does not matter.

[@horngeek9115]

It actually would make a difference in the exact number you use lol- I *think* it works out to an addition or subtraction of 3 orders of magnitude.

[@PaulFisher]

@@horngeek9115 in some respect this is true, but in my estimation, the calculations had enough approximations already taken that there’s not enough accuracy for it to count.

[@Gameprojordan]

1000 years at hyperspeed takes like 12 hours

[@The360MlgNoscoper]

@@horngeek9115 the difference would be smaller than any rounding error

[@Konomi_io]

@@Gameprojordan that makes no difference at the scale of the numbers in the video

[@SirGigster]

I want to get off Marcel Vos's Wild Maze

[@capacitatedflux]

T H E H E D G E N E V E R E N D S

[@johnfoltz8183]

Mr. Bones Wild Hedge Maze

[@seokkyunhong8812]

Now you can

[@epicboomshine6595]

Just looking at Marcel Vos’ Graveyard makes me sick!

[@SongbirdOfficial]

- Open RCT2 devs, August 1st, 2020

[@Nitron2097]

Well, shit. Now you're actually helping DEVELOP the game. Kudos. :D

[@DaVince21]

He has been! Just check his Github history... :)

[@Aereto]

In other words, he is a bug/exploit hunter.

[@Dripikdrippydipsdropkicks]

"only ran the game for 1000 years" yeah so casually only ran this theme park much longer than theme parks themselves have been around. Some say this theme park was the real beginning of Christ

[@Codraroll]

Others say this maze is why Christ hasn't returned yet.

[@shanestaley6595]

Bacon bob dont worry, the devs are trying to fix that bug

[@_iphoenix_6164]

Huge kudos to the devs here

[@carykh]

I was just thinking, what if you made the big maze right-indented, but used the guests' old asymmetric maze-solving algorithm? My gut feeling is that the estimated amount of time to finish the maze drops longer than the heat death of the universe, to just a few hours. (because it's now the guests' natural inclination to move forward along the maze)

[@roi8138]

Hello cary key hole

[@kosherkingofisrael6381]

It would still take the same time as the new big left-indented maze. The new one has the same bias as the old one but, the bias is bi-directional.

[@tcoren1]

carykh I think his calculations are quite problematic to begin with, so the numbers he gets are likely very much not accurate. He assumed that the length of time increases exponentially with the size of the maze, which might be a good approximation in the backwards skewing maze, but is very wrong here I think. The guest’s progresses seems pretty similar to a random walk, which would mean that the time to solve his quadratic (if a maze is 1000 times as long, it takes a million times longer to complete, which is a large number but much smaller than something like 1.05^1000). For the right sided maze, the progress is linear in time (ignoring random fluctuations we expect the guests to advance a tile every such and such amount of time), so the solve time should also be linear in size

[@Empiro3]

@@tcoren1 Yeah you're correct. For some reason I got it in my head that for a random walk, the transition distance goes up with the logarithm with the number of steps (which would mean that the number of steps to solve is exponential), but for a true 50/50 random 1-d walk, which is what this is, the distance is indeed related to the square root of the number of steps. The time-to-solve would still be really high, but certainly not heat-death of the universe long.

[@AkumaADemoncus]

Inb4 OpenRCT2 devs implement Trémaux's Algorithm.

[@jamessteckel5379]

guests also get tired/hungry early on in their forever journey through Marcel's Wild Maze, so they travel at a fraction of the speed...

[@jamesgaming7198]

Yeah, that really should've been factored in, unless those movement speed penalties don't apply in mazes or something.

[@squashiejoshie200000]

@@jamesgaming7198 They do apply, but the time it takes them to navigate the maze is long enough that it just gets factored into the calculation naturally. If you look at the video at 3:20, the guests in the longer mazes are moving at minimum speed.

[@PianoKwanMan]

@@squashiejoshie200000 Also, unless they travel at hundreds of orders of magnitudes slower than not tired guests, then it wouldn't change the result

[@wishonpleiades6288]

I wonder if the original pathfinding algorithm was implemented that way to save computational resources on weaker hardware back in the day. Since the new algorithm checks all four directions, it probably takes slightly more resources

[@reillywalker195]

You're probably right. After all, the reason why guest pathfinding sucks isn't because programming good pathfinding is difficult but because having hundreds or thousands of guests with good pathfinding would kill the framerate.

[@KuraIthys]

Wouldn't surprise me. RCT2 is what, from 2002? I was making my own games back then. (hard work, since pre-baked game engines were not a thing and not really accessible to amateurs), and well, fairly basic things could still cripple PC's back then... I don't even know what the minimum system requirements were, but they were probably a lot lower than the state of the art from that year... Granted, it's a lot more power than Transport Tycoon had; A game that had to run on a 486 systems... It's always bemusing watching the pathfinding problems TTD had. The pathfinding algorithm it uses is more robust than you'd expect for a game running on a 486, with I think, only 4 megabytes of RAM required, and having to do pathfinding for up to 400 vehicles (default settings are about 100 of each type if I recall) I believe the algorithm is something fairly decent. But vehicles still get confused because to save performance a vehicle only checks 8 steps ahead. Any route with distances longer than 8 squares the game takes such an obscene simplification that you never know where a vehicle will end up. And yet, for all that, vehicles go the correct direction more often than not, with only a tiny bit of handholding from players every so often...

[@Mattpoppybros]

thats definitely the reason pathfinding outside of mazes is so bad, but i think the reason its like this inside of mazes is so that guests spend longer in them

[@WillowEpp]

My immediate thought was Chris just had a series of conditional jump instructions that started with the same direction every time in his original code and that propagated to the sequel.

[@CODMarioWarfare]

KuraIthys RCT1 could run on W95 with a Pentium 2. It’s still had to be designed to handle something like 9000 agents (guests and trains etc) though.

[@ByTalo]

Most Devs: Oh god these nerds found another bug. Now we gotta spend weeks fixing it. OpenRCT2 Devs: A broken mechanic? One sec... There, gone.

[@hellishinc]

That's the power of open source software. Anyone can make a change.

[@gloweye]

To be honest, he did spell out where it was, so it was probably easy to fix.

[@MattSpaul]

A sign that it's well-built code if it can be fixed quickly without breaking other things

[@The360MlgNoscoper]

Pretty much wube software too

[@mikechurvis9995]

Also, most bug reports aren't *nearly* as well-written as the average MarcelVos video

[@hunterwylie6969]

"Maze map at 6:19 looks too intense for me"

[@davidmoore1253]

I too prefer mazes with no inversions.

[@Whatsuppbuddies]

Negative Gs, baby

[@LKDesign]

I think he was testing this new Australia mod.

[@offrails]

I wonder what the original motivation was behind the original algorithm, as if you eliminate the random chance and force a single direction (i.e. always turn left, if not possible go straight, and if that fails turn right), if the maze has a single entrance and exit, it will eventually be solved - this was the technique I used when solving the maze in 7th Guest. The algorithm is also used in that 3D maze screensaver that came with later versions of Windows 95, you will notice that the camera always hugs the left (or right) wall and will always come to the solution. I personally suspect that when Chris Sawyer was developing the game, he wanted a balance between an "always solving" algorithm and a "completely random" algorithm so that peeps would tend to use the wall-hugging algorithm so that they do get through the maze, but add in some randomness so that they spread out a bit more. What I would like to see: A comparison of solvability of "standard" mazes using the different algorithms (wall-hugging, old algorithm, new algorithm)

[@Themaxleydog]

problem with the wall hugging algorithm is if you let players make their own mazes (which a player can make whatever type of maze they want) then theres the possibility the player will make a maze that contains a loop with no dead ends which will cause the guest to walk in circles forever

[@duncanfrot4318]

The original algorithm was designed to be as simple as possible to implement in assembler. My version is also very simple but it uses more memory and CS tended to design things to not use any additional memory if not required. It's one of those things where once it sort of works there isn't much point changing it.

[@karelspinka3031]

@@Themaxleydog Is it possible though? If you start wall hugging immediately upon entering the maze, I think you cannot enter a loop. The only exception I can think of is putting the exit in the middle of the maze.

[@Themaxleydog]

@@karelspinka3031 well pretend you have a maze that is only one single loop , they enter the loop and keep turning left , if the exit is on the right they will never turn toward the exit , so yes they will turn left forever if theres a loop

[@Forthro]

As it is already said, most likely it just was the simplest possible algorithm that required minimal number of calculations while being random enough. Prevent guests from turning back (because this behavior doesn't make any sense) and generate new direction in the smallest number of steps if the one that was randomized is not valid.

[@robertstegmann9260]

Fun Fact: Make a large maze with no walls. The guests will struggle and get lost

[@nthgth]

Just like on large open areas of tarmac, lol

[@claudetheclaudeqc6600]

Between 20 seconds to infinity

[@HeliosExeunt]

I saw this on a multiplayer server once. The builder named it "THE EXTREME IDIOT TEST".

[@slowfreq]

Man, I was just thinking "I wish I could unwatch that hedge maze video and watch it again cause it was so cool the first time", and here we are with a whole new one!

[@anttiroysko3871]

With the new algorithm, the expected time spent in a maze should increase quadratically, not exponentially. If it takes a quest 1 second to walk 1 tile, then it should take by expectation n (2n + 7) / 3 seconds to solve a n-indent maze (assuming the maze has no turns, and it is impossible to leave from the entrance). As I understand your chart, the number of indents is length * 4 - 2. The ratios should then be around L = 6: ~1.44 L = 7: ~1.37 L = 8: ~1.31 L = 9: ~1.27 L = 10: ~1.24 L = 11: ~1.21 L = 12: ~1.19 L = 13: ~1.17 L = 14: ~1.16 ... This matches well for small lengths, but for larger lengths the solve times in your chart increase more. Maybe it is somehow caused by the turn in the maze? ------------------------------------------------------ Say we have n indents. Then we have 2n states: for every indent i, the state where we are going forward F_i, and the state where we are going backward B_i. State F_{n+1} will denote the end of the maze, and B_0 the start If the current state is F_i, the next state is F_{i+1} with probability 0.75, and B_{i-1} with probability 0.25 (as we either go straight ahead, or go into the indent, after which we go to F_{i+1} or B_{i-1} with equal probability). Similarly from B_i, the next state is B_{i-1} with probability 0.75 and F_{i+1} with probability 0.25. For B_{0}, the next state is F_1 with probability 1. Denote by E[F_i] or E[B_i] the expected amount of tiles we walk, if our initial state is F_i or B_i respectively, until we reach F_{n+1} (the goal of the maze). We have: E[B_0] = 1 + E[F_1] E[F_{n+1}] = 0 E[B_i] = 2 + 0.75 E[B_{i-1}] + 0.25 E[F_{i+1}] E[F_i] = 2 + 0.75 E[F_{i+1}] + 0.25 E[B_{i-1}] We add 2 instead of 1, as with probability 1/2 we walk into the indent, which is 2 tiles of walking, so we walk 1 + 1/2 * 2 = 2 tiles by expectation to reach the next state. We have E[B_i] + E[F_i] = 4 + E[B_{i-1}] + E[F_{i+1}], thus E[F_i] - E[F_{i+1}] = 4 + E[B_{i-1}] - E[B_i]. Adding these up for i = 1, ..., n we get E[F_1] - E[F_{n+1}] = 4n + E[B_0] - E[B_n]. But since E[F_{n+1}] = 0 and E[B_0] = 1 + E[F_1], we get E[B_n] = 4n + 1. Since E[B_n] - 2 = 3 (E[F_n] - 2), we also get E[F_n] = (4/3)n + 5/3 To get from F_{n-1} to F_{n+1}, we need to go through F_n, so E[F_{n-1}] = ((4/3)(n-1) + 5/3) + E[F_n] = 4/3 (2n - 1) + 2*(5/3). By induction, we get that F_{i} = (4/3)(i + (i+1) + ... + n) + (n-i+1) * (5/3). Thus F_1 = 4/3 (n (n+1) / 2) + n (5/3) = n (2n+7) / 3

[@zilvarro5766]

Yeah, I also found it should increase quadratically. Take this upvote, my fellow soldier of maths.

[@moseszero3281]

I upvote for the maths I don't understand.

[@KAngel32]

Im scared

[@macdjord]

Note that if the guest goes into the indent, that adds 2 units to their time before the progress to either the next or previous junction.

[@cancercentral9997]

nerd mad respect still

[@anter176]

So now that there's a 50/50 chance for a guest to gain/lose progress in the mace, how'd the times change if you had indents on both sides? That should mean that there's a 3-way split between gaining/losing/no change when coming out of a indent And a 66% chance of going into a indent when they first encounter the intersection. I suspect that guests won't lose more time by walking backwards with this layout, but they will be ~16% units more likely to go into a indent, where the odds going forwards and backwards are equal when they then walk out The time they spend walking between two indents probably isn't worth as much as sending them back one intersection, but it could add up, and surely it can't be worse than indents on just one side! I mean there's twice as many indents per intersection!

[@zuthalsoraniz6764]

When entering an intersection: 1/3 continue, 2/3 go into an indent When entering an indent: 1/3 forward, 1/3 back, 1/3 other indent -> Subtotal: 1/3+2/9 forward, 2/9 back, 2/9 go into an indent And you just repeat ad infinitum, ending up with 1/3+2/9+2/27+2/81... to go forwards, 2/9+2/27+2/81... to go backwards, so in total you end up with a 2/3 chance to keep going and a 1/3 chance to change direction at each intersection, if I did not do my math wrong. Of course, you have a chance to spend an arbitrarily long time in between bouncing between the two indents.

[@MercenaryFox]

hello, furry

[@davidmoore1253]

Also this takes up 50% more space. If you want to make the hardest possible maze within a restricted space that will make a big difference.

[@GroundHOG-2010]

@@zuthalsoraniz6764 The easier way of solving it. When encountering an intersection there is a percentage of continuing (1/3) and a percentage of going into an indent (2/3). There is only two valid ways of getting out of an indent, forward and backward. If you go into anouther indent you will just get back to the same choice. Since there is an equal likeliness of going forwards or backwards, the chance of both when going into an indent is 1/3. So the chance of continuing is 2/3, while the chance of reversing direction must only be 1/3. This does assume an infinite amount of time bouncing between indents.

[@Flywolf79]

If the added third option is just "no progress" wouldn't that just extend the time by ... ah maybe not so simple as I thought when I started typing ... I need to think about it :D

[@easysteezy58]

1:48 wait that dude completed the maze in YEAR 1, what an absolute BEAST!

[@HellScream107]

KZbin randomly brought me to your maze video for some reason. I had not played RCT in almost 15 years, but I could not stop watching your videos. I bought RCT Classic and have been playing the game a lot. Please keep up the good work!

[@nick32145]

2 videos in a week? What a treat, and on my first day of work too thank you!

[@I3asher]

You did this, Marcel. Be proud.

[@Mallow-568]

"I'm about to ruin this man's whole maze pathfinding career"

[@VincentRubinetti]

Marcel: I am never going to financially recover from this

[@Omnicide101]

Man, I'm Dutch myself, and normally strong Dutch accents in English just hurts, but yours really works for some reason. Toffe video!

[@HedgehogStudios1]

I've heard heavier accents from friends

[@daangeboers2406]

I usually feel the same but his is very easy to warm up to

[@Uncle_Yam]

I feel like the devs intentionally made the algorithm to give a bias towards one side - this is how you solve mazes in real life- if you just hug left the whole time you eventually make it out. I wonder if a 50/50 algorithm makes "normal" mazes way harder to solve

[@BigDBrian]

I mean, I think chris sawyer just wanted a simple, working algorithm for guests to walk around and didn't care about how well it actually held up to scrutiny. It's just a single flat ride in a state of the art theme park sim.

[@oelboy]

It would also look a bit weird if all guests were using the same one or two paths

[@AndyLundell]

The original algorithm was easier for the CPU, so they probably implemented it that way automatically without thinking too hard about fail conditions.

[@KasedaFromMinecraft]

The devs probably only implemented it that way because it's the least resource intensive way to implement random movement decisions. In the worst case with a completely random algorithm, an immortal being wouldn't make it out of the maze before the heat death of the universe (assuming it has at least two intersections) since you can randomly keep going between the two intersections without ever reaching the entrance or exit. The chance is incredibly small, but exists. I think it would be hilarious for the devs to add a 1/1000 chance that a guest uses a follow-the-left-wall algorithm when entering a maze. It would be easy enough to implement- it would basically be the original algorithm except instead of randomly choosing the initial direction the initial direction is always to turn left. This would add a bias for indents on the right, so maybe there's another 1/1000 chance that a guest follows the right wall instead. Most guests would be stuck in the maze, but over a long period of time, some guests would just waltz through the maze.

[@Leyrann]

Except that bias is nothing like hugging one side. Hugging one side would mean that your bias should flip every time you turn around. Oh and also, that trick only works for mazes where you're looking for an exit. If your goal is, for example, to reach the _center_ of the maze, it doesn't work.

[@jamesflameson]

trying to make the impossible maze in OpenRCT2 after your video felt like trying to make an Aether Portal in vanilla minecraft

[@Davtwan]

“I want to get off Zeno's Paradox Maze.”

[@hindigente]

Just goes to show how impressive OpenRCT2 is.

[@ItzzzBeamo]

I wonder if theres a way to add into the guest's algorythm a way to mimick being "aware" of having already walked through a tile in a maze, like if someone in real life was walking through a maze, and after walking through a certain part of the maze 3 or 4 times, gets a "deja vu" moment and goes "Oh, I've been here already a couple times." , and the algorythm trying to replicate that would then reduce the probability of returning to a tile that it may have flagged as being travelled through more than once.

[@duncanfrot4318]

There has already a proposed redesign that adds memory for the last ~4 decisions but it wasn't going to be deterministic (would cause issues on network games) until the new save format is implemented.

[@KuraIthys]

You could make the game's maze solving behaviour arbitrarily complex (you could even have different peeps use different solving strategies if you wanted to). But, that does come at a price to performance. Less of an issue now of course given how much faster computers are. But calculation time and memory use are not free. Just a lot cheaper than they used to be. XD

[@Codraroll]

Maybe the game could compute a correct path from the beginning to the end of the maze, then make it so guests would never walk any part of that path in reverse? Of course, it would break realism in multi-path mazes (where guests could take a detour and then immediately know the right way forward once they merged back on the main path), but it would make Marcel Vos' test mazes trivially solvable.

[@AbacusManify]

A depth-first search algorithm would be ideal and decently realistic, but would change how guests navigate mazes and make them much, much better at it than they currently are.

[@coling.4476]

Instead of having your maze with an indent on one side, make it so it has an indent on both sides. This will increase the time it takes the guests to complete the maze! Previous this was a bad idea, but since they removed the bias it works perfectly!

[@jluijk542]

6:17 confused me. WTH is going on with my brain? But then I saw that the background was upside down

[@Manticore_007]

Putting the Marcel in M.c.escher

[@TheBoneKing]

King you made me play rct2 all over again thanks for it

[@recessiv3]

Hi Marcel, great video This is actually a great example of an absorbing Markov chain, and as such this problem can be solved exactly to tell us the precise number of steps (where a step is going one indent forward/backward) on average is required to escape the maze. I quickly created a couple of python scripts with one that runs a simulation of this scenario, and another that automatically computes the mean absorption time (steps required to escape) for a given size of a maze. Running the simulation and the analytic calculations shows that they agree, and also that for each indent added, the average steps required to complete the maze increases almost perfectly linearly, with an increase of almost exactly 2 extra steps for every tile added. As an example, for a maze of 2 indents, the average steps needed to escape is exactly 41/9, or 4.5555. Running the calculations on an indent size of 40 (given that you said for every tile an extra 4 indents can be added, so this should give the steps required for a maze of 10 tiles) you get 76.5 average steps to escape the maze. Given on average a guest takes 76.5 steps to escape a 10 tile maze, and a 10 tile maze takes 7 minutes and 12 seconds to escape, that should mean it takes a guest roughly 5.65 seconds per indent. Using this number, and the required steps of 257512.5 (calculated using the value of 128,756 indents for the large maze you mentioned in your last video) that shows that this maze should take about 1454946 seconds to escape, or roughly 16.8 days. I just thought it was a cool thing to note that this problem can actually be precisely solved mathematically, the only thing that differs is the time taken for a guest to complete one step (move from one indent to the next) which I imagine may vary. Also just as a fun note, if there's instead a 37.5% of going backwards (as is the case in your first video), the time to solve is about twice as much as is now. For 10 tiles (40 indents), it takes 148.5 steps on average as opposed to 76.5. This value increases by 4 for ever indent added however.

[@luigiforsthoffer]

Look at all those guests with their heads down in the mazes. They're not going to make it. This labyrinth is going to have some bones as decoration.

[@epicboomshine6595]

The literal bone zone.

[@nthgth]

Reminds me of Wolfenstein 3D; back in the day I imagined the bones you'd sometimes come across were other protagonists (not that I knew the word) who had not solved the mazes and died

[@lyznav9439]

@Marcel If you look at the new algorithm, then it is equivalent to a random walk with a bias of 25% against 75%, but with one change. The chances are 50% to go forwards and 50% to go in. If it goes into the indent, then upon return the chances are 50% forwards or backwards. If the guest turns back, then the probabilities switch. When again the guest turn so as to face towards the exit, the probabilities switch again. So, one needs to keep track of which way the guest is facing, which is I think usually not a property of random type walks. I am not a combinatorialist, but my guess is that one can either 1) simply simulate the random walk with these modifications or 2) directly calculate the probability of completing after a certain time. In terms of 2) there is a rule about sqrt(n) distance for a nonbiased random walk, and I think it is possible to directly calculate for a (25%,75%) walk. One has to be careful to take into account whether the guest faces the exit or the entrance, but this concept must exist for a random walk, and maybe one is able to find it. By the way, a random walk is simply drawing a trace of up and down with a horizontal line starting point. A coin flip is also a random walk, but it is unbiased. In your case you want to get within some distance of the line, and you are (unlike a coin flip) not allowed to go to negative positions below the line, i.e., the line bounces you back as I assume the entrance does in RCT.

[@darkestccino5405]

There's still potential for improving the algorithm further and make them take more information into account, causing it to be more like if a real human was tasked with solving this maze.

[@tetraedri_1834]

But that would take up memory, making mazes computationally more expensive. Not a big issue with modern computers, but back in 1990's it may have been.

[@Anolaana]

Fantastic! Now I can get out of this stupid maze!

[@daskampffredchen]

Now you only have to walk the observable universe

[@laytonjr6601]

If you wanted to get out of this maze, just don't go into indents and go straightforward. You still have to travel across an entire parc dozens and dozens of time so even the fastest route can take you days

[@FerrybigGaming]

4:54 the new solve time is actually bigger, as it uses a tousand seperator inside the number. The old number uses a decimal seperator

[@johnnycapps9010]

Absolutely legend. Thanks for the follow up after the algorithm change!

[@despecc]

4:48 used a period instead of comma for the number on the bottom

[@Roozyj]

probably automatism, as in the Netherlands we use commas and periods the other way around than they do in the USA (which makes reading numbers 'in English' very confusing xD)

[@MarcelVos]

Shit, that's my Dutch roots showing through. We use a period for thousands and a comma for decimals.

[@gavin9088]

It's reversed in a lot of other countries, periods for separate groupings of hundreds, thousands, millions, etc. And comma for decimal place. It's weird to look at the first time but it's not strange once you figure it out

[@drunkenhobo8020]

@@MarcelVos Dutch roots? Going by your accent, your entire root system, trunk, branches and leaves are Dutch!

[@hindigente]

That's how it is in many languages. Spanish, Portuguese and French, to name a few.

[@colepdx187]

Just got my copy of RCT2 in the mail. I played RCT about 20 years ago and your videos inspired me to give RCT2 a try. Thanks for all the fun videos. Cheers.

[@ctnc6059]

When I saw the title, I wondered why they did this of all things. (Needless to say, the wondering was sarcastic and I started laughing.)

[@Trimead]

something else you could possibly do to increase the length of time to get to the end of the maze is to decrease how many turns the maze has. basically if you make a square with an open bottom pattern, leaving the very bottom pixel for the exit, you'll end up with under 100 turns.

[@strudlesgaming]

The average completion time for any maze given any preference of directions could be calculated using a discrete Markov Chain if you really wanted to waste your time in pursuit of this topic (in regards to the fact that there’s nothing you can do to address the nonlinearities in solve time). I can think of some simpler methods when the maze is restricted to right/left only dead ends like you showed, though. Let’s say you have to move forward N tiles to complete the maze. Let X[i] be a random variable that is 1 if the guest progresses further on his ith opportunity to do so, otherwise -1, then the probability of solving it in n steps is the probability that there exists some i=N. Taking the expectation over this distribution gives the average number of steps, from which average completion time can be easily obtained. Come to think of it, this approach is fairly complex too.

[@vissengek]

I just found your channel and I love it. The videos bring back so many good memories.

[@Gui101do]

So awesome that a game as old as this is still ripe for great content

[@AbacusManify]

Quite serendipitous that these videos come out while I'm studying Search in my degree at the moment. It would be interesting to see what the numbers would look like if we used algorithms like Depth-first search to prevent guests from walking backwards any further than necessary...

[@TheRasuo]

The short mazes might have different multipliers because guests are tired for less time in short mazes (slow walk speed)

[@edwardfeys5022]

Could the energy level of the guests have something to do with the solve time (and multiplier) of the longer mazes? I'm noticing that the guests in your longer mazes are walking slower wich would probably result in a longer solve time. Of course on the super long mazes the guests would be tired practically all the time.

[@mambodog5322]

Here's the thing with these huge numbers. The total time it would take is 8.1*10^2833 years. Even if guests walked a million times slower when tired, The new time would be 8.1*10^2839 years. It barely makes a dent.

[@DarkIzo]

6:28 please dont do that again, my brain is kinda fked cuz of that flipped park

[@hegyak]

If you are really curious what Build of OpenRCT2 added this change: f49bfa777a79277fbd37827cc7f054adfb3525e3 or v0.2.6-f49bfa7 That Commit has the Maze Change. Any Commit newer then that version, has the Maze change as well.

[@heartysquid]

Great video man, thanks for brightening my afternoon

[@JPK314]

5:21 the commenter is correct in that it's not actually a geometric series (it's definitely not linear though, I think they meant geometric or exponential), and the amount added per indentation only approaches a true geometric series (with each successive indentation multiplying the time required by a constant amount) in the limit. The intuition behind this is that you can only go a finite distance back to the start, and that distance changes depending on where you are in the maze. For more detail, see my comment on the previous impossible maze video

[@Ourlivelihoodband]

I strongly believe you will solve the meaning of the universe through RCT2.

[@lathanchurch8352]

I remember when I first played rct2, an old desktop and another game called blackbeard's revenge, but of all the games I've played over the years, rct2 have remained one of my absolute favorites, I still have the original disc somewhere but I don't remember where so I re-bought it on steam and your videos are making me want to re install it

[@sneckie]

I LOVE how quickly the OpenRCT2 team addressed this bug after you made the video.

[@Whatsuppbuddies]

“I don’t want to get off Maze 1 Maze 1 is my home”

[@Proxinem]

2:49 I love how it looks when all the guests want to leave the maze and are unhappily skulking around haha

[@ZeldagigafanMatthew]

Duncan's comment of "this is just to mess with Marcel Vos" has me in stitches.

[@Captaincrab77]

Always happy to support man!!

[@emre686]

This channel is so cool, keep up the great work. Amazing!

[@E-102_Gamma]

Now what happens if you make a maze with indents on *both* sides of the main path? Does it take the guests any longer to get through it?

[@retrorobbyreviews]

Makes me want to play OpenRCT2 and try this out for myself. Thats cool that the developers contacted you!!!!

[@TChapman500Gaming]

"I want to go on something more thrilling than Impossible Maze 1."

[@Naverb]

As at least one of the comments implicitly notes, we can get exact numbers here using Markov Chains; you don't need to guess about things being roughly linear or even do trials at all. A simple pathfinding algorithm like this is just modeled as a matrix, which encodes the possible states of the system and the probabilities to move between them. You obviously don't want to model every intersection as an entry to the matrix, so you instead model the states as "going toward exit", "going toward entrance", "coming out of left indent", etc... Basically exactly what you did in your first video. These account for all the possible states of the system, and you can then use theorems from probability theory to find the expected (aka average) time for certain things to happen, such as escaping the maze. You could also find the expected number of times to return to the start before escaping, easily calculate the correct formula for the multipliers you mention (which is, I imagine, nonlinear) and so forth. If you're interested in incorporating any of these techniques, I'd recommend looking up some of the stuff on Wikipedia. In this case any state can be reached from any other statein finite time with positive probability, so the Markov Chain is referred to as "Ergodic". Ergodic chains have pretty simple formulas for calculating these expected values, which should be a starting point for you.

[@lknapp235]

3:51 Statistically, you probably could/should have included the multipliers for mazes under 10 tiles when calculating the average, because the difference compared to the other lengths isn't mathematically significant enough (i.e. even though they're "quite a bit higher than the rest," they're not statistical outliers by definition). This would give you an average multiplier per tile of length of about 1.26, and a multiplier per indent of about 1.059. I realize that those numbers aren't too different from what you calculated, but I thought I'd share this anyways.

[@PsychoMuffinSDM]

For some reason, YT feed your video to me. I don't know why. I am not a huge fan of RCT (sure, I liked it back in the day), but for some reason I CANT STOP WATCHING! I don't know if it is the depth of content. Or the crazy parks in the background, but I gotta keep watching. Thanks for bringing back all these memories of RCT!

[@sagacious03]

Lol, what a fast update. Great video! Thanks for uploading!

[@Treajonker]

Wait a minute didn't you have like 5k subs last week nice growth more power to you

[@Tomasmoravia]

Hi Marcel, great videos, I've recently picked my old CD with this gem and with Open RCT it is great to play. I like your videos and would love to see one on the elevators or lifts for hills and valleys scenarios, keep up the great job you do.

[@FrankieSmileShow]

I wonder if the descending values of the multiplier for longer and longer mazes might not be because of a lower sample, but because when a guest turns back, the more indents are behind them, the more chances they have to turn back again and continue progress instead of reaching all the way back to the entrance again and starting from the beginning. That might have a slight attenuating factor to the increase of indents, every indent both adding a large chance to turn back, but also a small chance to turn back again, flattening the difficulty increase over larger numbers. If that is the case, the time estimate of the giant maze might be very inaccurate, because the increase for every indent could be smaller and smaller, though I would expect that the reduction in increase, itself, also flattens over large numbers. Like, by the 1000th tile, maybe the increase is closer to 1.12 or smth, and the numbers never quite reach lower than 1.10

[@unepanthere]

To test if there's a bias for either left or right, one would have to run many times the same maze, just to get an idea of the variance between the runs. Then, one could use the unpaired two-samples Student's t-test to determine if the means of two sets of data (the left-handed one and the right-handed one) are significantly different from each other...

[@GygasDistruttore]

Important question: how much time would it take for the guests to finish the unpatched Eternal Right indented maze? Can we finally walk a googleplex years for atom, or we are still far away?

[@MarcelVos]

100 hours or so.

[@GygasDistruttore]

@@MarcelVos thats an incredibly short time. Is it the shortest park wide ride, or you can do better? Probably yes, but you never know.

[@Dakakeisalie]

Wouldnt having indents on both sides of the path now be a huge drag on the solve time? When approaching each double indent, there is a 66% chance of going in an indent, then there is a 33% chance of crossing over to the indent on the far side.

[@thomastc2]

A drag, yes. A huge drag, I don't think so; just a constant factor (maybe 2). It doesn't matter much how often guests enter an indent, as long as coming out again they don't have a bias towards one or the other side of the main path. Every time they come back to the main path, it's a fair coin flip: X% towards the entrance and X% towards the exit, and (100 - 2*X)% of wasting some more time. This is true whether you have indents left, right, or both.

[@user-semenar]

@@thomastc2 The drag definitely would be huge; you can think of 'impossible mase' with the old algorithm as having 3 possible indents on each position.

[@want-diversecontent3887]

There's a programming puzzles and code golf challenge for this, and it turns out if you remove some of the dead ends near the enterance, it's more effective.

[@Thepuffingyank]

Wow Thats Amazing. Thank you Marcel

[@Twinrehz]

That image of the upside down park confused the shit out of me for a second xD

[@MNSweet]

I wonder what it would take to update the path finding to be more intelligent. Nothing crazy like a full completion algorithm (A*, Bi Directional, etc) but have it some form of line of sight 2-6 tiles in front of them to turn around if they see a dead end. I'm just a web developer (PHP/JS) so won't know were to start, let alone program in C++ or native assembly but as a player I know it would make maze making more fun.

[@wakaNL]

Just thinking about it right now and how would a double indented maze compare in diffuculty right compared to the single indented maze of the same total size (let's say 6x6). With the new way algorithm it feels like the double indent might make it longer since there are more options to spend time being useless by going back or staying in the same lane instead of either choosing to go forward or either waste time/go backwards.

[@thomasrinschler6783]

I wondered on the previous video - do handymen have the same pathing algorithm? It would explain why my handymen always seem to prefer certain areas in their zones and seem to ignore others. If those ignored areas were more "left biased", they might have just been less likely to path there.

[@itabiritomg]

There is a failsafe algorithm for solving any maze: keep your hand on the first right side wall and follow it forever. If the wall turns in any direction, then follow the wall even if it is a dead end. No matter how big the maze is, this will take you to the exit.

[@Point27Edited]

While this is good advice it is only true if both entrance and exit in connected through a wall, if you have a maze with "islands" of wall you might not be able to use this technic. You know, for when you inevitable end up stuck in a maze, as you do.

[@NHOrus]

If maze is single linked and doesn't have internal loops.

[@itabiritomg]

@@Point27Edited The only way you won´t find the exit on a maze with islands using this algorithm is if the exit is inside the island but this is impossible on a 2d maze.

[@itabiritomg]

@@NHOrus you cannot make a internal loop on a 2d maze with the loop starting on the first internal wall. it is impossible.

[@saurillian]

if you want to be a tad faster though you can see if the exit is on the left or right hand side of the entrance. if it's to the left, sticking to the left wall will statistically be faster

[@ry33412]

0:14 "if you have not seen that one yet, you'll not really understand this video" 1:14 *explains last video immediately after*

[@Kavukamari]

I wonder if it was done that way originally because it was easier or faster to do it that way because they were limited by assembly, these days we have a lot of shortcuts that they probably didn't want to write all out using just assembly code

[@kevindejong5069]

4:02 I don't think the mazes are too "small" for the randomness since they did have a lot of visitors. I think this is because the guests got tired after a while and start walking more slowly, making short mazes faster to solve than big ones.

[@iracingtf5051]

exactly!

[@zaodacrusher7498]

What'd happen if you put indents on both sides now? I wonder how the extra "rolls" for lack of a different term would affect completion time with the new 50/50 update.

[@h0b0b0z0]

2:55 i love how sad all the people in the maze are lol

[@acastilhon]

What would happen if instead of only left indents, the maze had right and left indent at the same lenght of maze? As I understood, at reaching an indent in the new algorithm, the guest would have a 33.3% of taking a left, 33.3% for right and 33.3% of going forward. What would mean less chance of taking the path to the exit (50% in current configuration). And when leaving the indent, the guest would have a 33.3% chance of going to the exit, 33.3% chance of going back and 33.3% chance of entering another indent. Also a smaller chance to go to the exit than current setup (50%). In th other hand, this new configuration would fit less indents, so it miight be a shorther path towards the exit.

[@TheSamuelMuller]

I've never actually played RollerCoaster Tycoon 2, original or otherwise, but your video's are super interesting!

[@TheAcrilon]

Hello Marcel, I have a question for you. i see that you do a lot of stuff for roller coaster tycoon 2 on this channel or rollercoaster tycoon stuff in general but not that much of specific stuff for rollercoaster tycoon 1. Is there any chance that you can make a Video about the hardest Scenarios in rollercoaster tycoon 1 or maybe big differences between the games (like the change of the looping coaster trains). i would love to see more content about that. also keep up the nice and interesting Videos about these games :)

[@Empiro3]

tcoren1 made a really good response but I think it's important because it actually changes the analysis a lot. Without a bias of going back toward the entrance, this is basically a random walk (look up 1d random walk), where you have a 50/50 chance of making or losing progress. The key is that in a random walk, to make n progress, you need n^2 number of steps, not exponential. For a large n, this makes a huge difference. 128,000 ^ 2 is still a huge number, so it will take a very long time (like age of the universe long), but not many heat-deaths of the universe long.

[@tijmen131]

I'm just binging your videos while traveling from Aachen to Bratislava by train

[@nickstonehenge]

i watched like two videos of this guy and now my entire youtube recommendations looks like a theme park

[@hindigente]

I wonder if there is an easy way to make the pathfinding algorithm even better. Maybe there is a way for guests to notice close dead ends.

[@Codraroll]

Anything like that would make it more memory intensive, I think. A possible cheap solution (but not sure how well it would work with the logic of the game) would be that the game computes and maps a path through the maze as soon as the ride is opened. I'm not sure how efficient maze-solving algorithms are, but they would only have to be applied once per maze. This "correct path" is stored with the maze and used to influence guest AI decisions, by not allowing them to walk any part of the path in reverse. They could branch off the path, take shortcuts or detours if any exist, or cross the path, but once they have turned around from a dead end (or merged back onto the main path after a detour) they wouldn't be able to follow it back towards the entrance.

[@Empiro3]

Yes, you'd need to keep track of where each guest has been, which would take up some memory, though on modern hardware it wouldn't be that much, all things considered. Still, it would assume that each guest has a string and chalk to mark their progress, which they wouldn't have. A good compromise might be to let the guest cheat whenever they do the "jumping up" animation. When they do that, allow them to take X number of steps toward the exit.

[@billy65bob]

I can think of a few easy solutions to "improve" their pathfinding for these mazes while keeping it cheap 1. Keep track of more than 1 of the guests' previous tiles, and bias them against revisiting 2. Bias guests to prefer visiting tiles with fewer other guests 3. Put a counter on every tile that increments every time a tile is visited by a guest; have guests prefer tiles that have been less travelled.

[@daskampffredchen]

Reminds me of Serious Sam getting an Update for its broken spawners after decino made a video on them

[@ctb3335]

Wait, did they really?!

[@Spacecoke]

You got me playing RCT again. Thanks :)

[@michaelzautner4848]

With the new update, would you be able to get a longer time doing a double indented maze on the large maze than single indents on one side or the other? It takes up more space, so you get less total indents, but you greatly reduce the chances of a guest advancing forward.

[@garlet69]

The algorithm can be modified to use the left or right hand always touching the wall strategy after the guest is inside the maze for a random amount of time

[@markhaus]

I LOVE that the merge request on the openRCT2 repo is explicitly to mess with Marcel

[@michaelmazarakis6796]

Pretty cool you had an impact on the development 👌🏻👌🏻

[@JoransGameKanaal]

I think it is a good update and can have effect, I was playng an ancient mytologie map (dont know the name xD) where was a allready a prebuild maze that you couldt sell and I think it was mosty left indented because they couldnt solve it and there were people stuck there for the entire duration of the map and they killed my park rating