1

I found this question here on Stack Overflow about good algorithms to generate mazes. I would need an algorithm which also generates mazes but where I can decide if they have a solution or not. Which algorithm is suitable for this?

Gilfoyle
  • 3,282
  • 3
  • 47
  • 83
  • Can you clarify what you want it for? My first guess would be testing maze-solving algorithms - and in that case I would guess you might also be interested in having multiple solutions, loops, dead-ends, etc. But I might be mistaken. – Hans Olsson May 03 '18 at 14:32
  • @HansOlsson Yes, I want to test maze-solving algorithms – Gilfoyle May 03 '18 at 14:34
  • A good maze generating algorithm always generates a maze that has a solution. – Jim Mischel May 03 '18 at 17:35

1 Answers1

2

Use a Recursive Backtracker to generate a labyrinth with one solution. Or any of the several algorithms available.

These algorithms will generate some kind of labyrinth data format, usually indicating for each cell the status of two of its edges (so, two bits per cell), and also the unique solving path.

Then, if you want for it not to have a solution, choose a cell in the middle of the path and add one wall, killing the only solution there was. How to do this depends on the algorithm's maze data format. It could be as simple as 

if (noSolution) {
    var kill = Math.floor(maze.path.length/2);
    maze.cell[maze.path[kill].y]
             [maze.path[kill].x].edges = { };
}
LSerni
  • 55,617
  • 10
  • 65
  • 107
  • Can you please more specific. How can I determine which cell belongs to the path? And is there, using the recursive backtracker, only a single solution? – Gilfoyle May 10 '18 at 12:32
  • The determination will depend on the algorithm. Which if it generates a perfect maze, as those listed in the linked answer do, willl give you one and only one solution. – LSerni May 10 '18 at 12:45