7 ms·
Algorithms for making more interesting mazes
- bartread 10y agoThis 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.
- V-2 10y agoI'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".
- baldeagle 10y agoThat is kinda like the premise of the 'maze runner'. The maze re-ordered itself every night.
- V-2 10y agoTrue, 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.
- pavel_lishin 10y agoI 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".
- bartread 10y agoIt'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.
- seanwilson 10y ago> 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/ http://miegakure.com/ Mind-boggling is a good word for it!
- V-2 10y agoThis looks super interesting, thanks!
- sp332 10y agoThere'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-understanding-and-parallel-universes/ 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.
- Bjartr 10y agoI 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.
- xigency 10y agoI remember trying to solve a spatial 4D maze using this program: http://www.urticator.net/maze/ http://www.urticator.net/maze/ It's difficult.
- dahart 10y agoThe 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...
- nanolith 10y agoAnother 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.
- TeMPOraL 10y ago> 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...
- dalke 10y agohttp://www.commitstrip.com/en/2016/04/14/meanwhile-in-a-parallel-universe-3/ http://www.commitstrip.com/en/2016/04/14/meanwhile-in-a-para...
- 3pt14159 10y agoHmmmm. 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?
- jefffoster 10y agoI love maze algorithms. The visualisations by https://bl.ocks.org/mbostock/11357811 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-challenge http://www.red-gate.com/our-company/entrypage/coding-challen... if you are interested.
- nayuki 10y agoI like Mike Bostock's demos of maze-generation algorithms: https://bost.ocks.org/mike/algorithms/#maze-generation https://bost.ocks.org/mike/algorithms/#maze-generation
- dahart 10y agoFun! 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.
- tyrbo 10y agohttp://www.jamisbuck.org/mazes/ 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.
- tarentel 10y agohttp://weblog.jamisbuck.org/ 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.
- jondubois 10y agoThat's a-maze-ing.
- munificent 10y agoFun 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: http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes...
- bartread 10y agoYeah, 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.
- bartread 10y agoThat's an awesome post, by the way, so thanks for sharing - definitely going to crib some ideas from it.
- macintux 10y agoCompletely 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!
- bartread 10y agoNot this guy, by any chance? https://sites.google.com/site/markyeedesign/ https://sites.google.com/site/markyeedesign/