Recursive backtracking maze algorithm: Infinite loop/recursion limit?

[RobMN502]

After finding out about recursive backtracking, I figured I’d try my hand at developing a basic maze algorithm. After making what appeared to be a working recursive backtracking maze, I ran into a few issues, as well as some major crashing.

Essentially, it works off of a grid of integers with variable associations. Maze paths can be adjacent to walls, and must be spaced one away from non-barrier tiles in use, but fill empty ones. Simple enough. I check all directions for each tile and, while it is possible to move to one of those directions, it will loop through in order to handle recursion. As for finding the coordinates themselves, I have a parallel array of coordinates that I used to check each position (x or y * tilesize, allows for static mesh placement). I haven’t developed a true system of random pathway choice, so I need to handle that as well, and the current fixup is pretty terrible looking (you’ll see)

An example of a smaller maze and the maze it generates, nothing too fancy.

Because the mazes are dependent on while loops and directions, it appears that the recursive methods enter an infinite loop after some number of tiles has been reached (stopping points included 30 by 30 and 58 by 20). This is what it looks like if I use a for loop that occurs four times, so there are definitely more movements to be made.

I generate the integer grid and assign values here. The outside tiles are set as barriers, and the rest are empty.

Been messing around with whether or not it should occur with a for loop and such, but I figured I was better off starting at the first open position (1 by 1, or 200 by 200 if considering tile size)

An example of directional checks. Went through each one to make sure that the coordinate math was correct, so they do calculate the space to be moved to as well as three surrounding blocks (like a tetris block)

Still have to figure out an efficient way to randomly choose between directions without making this sort of mess.

I suppose I’m at a pretty hard standstill here. Maybe I’m missing something really key to this process here? Perhaps this sort of programming isn’t particularly suited for Blueprints as much as it is for C++? Will we ever find a solution? Who is the father?

[RobMN502]

Any ideas?

[HateDread]

Have you tried raising the loop iteration limit? Apparently the limit is not number of loops, but number of instructions.

As Ryan suggests in the above link, navigate to Edit -> Project Settings -> (Engine) General Settings -> ‘Maximum Loop Iteration Count’, and set it to a higher number. In my case, I threw an extra zero on the end, and now my problems are gone (I was doing a lot of array manipulation inside a nested foreach loop, and consistently went over the limit).

Hope this helps!

[RobMN502]

Thanks for the suggestion. After a bit more testing and tweaking, it appears that my primary issue is that recursive blueprints seem to suddenly stop after so many iterations. It appears to be around 248 to 250 times, so I figure the most efficient way to go about this process would be with some C++ code. Getting a two dimensional array out of that would be pretty easy I figure.

[Hyperloop]

You could look at breaking up the loops over several ticks - I ended up doing that with some world gen stuff I’m doing. I made a macro for it, here’s the pastebin: http://pastebin.com/n7DbtZ1P (paste into a blueprint to see the setup).

My example works if you know the number of loops you need to execute, but I’m sure you can see the basic idea and change it to suit your needs.

[pattym]

Hi RobMN502, I found you thread and thought I’d give you a hand. A few month ago I made a random maze generator based on the recursive backtrack algorithm and I actually made a tutorial on it you might find useful.

Tutorial: Random Maze Generator

It’s not the best way of doing it and I have since made a more improved version (no tutorial I’m afraid) but the general concept is the same so you might be able to use some of the methods I used to resolve your problem. I myself never bumped into the recursion limit but just so your aware the time it takes to generate increases exponentially as the size increases. The largest I was able to generate was about 125*125 which took about 15 mins (not ideal really) but generating smaller mazes tiled next to each other can significantly improve this.

I hope this helps.

[Jamendxman3]

Did you develop this yourself or follow a tutorial? I am making a mining game and need something to make caves.

[RobMN502]

Thanks for the feedback guys. Decided to go back to the drawing board and see what I’ve been doing wrong. Tried to work out the program in java with similar logic, and it works really well right now! Turns out that loops are absolutely unnecessary, if statements are the way to go. Here’s an example of some output:

Was feeling lazy, so I didn’t color code the whole thing.
*- Hallway floor
W- Walls
B- Outer barrier
_-Room space

The algorithm/logic is actually based off of something I’d seen online a while back. Pretty extensive discussion on how to generate rooms, hallways and doors without error. In this case, I need to fix up a connector method that I’ve been working on, but the yellow slashes essentially indicate potential doors. So, a room is given a random number of doors (I’m keeping it at 1 to 2 right now), and space between two different rooms (eg: hall and room, room 1 and room 12) is a candidate.

I figure that moving to C++ would allow for some crazy generation, because this thing popped out in a few seconds. Rooms at 50 x 50 generate fairly quickly, although anything above 120 x 120 causes some stack overflow errors with the hallway generation. I’ll see if I can make the logic more efficient, but I doubt having a map over 100x100 tiles would be a good design choice anyway.

However, after looking into other methods of generation, I see that although the dungeons generated are flawless and provide some good hallways, the algorithm/logic is flawed in that hallways are generated inefficiently. There are some other ways to generate procedural, large scale maps without the use of recursive methods, although that would take some time to implement properly. Generating X amount of boxes, choosing a handful of larger boxes and connecting them through others is one method I read up on. I’ll see what else there is to try.