4 ms·
I'm interested see how the maze is generated so that there Is a solution to it (ie, no exit point without an open way)
by harel 11y ago
I'm interested see how the maze is generated so that there Is a solution to it (ie, no exit point without an open way)
- shultays 11y agoNot OP but you can always generate a fully random maze and then merge the unconnected blocks by simply removing a wall that can connect them
- white-flame 11y agoMost maze generators build a giant tree, starting from an arbitrary point and sending out branching corridors until the area is full. By its nature everything's connected.
- lovegraphs 11y agoThe particular generation algorithm that you see is called "Randomized Prim's algorithm" on Wikipedia. It starts at a random cell in a grid, marks it as discovered, and adds all of that cell's adjacent walls to a queue. It then selects a random wall from the queue and, if the cell on the other side of the wall has not yet been discovered, opens up that wall. It adds all of the adjacent cell's walls to the queue, marks the adjacent cell as discovered, and selects the next random wall in the queue until all the cells have been discovered. It's kind of a modified BFS. This algorithm guarantees that all cells are connected.