Algorithms for making more interesting mazes 232 points by rinesh on Oct 10, 2016 | hide | past | web | favorite | 30 comments

 Another interesting aspect of the grid coloring approach is that one can pre-bake larger rooms within a maze, which is useful when adding a maze to a different style game, such as a first-person shooter or an RPG. Other features, which aren't provided by the standard Prim's Algorithm, such as 2.5D mazes (bridges and tunnels), or having more than one path to a given room, can be added after maze generation has been completed. A bridge, for instance, can be added by connecting two locations and adding a wall to block off one of the locations from the algorithmically defined path, if maze continuity is desired.I played with using mazes as a way to find things that are quickly solved by machines but take some concentration from users, as a sort of anti-CAPTCHA test. Obviously, there are thousands of such potential tests, but mazes have an aesthetic appeal lacking, in say, "find the prime factors of this 128 bit number." A child can brute force a maze, as can any adult, given enough time. A machine breezes right through large mazes that could take hours for a human to solve by hand. When would such a test be useful? I'll leave that to the imagination of the reader.
 > A machine breezes right through large mazes that could take hours for a human to solve by hand. When would such a test be useful? I'll leave that to the imagination of the reader.You could imagine androids using that as a sort of reverse-CAPTCHA to distinguish people from machines and preventing the latter from entering their secret gathering place.Which brings me to the last episode of Westworld... Boy, I have a theory about the Maze for you...
 Hmmmm. Sounds like a way of filtering out the non-determined, non-intelligent, and/or non-moneyed from a vast sea of candidates. So I would guess you were hiring junior game developer fresh out of college for a coveted opening?
 Nothing that extreme. This was more of a theoretical thing. Certainly, it could be used to filter people based on their ability to design a maze-solving heuristic, but some constraints would have to be placed on the test, as one can query Google for an A* implementation that could pretty easily solve this without having to understand basic recursive searches.If I were to design this as an interview problem, it would probably be for a general purpose solver and a pair programming exercise.
 Fun article! One thing I've found is that no matter how you tweak them, mazes are rarely fun for players. They are too dense and crowded for a game, and they don't have open space where interesting combat can occur.They can be a good tool in your toolbox when generating levels, though, if you combine them with others. I wrote a post about one approach a while back:
 Yeah, I tend to agree. Pure mazes are great for Pacman and the like but perhaps not much else (and, of course, Bomberman): as you say, just too dense to be very playable.Even this is debatable because in many variants, destructible walls aside, the layout is substantially similar between levels.
 That's an awesome post, by the way, so thanks for sharing - definitely going to crib some ideas from it.
 I love maze algorithms. The visualisations by https://bl.ocks.org/mbostock/11357811 are great for understanding the basic algorithm, and I like the twists in the article.Never sure how much promotional content should be on here, but the company I work for (Redgate) has a coding challenge related to this. See http://www.red-gate.com/our-company/entrypage/coding-challen... if you are interested.
 I like Mike Bostock's demos of maze-generation algorithms: https://bost.ocks.org/mike/algorithms/#maze-generation
 Fun! I want to enter, but I'm not sure I have the time. :(Nothing at all wrong with posting that, btw. You might consider posting it to the front page if you haven't already.
 http://www.jamisbuck.org/mazes/ was a good resource when I was looking into maze algorithms.He had (has?) a lot of interesting blog posts on mazes as well.
 http://weblog.jamisbuck.org/or if you click on the name of the algorithm in the url you posted it brings you to the blog post about it.
 The grid colorings approach is very cool! I don't think I've seen that one before, I bet you can somehow take that idea even further. You could also get similar effects by creating a regular uncolored (axis-aligned) grid maze and then rotate and re-rasterize it into another grid. But the grid coloring approach looks like it handles the boundary automatically.One of these years I'll write it up, but I've played a lot with no-grid mazes, and once you get away from the 2d array, it opens up a lot of interesting possibilities. Prim's algorithm works equally well on a mesh where vertices have an arbitrary number of edges...
 Completely irrelevant, but in vague hopes my old friend might see the shout out here...One of my best friends growing up was an artist (whether he considered himself one or not) named Mark Yee who drew incredibly intricate mazes, typically nested inside a dragon as I recall. Wish I still had one of his sketches.So, if you're out there somewhere Mark, John from Brownsburg says hi!
 Not this guy, by any chance? https://sites.google.com/site/markyeedesign/
 This is really cool. I find procedural generation invaluable for the games I'm working on. So far I'm just using it for background graphics but I'm planning to start working on a maze-based game fairly soon for which this article will provide a great jumping off point.
 I've always played with the thought (too lazy to ever get down to it) about multi-dimensional mazes. They could be very small, but still make for mind-boggling puzzles.Even a 4D maze; let's call it a 3D maze with time-travelling. Could be just 3 "squares" deep in the 4th dimension for a start: "yesterday", "today" and "tomorrow".
 There's a game coming out called Miegakure that involves 4D puzzles, with only 3 discrete position along the 4th dimension. http://marctenbosch.com/news/2015/02/miegakure-and-understan... Instead of navigating directly into the 4th dimension, you have to rotate the world around you, move a bit, then rotate it back to move sideways.
 > Even a 4D maze; let's call it a 3D maze with time-travelling. Could be just 3 "squares" deep in the 4th dimension for a start: "yesterday", "today" and "tomorrow".Have you seen this?"Miegakure [Hide & Reveal] is a game where you navigate a four-dimensional world to perform miraculous feats and solve puzzles."http://miegakure.com/Mind-boggling is a good word for it!
 This looks super interesting, thanks!
 I can't find it now, but there was a Minecraft "adventure" map that was played by a couple of the Yogscast (I think Lewis and Simon) that involved moving back and forth through time and you had to be in the right spots when moving switching times to get across various barriers. So this is definitely a concept that has been explored.Thinking further, The Legend of Zelda: Oracle of Ages definitely involved puzzles like this.
 I think I remember seeing a game like this; moving along one axis also moved you through different periods of time, so that a wall that blocks your path "today" wasn't built "yesterday" and might be a ruin you can jump over "tomorrow".
 It's not a maze game, but that sort of reminds me of Braid (platformer featured in Indie Game: The Movie) where you had to move back and forth through time to navigate certain obstacles. Very cool, and very beautifully rendered.
 I remember trying to solve a spatial 4D maze using this program: http://www.urticator.net/maze/It's difficult.
 That is kinda like the premise of the 'maze runner'. The maze re-ordered itself every night.
 True, and "Cube" also. Only to some extent though: these mazes reordered by themselves, and those trapped in them couldn't "travel in time", or navigate between different setups.
 Cube 2: Hypercube also involved time travel
 Now I'm just envisioning a mechanic like prince of Persia: sands of time
 That's a-maze-ing.

Search: