5 ms·

Maze Design (2005)

156 points by amenghra 8y ago

amenghra 8y ago
a-maze-ing!
- notfed 8y ago
  It had to be said.
roland35 8y ago
I would love to plot some of these out with a pen plotter!
xamuel 8y ago
People who like this should also check out Robert Bosch's "TSP Art" (TSP stands for Travelling Salesman Problem). While this submission focuses on mazes, Bosch focuses on non-intersecting paths. The two problems are clearly dual, since a maze's solution is a non-intersecting path, and conversely every non-intersecting path is the solution to a corresponding maze. http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html
- qxi 8y ago
  OP's site is from 2005 and Bosch's site mentions the author of, and links back to, the submitted link ;)
  - xamuel 8y ago
    Oh, thanks, I explicitly tried to check but somehow missed that!
- adaml_623 8y ago
  Did you notice the dates on the page? The linked web page predates Bosch's work.
- onychomys 8y ago
  His don't really look like mazes, though. There's never any choice involved in the lines. In a maze, you're constantly needing to decide if you should go left or right. His art is just one single line without any branches, as far as I can tell (...and as you'd expect from a TSP algorithm!).
  - cr0sh 8y ago
    Did you miss this part of the post you're responding to (I am modifying it to make it hopefully clearer)? > The two problems are clearly dual > A: since a maze's solution is a non-intersecting path, and > B: conversely every non-intersecting path is the solution to a corresponding maze Focus on "B" - the output of a TSP algorithm "is the solution to a corresponding maze". IOW, the negative space of the TSP algorithms output is the maze itself...
    - deleted 8y ago
      [deleted]
    - onychomys 8y ago
      That post was edited after I responded to it.
- andjd 8y ago
  I went to Oberlin, where Bob is a professor. The pair of Campbells soup pictures were gallery framed on the wall of one of the classroom buildings
- deleted 8y ago
  [deleted]
- flashman 8y ago
  /u/rhiever also published some code on transforming an image into a travelling salesman path: http://www.randalolson.com/2018/04/11/traveling-salesman-portrait-in-python/ http://www.randalolson.com/2018/04/11/traveling-salesman-por...
agbell 8y ago
A great book about maze generation is "Mazes for programmers" http://www.mazesforprogrammers.com/ http://www.mazesforprogrammers.com/
- crdrost 8y ago
  Seconded. While this book has a lot of nice encouragements to simply coding and enjoying mazes, it also ships with two absolutely kick-ass appendices. The first is a very short bite-size summary of all of the algorithms that the book has covered, so that you don't have to read through the entire book again to remember the differences between the different algorithms. This is so good I wonder why it is not a standard feature of textbooks in general, such that it has its own standard section name (say "Abridgement"). The key is that it's longer-form than an introduction or abstract or conclusion, but the freedom to occupy its own space allows it to be expressed in human terms, unlike the "real research" parts which have to be a bit more rigorous. The second is a quantitative comparison of the different algorithms among different measurements, which again is like "why isn't this an appendix everywhere?" and such. It's still not trying to be absolutely rigorous but just to give a rough feel for the different options there. As a result you can just grab the textbook as a reference, flip through those appendices, say "yeah that's what I'm looking for, longer twistier paths," read up a quick description of how that algorithm works, say "well that's a bit more involved than this other one which looks good enough, maybe I'll start from there."
- neves 8y ago
  wow, US$32 for the kindle edition. It looks nice, but a bit too much for a toy book.
  - sanj 8y ago
    It is the most enjoyable prgramming book I’ve read in a decade. Well worth it.
  - AlexeyBrin 8y ago
    You can buy the ebook directly from the publisher for $25 https://pragprog.com/book/jbmaze/mazes-for-programmers https://pragprog.com/book/jbmaze/mazes-for-programmers . You get pdf and epub formats and no DRM.
