CODEWITHSUNDEEP
algorithmmaze
Gilfoyle
Gilfoyle

Reputation: 3616

Algorithm to generate a maze with / without solution

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?

Upvotes: 1

Views: 689

Answers (1)

LSerni
LSerni

Reputation: 57378

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 = { };
}

Upvotes: 2

Related Questions