Re: Random maze/dungeon generator
Posted: Sat Jun 09, 2012 7:10 am
I had created a mage generation program a while ago and posted code for it last time someone asked about maze generation.
viewtopic.php?f=4&t=7126&p=46241&hilit= ... ion#p46241
My method was more "depth first search" algorithm and was used for a compact grid "room" style maze where each grid square is a room. Basically..
1) It starts by taking a starting point.
2) Draw a path starting from that point off in random directions. Pick a random direction and if it's not already taken, move into it. If it is taken, choose another direction.
3) Continue doing this until you reach a square that has no empty sides. i.e. there is no where to go.
4) If there is no where to go, choose a square at random that is A) part of an existing path and B) has at least one empty side and go to step 2.
5) Do this until all empty squares are taken.
As you go along and mark a square, set some flags in the squares data to tell the game which sides are open. (i.e. which walls would have doors)
This method would make sure the maze is solvable and would also not require backtracking. The only part you have to figure out is the method for figuring where to put the next start point after the first path is finished. That's pretty easy. Either choose a random square until you find a valid one, or loop through each path and randomly stop on a square if it is valid.
If you were to use a grid but wanted to have a block buffer between each path, you'd modify it so instead of flags for doors you'd just dig through an extra layer by setting it as open after setting the current square as open before moving on to the next one. Quite simple.
I plan on rewriting my maze generation algorithm for use in my 3D Raycaster engine and will probably use that method and will modify it to add things like rooms.
viewtopic.php?f=4&t=7126&p=46241&hilit= ... ion#p46241
My method was more "depth first search" algorithm and was used for a compact grid "room" style maze where each grid square is a room. Basically..
1) It starts by taking a starting point.
2) Draw a path starting from that point off in random directions. Pick a random direction and if it's not already taken, move into it. If it is taken, choose another direction.
3) Continue doing this until you reach a square that has no empty sides. i.e. there is no where to go.
4) If there is no where to go, choose a square at random that is A) part of an existing path and B) has at least one empty side and go to step 2.
5) Do this until all empty squares are taken.
As you go along and mark a square, set some flags in the squares data to tell the game which sides are open. (i.e. which walls would have doors)
This method would make sure the maze is solvable and would also not require backtracking. The only part you have to figure out is the method for figuring where to put the next start point after the first path is finished. That's pretty easy. Either choose a random square until you find a valid one, or loop through each path and randomly stop on a square if it is valid.
If you were to use a grid but wanted to have a block buffer between each path, you'd modify it so instead of flags for doors you'd just dig through an extra layer by setting it as open after setting the current square as open before moving on to the next one. Quite simple.
I plan on rewriting my maze generation algorithm for use in my 3D Raycaster engine and will probably use that method and will modify it to add things like rooms.