warent 8y ago
I have to say I've never really found a maze that was challenging enough to take more than a minute or so to solve. Some of these mazes look much more difficult than anything I've seen before. Very cool and creative!
- cr0sh 8y ago
  > I have to say I've never really found a maze that was challenging enough to take more than a minute or so to solve. http://www.astrolog.org/labyrnth/maze/larger.gif http://www.astrolog.org/labyrnth/maze/larger.gif Enjoy! Note: This is from the "Think Labyrinth!" site mentioned on the Maze Design site: http://www.astrolog.org/labyrnth/maze.htm http://www.astrolog.org/labyrnth/maze.htm It is also not the "largest maze" on that page by far; there are a couple of larger ones (as zip'd files), and likely those aren't the largest today. I'm pretty certain they are just meant as "art" - and not to actually challenge someone to solve them; but if you are so inclined, go for it! EDIT: I just wanted to add a bit more about the "dense maze" - the start/end is at the upper-left/lower-right of the maze; the white line is the "path" of the maze (black being the walls). Note how the image "changes" depending on the level of "zoom" - if you fit it to a smaller size, the "white" of the image will take a "cross shape", while other areas are "darker" - zoom in on those various areas, and notice how the path changes; it's a very complex construct!
  - paragraft 8y ago
    In related news I just found a way to lock up mspaint using flood fill. 7 minutes and counting so far.
    - afterburner 8y ago
      This sounds way more fun than "playing" the maze...
    - paragraft 8y ago
      Update: nearly 3 hours now and still going. Feels like there might be a CPU benchmark here. Update final: After just over 4 hours it appears to have given up without actually filling anything.
ajkjk 8y ago
Seems like the connected-vortices mazes are easy to solve if you start by just figuring out the maze of vortex-connections first (which is very small), and then just checking each individual vortex. (Sometimes a vortex will have several paths which aren't actually connected internally, but that should come out in the second step.)
- crdrost 8y ago
  I think one would have to attack it the other way: focus on each vortex first, classify its connectivity. Since I think any path from East to West would break a path from North to South and vice versa, you'd have to classify each vortex by what it connects, down to one of: {., NE, NW, ES, SW, NS, EW, NE/SW, NW/SE, NES, NEW, NSW, ESW, NESW} In a more visual language you'd have 5x5 tiles which the bigger picture is made out of: \ / \ / \ / \ / \ / \ / \ / \ / | | ‾‾ X X X X | | / \ / \ / \ / | | __ / \ / \ / \ / / \ / \ \ / \ / \ / \ / \ / \ / \ / X X X X . \ / / \ / \ \ / / \ / \ Once you've figured out each individual vortex I think solving the bigger problem is probably doable?
wyldfire 8y ago
> The designer traces regions of interest in an image and annotates the regions with style parameters. They can optionally specify a solution path, which provides a rough guide for laying out the maze's actual solution. The system uses novel extensions to well-known maze construction algorithms to build mazes that approximate the tone of the source image, express the desired style in each region, and conform to the user's solution path. Sounds cool. Is there a public implementation?
- amenghra 8y ago
  One repo I found is https://github.com/G3Kappa/pictomaze https://github.com/G3Kappa/pictomaze. It requires installing processing and the python plugin. You can see the write up / output: https://medium.com/@G3Kappa/generating-mazes-from-pictures-or-masking-entropy-4d050d148539 https://medium.com/@G3Kappa/generating-mazes-from-pictures-o...
sandworm101 8y ago
Does anyone know of work on nth dimension mazes? Back in the 90s I had a great maze generator/game that generated mazes with over/underpasses between points. I've also played around in some physical 3d mazes made of lumber. Not just walls, but several layers of paths above and below each other like a big rubix cube (great drunken fun). So what would a 4/5/6d maze look like?
JKCalhoun 8y ago
Not a big maze fan (sorry) but reading the comments and following some of the links, I cannot help but give a shout out to the incredible "Maze" by Christopher Manson. Reminded me of the classic "Masquerade" by Kit Williams. (I hope everyone is familiar with both books.) https://www.goodreads.com/book/show/99048.Maze https://www.goodreads.com/book/show/99048.Maze
- sasaf5 8y ago
  Thank you for this link! Definitely gonna add this to my coffee table!

Maze Design (2005)

156 points by amenghra 8y ago

amenghra 8y ago

a-maze-ing!

notfed 8y ago
It had to be said.

roland35 8y ago

I would love to plot some of these out with a pen plotter!

xamuel 8y ago

People who like this should also check out Robert Bosch's "TSP Art" (TSP stands for Travelling Salesman Problem). While this submission focuses on mazes, Bosch focuses on non-intersecting paths. The two problems are clearly dual, since a maze's solution is a non-intersecting path, and conversely every non-intersecting path is the solution to a corresponding maze. http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html

qxi 8y ago
OP's site is from 2005 and Bosch's site mentions the author of, and links back to, the submitted link ;)
- xamuel 8y ago
  Oh, thanks, I explicitly tried to check but somehow missed that!
