40
\$\begingroup\$

RollerCoaster Tycoon 2's maze is the inspiration for this question. Credit to Marcel Vos for thoroughly breaking the classic RCT2 AI. The pathfinding AI in this question is the AI in the latest version of OpenRCT2 at the time of writing, which was updated in response to that video.

image of RCT2 maze


Suppose a guest enters a \$w \times h\$ grid maze with the following strategy in mind:

After every step I pick a random valid direction except backwards, unless I have no other choice but to go back.

We are evil and wish to construct the maze that takes the most amount of time on average to solve using the above strategy.


This is a code-challenge. The winner is the answer that contains a \$100 \times 100\$ maze with the greatest mean solve time using the above strategy. In the case of a tie the earlier poster wins.

A \$w \times h\$ maze is a \$w \times h\$ grid of square tiles. It has two designated start tiles along the border, connected either horizontally or vertically, and similarly two designated exit squares, along the border, connected either horizontally or vertically. Between each tile there may or may not be a wall (with the exception of the two start and two end tiles, they must be directly connected to their partner). There is always a border of walls around the grid.

The guest enters with a 50/50% chance on either start tile, facing away from the other tile. Then the guest starts exploring the maze one step at a time. At the start of a step the guest looks to its left, forward and right (relative to its current direction) and checks for walls. It chooses a random new direction with uniform chance from the unobstructed directions. If and only if all other directions are obstructed it chooses to go backwards instead.

The guest wanders around as such until it reaches one of the two exit squares, which will cause the guest to immediately exit. The average number of steps it takes for this to happen is your score, the bigger the better. If the start and exit are not connected your maze is invalid and has no score.


To accurately score mazes I wrote a judge program in Python that uses Markov chains to compute your score mathematically. It requires Python 3, numpy, scipy and imageio to run (an optional dependency for a speedup is scikit-umfpack). In addition, the judge contains functions to output an image of your maze, as well as a compressed representation of your maze. Please familiarize yourself with the judge program before starting this challenge.

Please include (a link to) a \$100\times 100\$ compressed maze as generated by the judge program in your answer. Your answer will be scored based on this. An answer without a concrete, specific solution maze is invalid.

\$\endgroup\$
  • \$\begingroup\$ I think that the time can never be exponential in the graph size? (I can't prove this, but I can't find any exponential solution either) \$\endgroup\$ – user202729 Aug 6 at 13:54
  • \$\begingroup\$ Are you sure the start and end tiles are drawn correctly? I have line maze.set_exit(0, maze.height-1, 0, maze.height-2) which calculates correctly apparently but draws with axes flipped? \$\endgroup\$ – qwr Aug 6 at 20:38
  • \$\begingroup\$ Note that pillow images are usually row-major order, meaning indexing is done img[y,x]. \$\endgroup\$ – qwr Aug 6 at 21:11
  • \$\begingroup\$ The mazes could be made really evil with one-way gates. \$\endgroup\$ – qwr Aug 7 at 2:00
  • \$\begingroup\$ @qwr Fixed. Would you mind updating your answers with the latest version? \$\endgroup\$ – orlp Aug 7 at 2:30
11
\$\begingroup\$

No dead ends near the entrance, 21,477,560 21,485,005

Try it online!

Yay, 21 million. The giant horizontal segments up to row 19 are also removed, so about 20% of the entire grid is just an open space.

Also, as the "real maze" starts at the leftmost column, moving the entrance to the top right gives a slight bump to the score. (Thanks to @Neil)

enter image description here


Previous version, 20,211,703

Try it online!

Yes, 20 million. It's actually good to remove some dead ends and add some open spaces near the entrance, but it stops being good as it gets sufficiently far away from it.

