How can I generate a maze with multiple solutions and paths? #130
-
|
I need to generate mazes with multiple solutions, then I want to create an algorithms that finds the best path (it's a university project). How can I do that? |
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 1 reply
-
|
Hello! That's going to be tricky. All the maze-generating algorithms here create what are called "perfect mazes". Those are mazes with one, and only one solution. So none of these will generate you exactly what you want out-of-the-box. BUT, you could generate a maze, using any of the maze-generating algorithms here, and then randomly remove any one wall. This will almost certainly create a loop in your maze, and thus multiple solutions. And then you could use a maze-solving algorithm that works with loops and finds multiple solutions (say ShortestPaths). Sounds like it should only take 10 or 20 lines of code. If you need to know how to use Good luck! |
Beta Was this translation helpful? Give feedback.
-
|
Yeah I actually I made something similar: I created a function that randomly select some internal walls and it breaks them, so now it generates a maze with multiple solutions. Thanks for the answer :) |
Beta Was this translation helpful? Give feedback.
Hello!
That's going to be tricky. All the maze-generating algorithms here create what are called "perfect mazes". Those are mazes with one, and only one solution. So none of these will generate you exactly what you want out-of-the-box.
BUT, you could generate a maze, using any of the maze-generating algorithms here, and then randomly remove any one wall. This will almost certainly create a loop in your maze, and thus multiple solutions.
And then you could use a maze-solving algorithm that works with loops and finds multiple solutions (say ShortestPaths).
Sounds like it should only take 10 or 20 lines of code.
If you need to know how to use
mazelib, check out the API docs.Good luck!