adaml_623 8y ago
Did you notice the dates on the page? The linked web page predates Bosch's work.
onychomys 8y ago
His don't really look like mazes, though. There's never any choice involved in the lines. In a maze, you're constantly needing to decide if you should go left or right. His art is just one single line without any branches, as far as I can tell (...and as you'd expect from a TSP algorithm!).
- cr0sh 8y ago
  Did you miss this part of the post you're responding to (I am modifying it to make it hopefully clearer)? > The two problems are clearly dual > A: since a maze's solution is a non-intersecting path, and > B: conversely every non-intersecting path is the solution to a corresponding maze Focus on "B" - the output of a TSP algorithm "is the solution to a corresponding maze". IOW, the negative space of the TSP algorithms output is the maze itself...
  - deleted 8y ago
    [deleted]
  - onychomys 8y ago
    That post was edited after I responded to it.
andjd 8y ago
I went to Oberlin, where Bob is a professor. The pair of Campbells soup pictures were gallery framed on the wall of one of the classroom buildings
deleted 8y ago
[deleted]
flashman 8y ago
/u/rhiever also published some code on transforming an image into a travelling salesman path: http://www.randalolson.com/2018/04/11/traveling-salesman-portrait-in-python/ http://www.randalolson.com/2018/04/11/traveling-salesman-por...

agbell 8y ago

A great book about maze generation is "Mazes for programmers" http://www.mazesforprogrammers.com/ http://www.mazesforprogrammers.com/

crdrost 8y ago
Seconded. While this book has a lot of nice encouragements to simply coding and enjoying mazes, it also ships with two absolutely kick-ass appendices. The first is a very short bite-size summary of all of the algorithms that the book has covered, so that you don't have to read through the entire book again to remember the differences between the different algorithms. This is so good I wonder why it is not a standard feature of textbooks in general, such that it has its own standard section name (say "Abridgement"). The key is that it's longer-form than an introduction or abstract or conclusion, but the freedom to occupy its own space allows it to be expressed in human terms, unlike the "real research" parts which have to be a bit more rigorous. The second is a quantitative comparison of the different algorithms among different measurements, which again is like "why isn't this an appendix everywhere?" and such. It's still not trying to be absolutely rigorous but just to give a rough feel for the different options there. As a result you can just grab the textbook as a reference, flip through those appendices, say "yeah that's what I'm looking for, longer twistier paths," read up a quick description of how that algorithm works, say "well that's a bit more involved than this other one which looks good enough, maybe I'll start from there."
neves 8y ago
wow, US$32 for the kindle edition. It looks nice, but a bit too much for a toy book.
- sanj 8y ago
  It is the most enjoyable prgramming book I’ve read in a decade. Well worth it.
- AlexeyBrin 8y ago
  You can buy the ebook directly from the publisher for $25 https://pragprog.com/book/jbmaze/mazes-for-programmers https://pragprog.com/book/jbmaze/mazes-for-programmers . You get pdf and epub formats and no DRM.

warent 8y ago

I have to say I've never really found a maze that was challenging enough to take more than a minute or so to solve. Some of these mazes look much more difficult than anything I've seen before. Very cool and creative!

