Google+

Curse of the Recursive Backtracker

Leave a comment

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:

In human:

Start > Look where we can go > Take a step > If we couldn’t take a step go back a step

In pseudocode:

  1. Scan the tiles and find the first empty one.
  2. Place this on the Stack.
  3. Make the tile active
  4. While the Stack has data in it:
  5. Retrieve the coordinates of the top tile on the Stack.
  6. Check the four cardinal directions
  7. If there are none free remove the item from the Stack – Goto step 4
  8. If there are free directions pick one
  9. Set the linking tile to active.
  10. Set the new tile to active
  11. Add the new tile coordinates to the stack.
  12. 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

Cycle Squares

Check if free and if so put it onto the stack. Enter a While Loop as long as the Stack holds data….If Clear-While

Read the coordinates from the Stack
Read top item

Set the tile as active and check the surroundings for available tilesSet and check

If there are no tiles free – take the tile off the Stack…

If none free

If they are free, generate a random direction 0-3 (South, North, West, East) and link back if they are not free…

Choose direction

For each direction… check the bounds and add a linking tile…

Check Bounds

Finally add the new destination.

Push 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:

http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

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,

http://www.roguebasin.com/index.php?title=Dungeon-Building_Algorithm

Programming:

Stack – http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Mips/stack.html
While Loops – http://www.w3schools.com/js/js_loop_while.asp

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog Stats

  • 10,074 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 580 other followers

Archive

%d bloggers like this: