December 1, 2015 by jonmillymiles
In my previous post I explained that there were several choices that I was considering for generating my maze.
The first was Eller’s Algorithm, the next the recursive backtracker and finally a more linear corridor and room generation algorithm. In this post I will go through what has turned out to be a most surprising turn of events.
Firstly, I need to say that Eller’s Algorithm was fast… the recursive backtracker is not so fast: comparatively speaking it is extremely slow and it gets worse the larger the maze is. Secondly this algorithm requires a greater understanding of programming and programming techniques than the previous technique. Therefore you may well get lost, and there is no shame in that, but I will provide some useful links at the bottom to help.
Where to begin?? Well before you begin to build a routine to generate something you need to do your homework and think about how you want it to work. As with all design work, an hour spent thinking about this can save tens of hours in production. This becomes more importantly when combined with programming as 90% of the work will take 10% of the time and 10% of the work, the bugs, will take 90% of the time.
So to begin, how the recursive backtracker works:
Start > Look where we can go > Take a step > If we couldn’t take a step go back a step
- Scan the tiles and find the first empty one.
- Place this on the Stack.
- Make the tile active
- While the Stack has data in it:
- Retrieve the coordinates of the top tile on the Stack.
- Check the four cardinal directions
- If there are none free remove the item from the Stack – Goto step 4
- If there are free directions pick one
- Set the linking tile to active.
- Set the new tile to active
- Add the new tile coordinates to the stack.
- Goto step 4
And, there you go.
So what is a Stack. A stack is a First In Last Out data object that works like a big stack of books. You place a book on the top and keep doing it. When you want a book you have to take the top one off before you can access the one below it. If you want the one at the bottom then you need to take all of the other books off in order first. More here…
We use the stack to store where we have been so that we can take that step backwards and explore the other options.
So we need:
- A stack – an array of tiles (X+Y integers)
- Ways to add, read and remove from the stack
- A struct – tiles with X+Y integers
- A change to our check algorithm to allow for a change in scan range and which directions are blocked.
- Possibly some other stuff – always worth planning in some flex with this kind of thing.
The code, this took me a while:
Cycle through the squares
If there are no tiles free – take the tile off the Stack…
If they are free, generate a random direction 0-3 (South, North, West, East) and link back if they are not free…
For each direction… check the bounds and add a linking tile…
Finally add the new destination.
We don’t need to activate the new destination tile as it happens at the start of this loop.
Now to show you the results, and the speed difference as we scale up the map. I have found that by recompiling the blueprint while looking at the viewport window we can see just how the maze looks from above… it’s quite cool… and very useful 🙂
What I have done differently to my reference is that I have made the maze first and then placed the rooms, this means that I do not need to go round afterwards linking up the rooms as all the squares are already linked. What it does mean though is that there is a chance for each room to be connected many times.
You can see that as the maze is made bigger so the procedure becomes slower. That said I think there is a nice balance to the dungeons: all the rooms are connected and there are some dead ends left occasionally too.
And to see this in the game:
Now all of this doesn’t come without some research, I have “mashed together” a few techniques to make this work:
Roguebasin is a huge repository of procedurally generated content: http://www.roguebasin.com/index.php?title=Main_Page
However it is this page in particular that has helped with understanding the recursive backtracker:
Other sources of note:
Astrolog.org – http://www.astrolog.org/labyrnth/algrithm.htm
This was my final option, but for what I want to achieve, and I have I will not explore this aspect of the code any further,