Seeking some advice from more experienced programmers. I have been working on a random maze generator, with the backtracking method.
Without getting too much into code details, my ‘step start’ function checks 4 cardinal directions, decides which of these are valid to take, then rolls and picks a random viable path.
This calls a ‘normal step’ function which records the new step coordinates and calls the original ‘step start’ function again.
Once we reach a point where there are no more viable paths, a boolean is flipped and the next step will instead call a ‘backtracking step’ function, which performs a step back and (re)tries to make a step by calling the original ‘step start’ function.
This of course loops a lot of times depending on the maze size. The saving grace, is when we get back to the start point, the functions end and we proceed with other things (placing visual tiles etc)
Issue:
After a certain maze size, this leads to a Stack Overflow error 1024, asking me to check for infinite recursion. If my information is correct, this occurs due to a limitation. The original step function remains open as long as new functions are called from it - and after a certain amount it just says ‘no more’. (not sure though)
So my question is, are there any elegant solutions to this issue?
I have tried sending signals instead of hard-calling functions, but it seemed to not change anything. I even tried sending signals to a global signal bus, separate from the main script and sending signals back, to step again, but this also resulted in the same error. (I’m assuming this does not work because I connect those signals to a function..?)
*(I have temporarily solved this by forcing a stop after every 10 steps, and by the _process function checking various booleans every frame, to restart the step function when it is not running and is allowed to run - I think this is barbaric and potentially dangerous - but I’m a newbie, which is why I’m posting here)
*
I can give more context if needed, I just wanted to keep it simple and straight forward
Well check for infinite recursion. Does your code go into infinite recursion (which would be a bug) or it just goes very deep when the maze size is large. If latter is the case, just increase the call stack size in project settings so it can handle your largest map.
That said, anything that can be done via call recursion, can be done without it by maintaining your own state stack.
There are some good algorithms there to compare yours to.
I have to say though, for all the problem sets the size of the area traversed is relatively small. You didn’t mention what the size of the maze you are trying to find the path for, but given you are stopping “… after every 10 steps …” I suspect it is fairly large. I’m not surprised you are overflowing the stack.
You likely will have to process sections of your maze in chunks.
It just goes deep, works fine on smaller maze sizes, and when I process in chunks its fine, so it does not go to infinity.
Could you elaborate on maintaining state stack? I’m fairly new to this Not sure how I would go about this without recursion.
Thanks for the link! I’ll check it out.
Although yea, it’s due to the size. I’m just not sure how to process in chunks more elegantly than I am doing now
How do you think recursion works? Or in fact any function call. It just pushes the current function context on the stack and creates a new context for a called function.
Instead of letting the language do this via function calls you can determine all the data needed to represent your state/context and just push that data structure onto your own stack (implemented via an array for example). Same with popping the state instead of returning from the function.
A classical example of recursive call algorithm is tree traversal. In GDScript you’d do something like this to traverse the scene tree:
func traverse_tree_recursive(node: Node) -> void:
print("visited: ", node)
for child: Node in node.get_children():
traverse_tree_recursive(child)
Non recursive version requires maintaining your own stack that holds the current state which in this case is the node we’re visiting. So the same thing without the recursive call:
func traverse_tree(root_node: Node) -> void:
var stack := [root_node]
while not stack.is_empty():
var current_node: Node = stack.pop_back()
print("visited: ", current_node)
var children: Array = current_node.get_children()
children.reverse()
stack.append_array(children)
So basically I’ll need to generate all my data in one function instead of hopping between functions I keep calling. Gotcha! I see where it went wrong now.
Not sure how I would go about this without recursion.