Maximum recursion depth exceeded

[Riyuzakisan]

(Using Blender 2.58a)

I’m working on this maze creator project and I wanted to set up an option to generate a random maze based on the Prim’s algorithm. The maze is made up of blocks which can be carved out to leave empty spaces. These blocks are stored in a dictionary.
Here’s how the algorithm works:

1. Pick a block to start at, add it to the maze list
2. Get a random block from the maze list to work on
    -This would be the spawn block if run the first time
3. Get the walls of this random block
4. Pick a random wall and get the neighboring cell on the other side
5. If the neighbor cell isn't already in the maze list, add it to the list
    and remove the block between it and the current cell
6. Repeat step 2 until all original empty cell blocks have been added to the maze list

I get this error involving the randint function from the random module.

I’m unfamiliar with what this error means, I can only guess that it ran out of memory. Any help would be greatly appreciated, or suggestions of a new maze generation algorithm that doesn’t pose this problem.

[Monster]

You produced an endless loop.

This happens when a method calls itself constantly (recursive looping).
While each call eats a bit of the stack memory the loop will break when no memory is left (could take a while).

I guess you use recursion to generate your maze. This is fine and a common method.

Usually such methods contains “security” checks to prevent endless loops, e.g. max depth checks. In that way the error you got is your security check.

Such loop often occurs when the recursive state didn’t changed while calling the next recursion.

E.g. first call(10) scond (9) … last call (0) = return but your get
call(10); call(9); call(9); call(9), call(9) which never returns

I suggest you add to your recursion

def recursionMethod( param1, param2 ...):
  ...
  recursionMethod( nextParam1, nextParam2 ...)

following security check at each followup recursion:

def recursionMethod( param1, param2 ...):
  ...
  if (nextParam1 == param1 and
    (nextParam2 == param2 and
    ...):
    print ("loooooooping!!!!!")
    return None
 
  recursionMethod( nextParam1, nextParam2 ...)
 
  ...
  if (anotherParam1 == param1 and
    (anotherParam2 == param2 and
    ...):
    print ("loooooooping!!!!!")
    return None
 
  recursionMethod( anotherParam1, anotherParam2 ...)

Mostlikely this does not help if your recursion uses multiple nested methods:

def call(x):
  anotherCall(y)
 
def anothrCall(y):
  call(x)

[Edit]
You can analyze the fragments of the stacktrace to see the recursive calls.
You can use PyDev or another debugger and debug into the recursion. But you should know what you are doing.
You could print the params of the recurision to help identifying the problem.

I hope it helps

[Riyuzakisan]

My method is currently using something like:

def main():
    from random import randint as rand
    o = generatorObject
    
    rindex = rand(0, len(o['maze'])-1)
    next = o['maze'][rindex]
    
    wall = getrandomwall_function()
    
    neighbor = getneighbor_function()
    
    if neighbor != None:
        wall = 'empty'
        o['maze'].append(neighbor)
    
    #o['cells'] is a list of original empty cells
    if len(o['maze'] < len(o['cells']):
        main()

This is of course just an example code. The maze generates fine with small dimensions, it’s just at around 20x20 and above that I start getting the error.

[Monster]

xxx_function is a strange name :). When you call it it () is obvious a function ;).

Anyway:
You recursivly call main() again.

You do not even provide actual parameters.
…
It seems you are sharing data via
property “maze”

hard to read
…

OK, you increase the size of maze until you over a limit (size of “cells”).

The problem is you do not increase the size of maze if neighbor is None but you still call the recursion. This is the main issue of your algorithm. Even without recursion your could produce an endless loop.

Finally: I do not see why you use recursion at all. It makes no sense here. You can simply use a loop:

from random import randint as rand
def main():
    maze = generatorObject['maze']
    cells = generatorObject['cells']
    while len(maze) < len(cells):
        next(maze)
 
def next(maze):
    # this gives you any part of the maze
    # it would be much better to choose 
    # from a list of not processed maze parts
    # otherwise you get random perfomance lags
    rindex = rand(0, len(maze)-1) 
    next = maze[rindex]
 
    wall = getrandomwall_function()
 
    neighbor = getneighbor_function() # think about what happens if it returns always None
 
    if neighbor is not None: 
        wall = 'empty' # what means that? it is not used anywhere
        maze.append(neighbor)
        return
 
    # when you are here the maze didn't changed 
    # and you are in danger to produce an endless loop
    # and you need to kill the process

[Riyuzakisan]

Thanks for the help Monster, very much appreciated

I’ve been afraid to use the while loop, almost every time I have used it, it somehow ended up making an infinite loop and crashing Blender. I must have been using it wrong before. The code I put up was just a quickly typed example of my original code, so some things didn’t make sense

I have it working now with the while loop and some return functions set up, and I can get it over the 20x20 limit now without problems. In fact, I generated up to 100x100, which is the maze dimensions limit, (with a bit of lag).

Here is a 50x50 generated maze: