News for hackers. Stuff that matters.
Re:A ride that takes 10^20k years to complete in Roller Coas... by mxwsn on Monday August 03, 2020 @04:47PM (#24043192)
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

Re:A ride that takes 10^20k years to complete in Roller Coas... by SwiftyBug on Monday August 03, 2020 @04:50PM (#24043236)
Re:A ride that takes 10^20k years to complete in Roller Coas... by 9nGQluzmnq3M on Monday August 03, 2020 @11:01PM (#24046100)
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".

https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...

Re:A ride that takes 10^20k years to complete in Roller Coas... by ben509 on Monday August 03, 2020 @11:43PM (#24046330)
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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by kd5bjo on Tuesday August 04, 2020 @02:30AM (#24047261)
> 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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by OJFord on Tuesday August 04, 2020 @03:07AM (#24047466)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by mcv on Tuesday August 04, 2020 @08:58AM (#24049455)
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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by kd5bjo on Tuesday August 04, 2020 @09:11AM (#24049580)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by viridian on Tuesday August 04, 2020 @11:04AM (#24050685)
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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by Munksgaard on Tuesday August 04, 2020 @10:18AM (#24050211)
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...
Re:A ride that takes 10^20k years to complete in Roller Coas... by OJFord on Tuesday August 04, 2020 @11:54AM (#24051177)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by peeters on Tuesday August 04, 2020 @10:29AM (#24050323)
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?
Re:A ride that takes 10^20k years to complete in Roller Coas... by OJFord on Tuesday August 04, 2020 @11:16AM (#24050793)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by peeters on Tuesday August 04, 2020 @02:21PM (#24052924)
Very true and thanks for clarifying.
Re:A ride that takes 10^20k years to complete in Roller Coas... by gpderetta on Tuesday August 04, 2020 @09:46AM (#24049875)
there is exactly an example of that in the github comment thread.
Re:A ride that takes 10^20k years to complete in Roller Coas... by liendolucas on Tuesday August 04, 2020 @12:46AM (#24046694)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by tapland on Tuesday August 04, 2020 @03:13AM (#24047498)
That would make guests follow some very strict paths, which would be much less realistic and would severely hamper any regular gameplay.
Re:A ride that takes 10^20k years to complete in Roller Coas... by Causality1 on Monday August 03, 2020 @11:47PM (#24046356)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by matsemann on Tuesday August 04, 2020 @04:47AM (#24047959)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by 9nGQluzmnq3M on Monday August 03, 2020 @11:58PM (#24046421)
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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by c17r on Tuesday August 04, 2020 @03:10PM (#24053414)
My Minecraft cave process was "torches to the right on the way in" so it's easy to backtrack
Re:A ride that takes 10^20k years to complete in Roller Coas... by hwc on Wednesday August 05, 2020 @12:36PM (#24062713)
This is why I always design 3-dimensional mazes.
Re:A ride that takes 10^20k years to complete in Roller Coas... by infogulch on Monday August 03, 2020 @05:18PM (#24043585)
It's always so wholesome when devs interact positively with 'exploit hunter' types. I wonder why it feels like that.
Re:A ride that takes 10^20k years to complete in Roller Coas... by spanhandler on Monday August 03, 2020 @10:41PM (#24045989)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by infogulch on Tuesday August 04, 2020 @12:48AM (#24046699)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by fsniper on Tuesday August 04, 2020 @03:20AM (#24047533)
Maybe because "exploit hunter" types are in fact doing QA for the developer?
Re:A ride that takes 10^20k years to complete in Roller Coas... by jansan on Monday August 03, 2020 @05:05PM (#24043414)
It actually is funny.
Re:A ride that takes 10^20k years to complete in Roller Coas... by SwiftyBug on Tuesday August 04, 2020 @08:02AM (#24049083)
Indeed!
Re:A ride that takes 10^20k years to complete in Roller Coas... by fossuser on Monday August 03, 2020 @05:29PM (#24043682)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by MauranKilom on Monday August 03, 2020 @06:03PM (#24043994)
According to Youtube recommending a newer video by the same author, you can still build impossible mazes:

https://www.youtube.com/watch?v=b-5aX2oLOgU

Re:A ride that takes 10^20k years to complete in Roller Coas... by nightcracker on Monday August 03, 2020 @10:33PM (#24045938)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by Taek on Monday August 03, 2020 @06:38PM (#24044321)
For a proper fix they would probably want the guest to remember places they had been previously and bias against those places.
Re:A ride that takes 10^20k years to complete in Roller Coas... by aasasd on Monday August 03, 2020 @08:59PM (#24045382)
Real-life mazes are sorta known for not working like that: https://youtu.be/u9xvrbfyKGQ?t=425
Re:A ride that takes 10^20k years to complete in Roller Coas... by int_19h on Monday August 03, 2020 @09:23PM (#24045518)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by egypturnash on Monday August 03, 2020 @08:49PM (#24045319)
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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by bscphil on Monday August 03, 2020 @11:36PM (#24046295)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by Taek on Tuesday August 04, 2020 @01:33AM (#24046965)
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 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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by bscphil on Tuesday August 04, 2020 @01:53AM (#24047058)
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 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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by atq2119 on Monday August 03, 2020 @05:21PM (#24043610)
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.
Re:A ride that takes 10^20k years to complete in Roller Coas... by Wowfunhappy on Tuesday August 04, 2020 @12:09AM (#24046480)
Oh, I didn't realize this was OpenRCT2, rather than the original RCT2. Do we know if the original game has this same oddity?
Re:A ride that takes 10^20k years to complete in Roller Coas... by laumars on Tuesday August 04, 2020 @12:23PM (#24051479)
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.

Re:A ride that takes 10^20k years to complete in Roller Coas... by simcop2387 on Tuesday August 04, 2020 @01:11AM (#24046856)
According to the next video from the youtuber, ye sit does.
Re:A ride that takes 10^20k years to complete in Roller Coas... by foota on Monday August 03, 2020 @05:51PM (#24043879)
It would be interesting maybe to design a system where people deviate a random amount from the optimal path.