5
\$\begingroup\$

I want to generate a maze with the following properties:

  • The maze is non-perfect. Means it has loops and multiple ways to reach the exit.
  • The maze should be random. The algorithm should output different mazes for different input parameters
  • The maze doesn't have to be braided. Means dead-ends are allowed and appreciated.

I just can't find the right resources on google. The closest i found was this description of the different types of algorithms: http://www.astrolog.org/labyrnth/algrithm.htm. All other algorithms were for perfect mazes.

Can anyone give me a website where i can look this up or maybe an algorithm directly?

\$\endgroup\$
  • 6
    \$\begingroup\$ You can easily convert a perfect maze to a non-perfect one by deleting a few walls at random. If you need to maintain some minimum difficulty, you can compute the shortest path through the maze and only delete walls that keep this above some threshold. \$\endgroup\$ – DMGregory May 25 '14 at 19:51
  • \$\begingroup\$ Sounds good. Almost too easy to work^^ The more walls i delete the easier the maze gets. I will try that out. \$\endgroup\$ – Shylux May 25 '14 at 20:55
  • \$\begingroup\$ I would approach it the same way that you simulate lighting. If you draw a straight line between the start and end that would be the simplest maze. Of course if it's a grid based maze you'd quantize the "line" to widely land on grid spaces and fill in walls around the line. For lighting effects you then find a point somewhere between the start and end on that line and then you move that point a random amount perpendicular to the line. Keep doing that until you fill in the entire grid. But that's just my guess at how I'd try it - which is why it's not offered in an answer. \$\endgroup\$ – badweasel May 28 '14 at 5:59
10
\$\begingroup\$

You can construct non-perfect mazes as DMGregory mentioned, starting with a perfect maze then deleting walls at random. However, it sounds like you may be after a maze that's not quite the same as a non-perfect one. The definition of a perfect maze is:

A "perfect" Maze means one without any loops or closed circuits, and without any inaccessible areas. Also called a simply-connected Maze. From each point, there is exactly one path to any other point. The Maze has exactly one solution.

That is, as long as there is at least one loop, it's not a perfect maze. It doesn't have to have more than one solution to be non-perfect, but since this is GD.SE I assume multiple solutions is a lot more relevant.

So how does one make a maze with multiple solutions? You'd need to remove walls that are along the solution path. This can be done deliberately, or just randomly remove walls but check how many solutions there are using a maze solver.

This still might not create interesting mazes though; a maze might have multiple solutions but if you're only adding a tiny loop in the solution, gameplay-wise it won't feel like multiple solutions - maybe a shortcut at best.

On the maze classification page you've linked, there is this interesting section:

Bottleneck finder: This means to find those passages or intersection points in a Maze such that every solution to that Maze passes through them. To do this, run the left hand wall follower to get the leftmost solution, and run the right hand wall follower to get the rightmost solution, where places the two solutions have in common are the bottlenecks. That technique however only works for Mazes that wall following will successfully solve. For other Mazes, to find bottleneck passages, find any solution to the Maze, and also run the blind alley sealer (which may make the Maze unsolvable if it treats an entrance or exit within the Maze as a large blind alley). Parts of the solution path that go through sealed off passages, are bottlenecks. enter image description here

That is, bottlenecks are passages that every solution passes through. You can create mazes with multiple solutions that feel meaningful by making sure that the length of bottlenecks is short compared to your shortest solution.

Bottlenecks are very useful for games in a number of ways:

  • Since players are guaranteed to pass through them, you can place things such as critical objectives, quest items, save points (depending on your game) here. If you have a limited budget for interesting content, you'll get the most bang-for-buck by making sure they are placed at bottlenecks.
  • Conversely, you may want to place optional items or secrets outside the bottleneck so that the player may not always find them. Depending on the method you use to determine bottlenecks, you could also find out which areas of the maze are not covered by any solution, and place secrets there.
  • Bottlenecks are natural chokepoints; this has implications that depend on the type of game, so design accordingly.
\$\endgroup\$
  • \$\begingroup\$ There's a lot more information about building mazes here: Maze Psychology - it is an excellent resource. It mentions how loops increase the maze's difficulty, unless they are on the solution path (where they create new solutions), but there are many more factors mentioned too. \$\endgroup\$ – congusbongus May 29 '14 at 23:13
1
\$\begingroup\$

I find that the RougeBasin wiki has useful gamedev articles. I've used them for my non-rougelike games in the past.

See two maze algorithms here and here.

Here's one using depth-first search (a weapon of choice for maze generation) on Rosetta Code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.