Non-perfect maze generation algorithm

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?

Answer

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.

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.