CODEWITHSUNDEEP
javaalgorithmrecursion
ultrainstinct
ultrainstinct

Reputation: 255

Recursive maze generation

I accidentally posted this question on a different account of mine, so I deleted the post and reposted on this account.

So I wanted to create a maze generation algorithm for fun, but I hit a bit of a bump. The algorithm I wrote puts in spaces that are unreachable and that have no exit. What could the problem be?

Here is what I mean

# # # # # # # # # # # # # # # # # # # # # 
# . . . . . # . # . . . # . # . # . . . # 
# . # # # . # . # # # . # # # . # # # # # 
# . . . # . # . # . . . . . # . . . . . # 
# # # . # . # . # # # # # . # # # . # # # 
# . . . # . # . . . . . # . # . # . # . # 
# . # # # . # # # # # . # # # . # . # . # 
# . # . # . . . . . # . . . . . . . # . # 
# . # . # . # # # # # # # . # # # . # # # 
# . # . # . . . . . . . # . . . # . # . # 
# . # . # # # # # # # . # . # . # # # . # 
# . # . # . . . . . . . # . # . # . . . # 
# # # # # . # # # # # # # . # . # . # # # 
# . # . . . # . . . . . . . # . # . # . # 
# . # # # . # . # # # # # # # # # . # # # 
# . . . # . . . # . # . . . . . . . # . # 
# # # . # # # . # # # # # # # . # # # . # 
# . # . # . . . . . # . . . # . . . . . # 
# # # . # . # # # . # . # # # . # # # . # 
# . # . . . # . # . # . # . . . . . # . # 
# # # # # # # # # # # # # # # # # # # # #

And this is my code
Description:
Create a maze consisting of entirely connected cells. As stated 0 up, 1 down, 2 right, 3 left, orientTo records whether the dfs went up/down/left/right to get to the current cell. In the mazeGen function: generate the cell you came from, now remove the wall between current cell and last cell. Generate all neighbours of current cell and randomly arrange them into an array, array holds x,y, and which way the dfs moved to get to this neighbour cell. Now iterate through this array and recursively call the dfs with these neighbour values.

Upvotes: 3

Views: 991

Answers (1)

Ante
Ante

Reputation: 5458

I suppose that maze spaces (non-walls) should make a tree. That means, all spaces connected and there is only one path between each pair of spaces.

Since tree doesn't have a cycle, it is possible to create a maze by breaking any cycle found. It can be done by finding cycles (DFS) and setting any space that is in detected cycle to be a wall till there is no cycles. It can be done in one DFS pass. Creation of different mazes is done by choosing different starting space and randomly choosing neighbour to proceed.

Upvotes: 2

Related Questions