Algorithms for making more interesting mazes

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.

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:

http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes...

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...

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.

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.

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!

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.

That's a-maze-ing.