cr0sh 8y ago
> I have to say I've never really found a maze that was challenging enough to take more than a minute or so to solve. http://www.astrolog.org/labyrnth/maze/larger.gif http://www.astrolog.org/labyrnth/maze/larger.gif Enjoy! Note: This is from the "Think Labyrinth!" site mentioned on the Maze Design site: http://www.astrolog.org/labyrnth/maze.htm http://www.astrolog.org/labyrnth/maze.htm It is also not the "largest maze" on that page by far; there are a couple of larger ones (as zip'd files), and likely those aren't the largest today. I'm pretty certain they are just meant as "art" - and not to actually challenge someone to solve them; but if you are so inclined, go for it! EDIT: I just wanted to add a bit more about the "dense maze" - the start/end is at the upper-left/lower-right of the maze; the white line is the "path" of the maze (black being the walls). Note how the image "changes" depending on the level of "zoom" - if you fit it to a smaller size, the "white" of the image will take a "cross shape", while other areas are "darker" - zoom in on those various areas, and notice how the path changes; it's a very complex construct!
- paragraft 8y ago
  In related news I just found a way to lock up mspaint using flood fill. 7 minutes and counting so far.
  - afterburner 8y ago
    This sounds way more fun than "playing" the maze...
  - paragraft 8y ago
    Update: nearly 3 hours now and still going. Feels like there might be a CPU benchmark here. Update final: After just over 4 hours it appears to have given up without actually filling anything.

ajkjk 8y ago

Seems like the connected-vortices mazes are easy to solve if you start by just figuring out the maze of vortex-connections first (which is very small), and then just checking each individual vortex. (Sometimes a vortex will have several paths which aren't actually connected internally, but that should come out in the second step.)

crdrost 8y ago
I think one would have to attack it the other way: focus on each vortex first, classify its connectivity. Since I think any path from East to West would break a path from North to South and vice versa, you'd have to classify each vortex by what it connects, down to one of: {., NE, NW, ES, SW, NS, EW, NE/SW, NW/SE, NES, NEW, NSW, ESW, NESW} In a more visual language you'd have 5x5 tiles which the bigger picture is made out of: \ / \ / \ / \ / \ / \ / \ / \ / | | ‾‾ X X X X | | / \ / \ / \ / | | __ / \ / \ / \ / / \ / \ \ / \ / \ / \ / \ / \ / \ / X X X X . \ / / \ / \ \ / / \ / \ Once you've figured out each individual vortex I think solving the bigger problem is probably doable?

wyldfire 8y ago

> The designer traces regions of interest in an image and annotates the regions with style parameters. They can optionally specify a solution path, which provides a rough guide for laying out the maze's actual solution. The system uses novel extensions to well-known maze construction algorithms to build mazes that approximate the tone of the source image, express the desired style in each region, and conform to the user's solution path. Sounds cool. Is there a public implementation?

amenghra 8y ago
One repo I found is https://github.com/G3Kappa/pictomaze https://github.com/G3Kappa/pictomaze. It requires installing processing and the python plugin. You can see the write up / output: https://medium.com/@G3Kappa/generating-mazes-from-pictures-or-masking-entropy-4d050d148539 https://medium.com/@G3Kappa/generating-mazes-from-pictures-o...

sandworm101 8y ago

Does anyone know of work on nth dimension mazes? Back in the 90s I had a great maze generator/game that generated mazes with over/underpasses between points. I've also played around in some physical 3d mazes made of lumber. Not just walls, but several layers of paths above and below each other like a big rubix cube (great drunken fun). So what would a 4/5/6d maze look like?

JKCalhoun 8y ago

Not a big maze fan (sorry) but reading the comments and following some of the links, I cannot help but give a shout out to the incredible "Maze" by Christopher Manson. Reminded me of the classic "Masquerade" by Kit Williams. (I hope everyone is familiar with both books.) https://www.goodreads.com/book/show/99048.Maze https://www.goodreads.com/book/show/99048.Maze

sasaf5 8y ago
Thank you for this link! Definitely gonna add this to my coffee table!