Maze Design (2005)(cgl.uwaterloo.ca)
cgl.uwaterloo.ca
Maze Design (2005)
http://www.cgl.uwaterloo.ca/csk/projects/mazes/
34 comments
/u/rhiever also published some code on transforming an image into a travelling salesman path: http://www.randalolson.com/2018/04/11/traveling-salesman-por...
[deleted]
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
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!).
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...
> 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...
That post was edited after I responded to it.
[deleted]
Did you notice the dates on the page? The linked web page predates Bosch's work.
A great book about maze generation is "Mazes for programmers"
http://www.mazesforprogrammers.com/
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."
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."
wow, US$32 for the kindle edition. It looks nice, but a bit too much for a toy book.
You can buy the ebook directly from the publisher for $25 https://pragprog.com/book/jbmaze/mazes-for-programmers . You get pdf and epub formats and no DRM.
It is the most enjoyable prgramming book I’ve read in a decade.
Well worth it.
Well worth it.
> 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?
Sounds cool. Is there a public implementation?
One repo I found is 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-o...
You can see the write up / output: https://medium.com/@G3Kappa/generating-mazes-from-pictures-o...
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?
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?
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
(I hope everyone is familiar with both books.)
https://www.goodreads.com/book/show/99048.Maze
Thank you for this link! Definitely gonna add this to my coffee table!
I would love to plot some of these out with a pen plotter!
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.)
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}
\ / \ / \ / \ / \ /
\ / \ / \ / | | ‾‾
X X X X | |
/ \ / \ / \ / | | __
/ \ / \ / \ / / \ / \
\ / \ / \ /
\ / \ / \ /
\ / X X X X .
\ / / \ / \
\ / / \ / \
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!
> 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
Enjoy!
Note: This is from the "Think Labyrinth!" site mentioned on the Maze Design site:
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!
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
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!
In related news I just found a way to lock up mspaint using flood fill. 7 minutes and counting so far.
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.
Update final: After just over 4 hours it appears to have given up without actually filling anything.
This sounds way more fun than "playing" the maze...
http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html