This is a derivation from width-3 dead end maze by removing some h-walls (it's called h-walls in the code, but it is a vertical segment in the image):

  • The h-walls from row 1 to row 22 (inclusive) are entirely removed.
  • The h-walls from row 23 to row 40 (inclusive) are reduced by half, keeping the odd indices.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Moving the start to 99, 0, 99, 1 bumps your score up a bit more. \$\endgroup\$ – Neil Aug 7 at 9:06
11
\$\begingroup\$

Tridents, score 21,947,177 21,951,598

UEsDBBQAAAAIAAAAIQAL/+yrSgAAAIgAAAAJABQAYXJyXzAubnB5AQAQAIgAAAAAAAAASgAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mirqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYGBhAGAFBLAwQUAAAACAAAACEAlmPInE8AAACQAAAACQAUAGFycl8xLm5weQEAEACQAAAAAAAAAE8AAAAAAAAAm+wX6hsQychQxlCtnpJanFykbqWgbpNpoq6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjoKRpo6CrUKZAOuZAYGhiQgToZiAFBLAwQUAAAACAAAACEAX1d180sAAACQAAAACQAUAGFycl8yLm5weQEAEACQAAAAAAAAAEsAAAAAAAAAm+wX6hsQychQxlCtnpJanFykbqWgbpNpoq6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjoKRpo6CrUKZAMuBihghNIAUEsDBBQAAAAIAAAAIQCi1p2qngAAACwnAAAJABQAYXJyXzMubnB5AQAQACwnAAAAAAAAngAAAAAAAADt2jEKAkEMheFM6ynSRWGK3XI9gJ1iY2EloztiIa7MLDbqKbywuydYcLD7QwjkEfgukM9mt97unTzkaW3Mp2RLtdexNq927lKfwu3QpTaO+SpccxzyfAn3OOzzpvFaV9XC61t/q5mIcyJlc6rceFfUGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGBgYGP8zpPCVbNr4AlBLAwQUAAAACAAAACEAXL51PqgAAAAsJwAACQAUAGFycl80Lm5weQEAEAAsJwAAAAAAAKgAAAAAAAAA7dohDgIxEIXhqeUUdQNJxa5cDoCDYBAoUtgSBGFJSzDAKbgwW4GFDTWI/7V5Scd8re9zsZov10auctM2pF3UqdX7tlZndd/FS/SnTRfbkOczf0yhn6eDP4f+PK6rytmmmTj7sL9lJGIkp6S/xORlSnoQUrohICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICD+kij7f2UGvULeNynpT3kBUEsBAhQAFAAAAAgAAAAhAAv/7KtKAAAAiAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUABQAAAAIAAAAIQCWY8icTwAAAJAAAAAJAAAAAAAAAAAAAACAAYUAAABhcnJfMS5ucHlQSwECFAAUAAAACAAAACEAX1d180sAAACQAAAACQAAAAAAAAAAAAAAgAEPAQAAYXJyXzIubnB5UEsBAhQAFAAAAAgAAAAhAKLWnaqeAAAALCcAAAkAAAAAAAAAAAAAAIABlQEAAGFycl8zLm5weVBLAQIUABQAAAAIAAAAIQBcvnU+qAAAACwnAAAJAAAAAAAAAAAAAACAAW4CAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAAUQMAAAAA

Based on @Bubbler's answer, but some tinkering about with a wall finding algorithm led me to tweak the layout slightly:

Tridents

Edit: Slightly improved my score by changing the exit orientation, which allowed me to use the trident shape there too. For some reason (I'm not ruling out human error) not only did @isaacg's "tricky routing" not affect the score for this layout but also my "trident exit" doesn't seem to affect the score for his layout...

I actually wrote a script where I could parametrise the number of long horizontal lines, how many of them had teeth, how many of them had gappy teeth, and how many of the ends had prongs, and this was the best I could come up with (also my wall finder couldn't find a way of improving it). Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "Note that due to a display issue the start and exit display horizontally but they are actually both vertical." I've fixed this bug already, please download the latest version of the judge :) \$\endgroup\$ – orlp Aug 8 at 0:10
  • \$\begingroup\$ @orlp I'm not sure how much difference it makes to my wall finder, but I think I'll stick to unrounded scores for its algorithm for now. \$\endgroup\$ – Neil Aug 8 at 16:33
  • \$\begingroup\$ Turning that sideways looks about as good as the nonsense I had at the end. \$\endgroup\$ – isaacg Aug 15 at 16:03
  • \$\begingroup\$ @isaacg Indeed, I had already tried the extra side version, and the score came out equal to yours to with an accuracy of <1e-10. \$\endgroup\$ – Neil Aug 15 at 16:11
9
\$\begingroup\$

Two sides of mazes, score 21987725

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJBqs1pOAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkA65kBghAp5OgNABQSwMEFAAAAAgAAAAhAEghScnMAAAALCcAAAkAAABhcnJfMy5ucHnt2jEOgjAUgOF29RTdqgkDjHgAN42Lg5NBqXEwaopxUU/hhQVP8F4xhOF/IS+hy5eSf+Sz2izXW2se5unr0Byinzv/2hc+c/54jfdYXXbXWIfufFGdm9CeN6fqFtr3aVlmrsjzWebeLm0mJnnsb0l2H8MKHwwMDAwMDAwMDAwMDAwMDAwMDAwMjP8byTPAPVRGH0Vs9PhaY7pHukBXGoWupAJdaRS6kgp0pVHoSirQlUahK6lAVxqFrqQCXWmUsXRlBrhHt5IF8U9k9gtQSwMEFAAAAAgAAAAhACNNXj3ZAAAALCcAAAkAAABhcnJfNC5ucHnt2rEKwjAUheFk9SmyRaFDO9YHcFNcHJyk2oiDWEnFRX0KX9g6uGq5gXKRP4RAu3w9J3fsc7GaL9fWXM3N16HdRT91/r4tfOb8vomXWJ02TazD+/2sOrahe98eqnPonsdFnmeuLCeZezjZGhnpsr3PBMJa2+tMIPpuCAgICAgICAgICAgICAgICAgICAiIb1u4dKUQx9BF/MV1D0AwUXqKEmdQRTBReooSZ1BFMFF6ihJnUEUwUXqKEmdQRTBReooSZ1BF/MNEJTQ1RFH9/r9KuW7z+cIfpzUvUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAXAAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEAkGqzWk4AAACgAAAACQAAAAAAAAAAAAAAgAHjAAAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhAEghScnMAAAALCcAAAkAAAAAAAAAAAAAAIABWAEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAjTV492QAAACwnAAAJAAAAAAAAAAAAAACAAUsCAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAASwMAAAAA

Based on @Neil's trident design, but I added an extra side of mazes, and also did some tricky routing right at the end to improve the score a bit more.

Two sides maze

It turned out to be optimal to have the blank region be a perfect square, which I didn't expect, due to the asymmetry of the maze region. The blank region is 58x58, and there are 14 rows of maze on each side.

I really wanted to get to 22 million, but I had to stop just short. I tried lots of designs that didn't improve anything, like making the blank region nonrectangular, or making the design symmetrical across the main axis. None of that helped.

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The symmetry doesn't affect the score much. The board can be considered as an undirected graph (with each cell a node and two cells have an edge iff they're adjacent and not separated with a wall), and two boards with the same graph has the same score. \$\endgroup\$ – user202729 Aug 10 at 2:32
  • \$\begingroup\$ I double-checked and you can also alternate each pair of paths between horizontal and vertical (which is visually slightly more pleasing) for the same score. \$\endgroup\$ – Neil Aug 13 at 9:27
  • 1
    \$\begingroup\$ I just noticed that the area of our blank regions is similar (mine is 3400 and yours is 3364). \$\endgroup\$ – Neil Aug 13 at 9:30
  • \$\begingroup\$ The "tricky routing" makes a whole world of difference; with my original routing the score is only 21983310 and I can beat that using a row of 2-way branches and 11 rows of 3-way branches, then 16 rows of 3-way branches in the opposite axis, scoring 21985758. \$\endgroup\$ – Neil Aug 14 at 10:25
  • \$\begingroup\$ I also tried extending the "tricky routing" along the length of the row, but it turns out that this makes no difference to the score at all. \$\endgroup\$ – Neil Aug 14 at 10:57
8
\$\begingroup\$

Even more dead ends, 16,555,009.5

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJABQAYXJyXzAubnB5AQAQAJAAAAAAAAAASQAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYIgNEAUEsDBBQAAAAIAAAAIQCcpkBwTAAAAKAAAAAJABQAYXJyXzEubnB5AQAQAKAAAAAAAAAATAAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GNMCIxgcAUEsDBBQAAAAIAAAAIQAsPfLMTwAAAKAAAAAJABQAYXJyXzIubnB5AQAQAKAAAAAAAAAATwAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhmQAVJUBoAUEsDBBQAAAAIAAAAIQAYEnl9jgAAACwnAAAJABQAYXJyXzMubnB5AQAQACwnAAAAAAAAjgAAAAAAAADtzbENwjAUhGG7ZYrXPZBcxGUYIB0oDUUqZIgRRUSQHaUBpsjCmBWQqPhP19w137I/7NrOmtk8tI/5nHQr+jx5daKXMU0p3I5j6uPnb8KQY/nzNdxj2eu6duKrauPkJd9lZaz9eTEwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDD+23gDUEsDBBQAAAAIAAAAIQBg04Z/fgAAACwnAAAJABQAYXJyXzQubnB5AQAQACwnAAAAAAAAfgAAAAAAAADt2jEKwkAQheFJ6ymmG4UtkjIewE6xsbAKG7NiIUZ2g43JKbxwkisEAhb/42PgvTPM73Q5nq+ZfORrTUi3aHu1vi7Mqd3b2EX/qtrYhHk/+GcK054e/h2mvi3y3GlZ7pwOuiwbyWTOqhcAAAAAAAAAAAAAAAAA8M/W/iITGQFQSwECFAMUAAAACAAAACEAoQWAvEkAAACQAAAACQAAAAAAAAAAAAAAgAEAAAAAYXJyXzAubnB5UEsBAhQDFAAAAAgAAAAhAJymQHBMAAAAoAAAAAkAAAAAAAAAAAAAAIABhAAAAGFycl8xLm5weVBLAQIUAxQAAAAIAAAAIQAsPfLMTwAAAKAAAAAJAAAAAAAAAAAAAACAAQsBAABhcnJfMi5ucHlQSwECFAMUAAAACAAAACEAGBJ5fY4AAAAsJwAACQAAAAAAAAAAAAAAgAGVAQAAYXJyXzMubnB5UEsBAhQDFAAAAAgAAAAhAGDThn9+AAAALCcAAAkAAAAAAAAAAAAAAIABXgIAAGFycl80Lm5weVBLBQYAAAAABQAFABMBAAAXAwAAAAA=

The guests now have 3 choices per intersection for most intersections, however there are only about 2/3 as many intersections. Of 34 corridors, the first and last corridors have 98 two-way branches, and 32 corridors have 2 two-way branches and 98 three-way branches. (I didn't count carefully)

enter image description here

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ As a hint towards further progress, believe it or not but this outscores your answer by around 2%. \$\endgroup\$ – orlp Aug 7 at 4:53
5
\$\begingroup\$

Empty maze, score 51113

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJBqs1pOAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkA65kBghAp5OgNABQSwMEFAAAAAgAAAAhAPN9K5lvAAAALCcAAAkAAABhcnJfMy5ucHntyDEOgkAUANGl5RS/+5JsASUewE5CY0FFVlliYYTsEhr1FFwYuIIJ3bxuZqlu17pJzGw+2vn4CHoW/d4LtaL9EKbg3u0QOr//i3tFv/34dKPf+lSWVoo8z6z85D+pAQAAAAAAAAAAAAAAAADgYCtQSwMEFAAAAAgAAAAhACFK7HxvAAAALCcAAAkAAABhcnJfNC5ucHntyDEOgkAUANGl5RS/+5JsASUewE5CY0FFVlliYYTsEhr1FFwYuIIJ3bxuZqlu17pJzGw+2vn4CHoW/d4LtaL9EKbg3u0QOr//i3tFv/34dKPf+lTkuZWyzKz85D+pAQAAAAAAAAAAAAAAAADgYCtQSwECFAMUAAAACAAAACEAoQWAvEkAAACQAAAACQAAAAAAAAAAAAAAgAEAAAAAYXJyXzAubnB5UEsBAhQDFAAAAAgAAAAhAJM3ghJMAAAAoAAAAAkAAAAAAAAAAAAAAIABcAAAAGFycl8xLm5weVBLAQIUAxQAAAAIAAAAIQCQarNaTgAAAKAAAAAJAAAAAAAAAAAAAACAAeMAAABhcnJfMi5ucHlQSwECFAMUAAAACAAAACEA830rmW8AAAAsJwAACQAAAAAAAAAAAAAAgAFYAQAAYXJyXzMubnB5UEsBAhQDFAAAAAgAAAAhACFK7HxvAAAALCcAAAkAAAAAAAAAAAAAAIAB7gEAAGFycl80Lm5weVBLBQYAAAAABQAFABMBAACEAgAAAAA=

Try it online! Just to get the ball rolling.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Zigzag path, score 12,582,074

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJVYfYFPAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhiQAXJUBoAUEsDBBQAAAAIAAAAIQDzfSuZbwAAACwnAAAJAAAAYXJyXzMubnB57cgxDoJAFADRpeUUv/uSbAElHsBOQmNBRVZZYmGE7BIa9RRcGLiCCd28bmapbte6ScxsPtr5+Ah6Fv3eC7Wi/RCm4N7tEDq//4t7Rb/9+HSj3/pUllaKPM+s/OQ/qQEAAAAAAAAAAAAAAAAA4GArUEsDBBQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAYXJyXzQubnB57doxDsIwDIVhZ+UU3gxShnYsB2ADsTAwobQNYkAUJYgFegouTHuFStl+Wx7eW74L+Hc47Y9nJ2/5WB9zl2yr9m1r82rXIb1SeFyG1Me534V7jlOfb+EZp7yuq8pr02y8jrpsVuJESp8rvhAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBDLieJvZPIHUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAXAAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEAlVh9gU8AAACgAAAACQAAAAAAAAAAAAAAgAHjAAAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhAPN9K5lvAAAALCcAAAkAAAAAAAAAAAAAAIABWQEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAAAAAAAAAAACAAe8BAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAArAIAAAAA

Try it online! Creates a giant zigzag, something like this but larger:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| S                                                             |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| S                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|                                                               |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
| E                                                             |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| E                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Slightly fewer dead ends, score 16,663,349

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJAAAAYXJyXzAubnB5m+wX6hsQychQxlCtnpJanFykbqWgbpNpoa6joJ6WX1RSlJgXn1+UkgoSd0vMKU4FihdnJBakAvkaRjqaOgq1ChQArhQGCIDRAFBLAwQUAAAACAAAACEAkzeCEkwAAACgAAAACQAAAGFycl8xLm5weZvsF+obEMnIUMZQrZ6SWpxcpG6loG6TaaGuo6Cell9UUpSYF59flJIKEndLzClOBYoXZyQWpAL5GkY6CkaaOgq1CmQDLgYcgBFKAwBQSwMEFAAAAAgAAAAhAJVYfYFPAAAAoAAAAAkAAABhcnJfMi5ucHmb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhiQAXJUBoAUEsDBBQAAAAIAAAAIQAhaJ1vdQAAACwnAAAJAAAAYXJyXzMubnB57cgxDoJAFEXRoXUVv/uaTAElLsBOY0NBRQYZY2HEzBgaYBVsGNgCBbG491TvTbfiei8T05leGx8fQc+iQ52pFX224Rfcp2pD49f/4t7RL398ua9f9jHPrWRperIyyrYOZocSAAAAAAAAAAAAAAAAAMDf2qMZUEsDBBQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAYXJyXzQubnB57doxDsIwDIVhZ+UU3gxShnYsB2ADsTAwobQNYkAUJYgFegouTHuFStl+Wx7eW74L+Hc47Y9nJ2/5WB9zl2yr9m1r82rXIb1SeFyG1Me534V7jlOfb+EZp7yuq8pr02y8jrpsVuJESp8rvhAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBDLieJvZPIHUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAXAAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEAlVh9gU8AAACgAAAACQAAAAAAAAAAAAAAgAHjAAAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhACFonW91AAAALCcAAAkAAAAAAAAAAAAAAIABWQEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAAAAAAAAAAACAAfUBAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAAsgIAAAAA

Try it online! Based on the original dead end guest trap as posted by @qwr, but removing some of the dead ends like this manages to increase the score:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| S     |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| S                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|       |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
|                                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+   +
| E     |   |   |   |   |   |   |   |   |   |   |   |   |       |
+   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +   +
| E                                                             |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

The original dead end guest trap, 16,505,047.166666668

UEsDBBQAAAAIAAAAIQChBYC8SQAAAJAAAAAJABQAYXJyXzAubnB5AQAQAJAAAAAAAAAASQAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOpo6CrUKFACuFAYIgNEAUEsDBBQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJABQAYXJyXzEubnB5AQAQAKAAAAAAAAAATAAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GHIARSgMAUEsDBBQAAAAIAAAAIQAsPfLMTwAAAKAAAAAJABQAYXJyXzIubnB5AQAQAKAAAAAAAAAATwAAAAAAAACb7BfqGxDJyFDGUK2eklqcXKRupaBuk2mhrqOgnpZfVFKUmBefX5SSChJ3S8wpTgWKF2ckFqQC+RpGOgpGmjoKtQpkAy4GKEhmQAVJUBoAUEsDBBQAAAAIAAAAIQCiugFzcQAAACwnAAAJABQAYXJyXzMubnB5AQAQACwnAAAAAAAAcQAAAAAAAADtyDEOgkAURdGhdRW/+5hMASUugA5jY2FlRhlDQcDMEBphFWwY3AIJ3X2nene53qvbIzGj+Wnt4zvoRXR65WpFP30Yguuefaj9v5eujX7rsXFfv/20KKzkWXa2Msu+nUwCAAAAAAAAAAAAAAAAAMCxVlBLAwQUAAAACAAAACEAKLPia5YAAAAsJwAACQAUAGFycl80Lm5weQEAEAAsJwAAAAAAAJYAAAAAAAAA7doxDsIwDIVhZ+UU3gxShnYsB2ADsTAwobQNYkAUJYgFegouTHuFStl+Wx7eW74L+Hc47Y9nJ2/5WB9zl2yr9m1r82rXIb1SeFyG1Me534V7jlOfb+EZp7yuq8pr02y8jrpsVuJESp8rvhAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBDLieJvZPIHUEsBAhQDFAAAAAgAAAAhAKEFgLxJAAAAkAAAAAkAAAAAAAAAAAAAAIABAAAAAGFycl8wLm5weVBLAQIUAxQAAAAIAAAAIQCTN4ISTAAAAKAAAAAJAAAAAAAAAAAAAACAAYQAAABhcnJfMS5ucHlQSwECFAMUAAAACAAAACEALD3yzE8AAACgAAAACQAAAAAAAAAAAAAAgAELAQAAYXJyXzIubnB5UEsBAhQDFAAAAAgAAAAhAKK6AXNxAAAALCcAAAkAAAAAAAAAAAAAAIABlQEAAGFycl8zLm5weVBLAQIUAxQAAAAIAAAAIQAos+JrlgAAACwnAAAJAAAAAAAAAAAAAACAAUECAABhcnJfNC5ucHlQSwUGAAAAAAUABQATAQAAEgMAAAAA

The original design in Marcel Vos's video. 50 corridors, each with 99 intersections, gives 4950 two-way branches (maybe off by one or two) for guests to choose between.

dead end maze

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.