Avoiding stack overflow (Maze generator in C)

Question

I'm currently writing a maze generator in C, using the depth-first search algorithm. It's working really well, and I'm happy with the result, but when I push the dimensions of the maze a bit too far (more than 2000x2000), it gives me a stack overflow.

I know it's due to the recursivity used in the algorithm, but I really don't know how I can avoid this problem...

Here's the sample of the program where the recursive occurs :

*int dirs is composed of 4 numbers randomized (1, 2, 3 and 4)

x and y are the coordinates in the map

void    recursive_gen(char **map, int x, int y, t_size size)
{
  int   *dirs;
  int   i;

  i = -1;
  dirs = gen_random_dirs();
  while (++i < 4)
    {
      if (dirs[i] == 1)
        up(map, x, y, size);
      if (dirs[i] == 2)
        right(map, x, y, size);
      if (dirs[i] == 3)
        down(map, x, y, size);
      if (dirs[i] == 4)
        left(map, x, y, size);
    }
}

And there's up function (the other are pretty much the same):

void    up(char **map, int x, int y, t_size size)
{
  if (y - 2 < 0)
    return ;
  if (map[y - 2][x] == 'X')
    {
      map[y - 1][x] = '*';
      map[y - 2][x] = '*';
      recursive_gen(map, x, y - 2, size);
    }
}

EDIT : So I did the same in iterative, with a custom stack to stock coords. It works great, but I can't figure out if 10k*10k maze if infinite looping, or if it's really really long (1000*1000 takes 43s, 10k*10k I stopped the program at 1000s)

Is there anyway I can optimize it? Here's the new code :

void    recursive_gen(char **map, t_size size)
{
  int   *pos;
  int   *dirs;
  int   **stack;
  int   i;
  int   istack;

  istack = 0;
  pos = malloc(sizeof(int) * 2);
  pos[0] = 0;
  pos[1] = 0;
  stack = alloc_stack(size);
  while (is_stack_empty(stack) == 0)
    {
      dirs = gen_random_dirs();
      i = -1;
      while (++i < 4)
        {
          if (dirs[i] == 1 && up(map, pos, size, stack) == 1)
            break ;
          if (dirs[i] == 2 && right(map, pos, size, stack) == 1)
            break ;
          if (dirs[i] == 3 && down(map, pos, size, stack) == 1)
            break ;
          if (dirs[i] == 4 && left(map, pos, size, stack) == 1)
            break;
        }
      if (i == 4)
        {
          pos[0] = stack[istack][0];
          pos[1] = stack[istack][1];
          stack[istack][0] = -1;
          stack[istack][1] = -1;
          istack -= 1;
        }
      else
        istack += 1;
    }
}

And the new up function :

int     lastof_stack(int **stack)
{
  int   i;

  i = 0;
  while (stack[i][1] != -1)
    i++;
  return (i);
}

int     up(char **map, int *pos, t_size size, int **stack)
{
  if (pos[1] - 2 < 0)
    return (0);
  if (map[pos[1] - 2][pos[0]] == 'X')
    {
      map[pos[1] - 1][pos[0]] = '*';
      map[pos[1] - 2][pos[0]] = '*';
      pos[1] -= 2;
      stack[lastof_stack(stack)][0] = pos[0];
      stack[lastof_stack(stack)][1] = pos[1];
      return (1);
    }
  return (0);
}

EDIT : working iterative program with custom stack (full working)

Here's a sample of the final code !

int     sub_gen(int *pos, int **stack, int istack, int i)
{
  if (i == 4)
    {
      pos[0] = stack[istack][0];
      pos[1] = stack[istack][1];
      stack[istack][0] = -1;
      stack[istack][1] = -1;
      istack -= 1;
    }
  else
    istack += 1;
  return (istack);
}

void    recursive_gen(char **map, t_size size)
{
  int   *pos;
  int   *dirs;
  int   **stack;
  int   i;
  int   istack;

  istack = 0;
  pos = alloc_pos();
  stack = alloc_stack(size);
  while (stack[0][0] != -1)
    {
      dirs = gen_random_dirs();
      i = -1;
      while (++i < 4)
    if ((dirs[i] == 1 && up(map, pos, stack, istack) == 1) ||
            (dirs[i] == 2 && right(map, pos, size, stack, istack) == 1) ||
            (dirs[i] == 3 && down(map, pos, size, stack, istack) == 1) ||
            (dirs[i] == 4 && left(map, pos, stack, istack) == 1))
          break ;
      istack = sub_gen(pos, stack, istack, i);
    }
}

