5 ms·

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 he

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-668259847 https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...

ben509 6y ago
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.
- kd5bjo 6y ago
  > 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.
  - OJFord 6y ago
    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 6y ago
      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.
      - kd5bjo 6y ago
        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.
        Munksgaard 6y ago
        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-668370640 https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...
        deleted 6y ago
        [deleted]
        viridian 6y ago
        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/ 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.
      - OJFord 6y ago
        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.
Causality1 6y ago
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.
- 9nGQluzmnq3M 6y ago
  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 6y ago
    My Minecraft cave process was "torches to the right on the way in" so it's easy to backtrack
- matsemann 6y ago
  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.
deleted 6y ago
[deleted]
liendolucas 6y ago
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 6y ago
That would make guests follow some very strict paths, which would be much less realistic and would severely hamper any regular gameplay.
hwc 6y ago
This is why I always design 3-dimensional mazes.

ben509 6y ago

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.

kd5bjo 6y ago
> 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.
- OJFord 6y ago
  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 6y ago
    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.
    - kd5bjo 6y ago
      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.
      - Munksgaard 6y ago
        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-668370640 https://github.com/OpenRCT2/OpenRCT2/pull/12546#issuecomment...
        deleted 6y ago
        [deleted]
      - viridian 6y ago
        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/ 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.
    - OJFord 6y ago
      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.

Causality1 6y ago

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.

9nGQluzmnq3M 6y ago
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 6y ago
  My Minecraft cave process was "torches to the right on the way in" so it's easy to backtrack
matsemann 6y ago
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.

deleted 6y ago

[deleted]

liendolucas 6y ago

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 6y ago

That would make guests follow some very strict paths, which would be much less realistic and would severely hamper any regular gameplay.

hwc 6y ago

This is why I always design 3-dimensional mazes.