and up function

int     up(char **map, int *pos, int **stack, int i)
{
  if (pos[1] - 2 < 0)
    return (0);
  if (map[pos[1] - 2][pos[0]] == 'X')
    {
      map[pos[1] - 1][pos[0]] = '*';
      map[pos[1] - 2][pos[0]] = '*';
      pos[1] -= 2;
      stack[i + 1][0] = pos[0];
      stack[i + 1][1] = pos[1];
      return (1);
    }
  return (0);
}

I can upload the full code on github if someone's interested !

you probably have to convert your recursive approach to an iterative approach with a custom stack. — Jean-François Fabre
– Jean-François Fabre ♦, Commented May 10, 2017 at 14:33
Probably not your intent, but the title is amusing for this site :-) — alexis
– alexis, Commented May 10, 2017 at 14:33
I rewrote something like that (flood fill, in python): stackoverflow.com/questions/40963288/… — Jean-François Fabre
– Jean-François Fabre ♦, Commented May 10, 2017 at 14:35
As a rule of thumb: For a given problem, if recursion doesn't seem to make sense, then don't use recursion. If it does seem to make sense, then don't use recursion. — Lundin
– Lundin, Commented May 10, 2017 at 14:38
@Lundin Your rule of thumb reduces to "don't use recursion" :) Why the hate towards recursion? — Ajay Brahmakshatriya
– Ajay Brahmakshatriya, Commented May 10, 2017 at 14:41

Ajay Brahmakshatriya · Accepted Answer · 2017-05-10 15:09:17Z

2

The stack space is usually small and wont be enough to hold lots of stack frames from all the recursive calls. But the heap on the other hand has lots of space (Almost all of your virtual address space).

So you can create a custom stack there which just holds the relevant data on it.

Then you cam use a while loop to process each instance on the stack. Your code is a version of DFS. Look up how you can do DFS without recursion.

The basic idea is that you start with an empty stack and push the first coordinate on it.

Then repeat the following steps till there are elements on the stack (use a while loop).

Pop an element from the stack
Perform the operation for that point
Add neighbours to the stack if they meet the condition (similar to what you used in recursion. Hint : See when do you call recursion, what condition do you check).
Repeat if stack not empty.

There is yet another way if you want to avoid all the code but are ready to sacrifice portability.

You can allocate some space on the heap (order of 100s of MBs) and make that your call stack by setting the stack pointer to that. Then start your recursion. After the recursion is done switch back to original stack.

Remember though you might have to change the Thread Environment Block's field to update the stack limit and stack base because the libraries may check against them to check if the stack is in the limit, or has overflowed.

edited May 10, 2017 at 15:09

answered May 10, 2017 at 14:37

Ajay Brahmakshatriya

9,3403 gold badges31 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

19 Comments

SamuelRousseaux Over a year ago

As I'm quite still a beginner, I didn't understand everything, especially the custom stack (a way to stack every coordinate visited, like the recursion "does" ?) edit: I'll try to recode this without recursion so :)

Ajay Brahmakshatriya Over a year ago

Yes you create a stack on the heap and push on it the coordinate to be processed. Keep processing every coordinate on the stack and adding there neighbours (if they are not added) till the stack is not empty.

SamuelRousseaux Over a year ago

Here's is how I think it could work 1) Create a stack (maximum maze sized) 2) Do the algorithm while possible (puting every coord in the stack) 3) When can't move anymore, travel back in the stack while not possible 4) restart algorithm 5) Find a way to stop it (empty stack?)

Ajay Brahmakshatriya Over a year ago

I will put in a simpler way in my answer. See if that helps.

SamuelRousseaux Over a year ago

Thank you very much ! edit: is there a way to mark this question as solved? I'm a bit new to this site :/ edit2: didn't look in the right place

|

Collectives™ on Stack Overflow

Avoiding stack overflow (Maze generator in C)

1 Answer 1

19 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

19 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related