3

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 !

SamuelRousseaux
  • 107
  • 1
  • 1
  • 8
  • 5
    you probably have to convert your recursive approach to an iterative approach with a custom stack. – Jean-François Fabre May 10 '17 at 14:33
  • 3
    Probably not your intent, but the title is amusing for this site :-) – alexis May 10 '17 at 14:33
  • I rewrote something like that (flood fill, in python): http://stackoverflow.com/questions/40963288/fatal-python-error-cannot-recover-from-stack-overflow-during-flood-fill/40963737?s=2|0.2649#40963737 – Jean-François Fabre May 10 '17 at 14:35
  • 2
    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 May 10 '17 at 14:38
  • @Lundin Your rule of thumb reduces to "don't use recursion" :) Why the hate towards recursion? – Ajay Brahmakshatriya May 10 '17 at 14:41
  • @AjayBrahmakshatriya For the following reasons: 1) it is most of the time very slow 2) it is very memory-consuming 3) it is very dangerous 4) it is hard to read 5) it comes with no benefits what-so-ever in 99.9% of all use cases. – Lundin May 10 '17 at 14:45
  • @Lundin most compilers performing tail call optimizations make it bearable though. But yes, I agree, in general one should try to avoid. – Ajay Brahmakshatriya May 10 '17 at 14:46
  • @AjayBrahmakshatriya Hence "most of the time very slow". Tail recursion might, if you are lucky, get optimized to a loop. Or you could write it as a loop to begin with. But most confused uses of recursion are _not_ tail call but some other mess, like in the above code. The compiler will not be able to optimize it, so the stack gets blown to pieces. – Lundin May 10 '17 at 14:49
  • I tried recursion because it was quite logic for this algorithm, I'll try to search for an interative approach ! – SamuelRousseaux May 10 '17 at 14:52
  • Porr man's partial solution: you can save some stack space by avoiding the parameters `map` and `size` as they never change throughout the algorithm. Instead have 2 global variables `map` and `size`. So the prototype would be `recursive_gen(int x, int y,)`. – Jabberwocky May 10 '17 at 15:33
  • I can't use globals :/ Forbiden by the exercise – SamuelRousseaux May 10 '17 at 15:50

1 Answers1

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).

  1. Pop an element from the stack
  2. Perform the operation for that point
  3. 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).
  4. 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.

Ajay Brahmakshatriya
  • 8,993
  • 3
  • 26
  • 49
  • 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 :) – SamuelRousseaux May 10 '17 at 14:53
  • 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. – Ajay Brahmakshatriya May 10 '17 at 14:56
  • 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?) – SamuelRousseaux May 10 '17 at 15:03
  • I will put in a simpler way in my answer. See if that helps. – Ajay Brahmakshatriya May 10 '17 at 15:04
  • 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 – SamuelRousseaux May 10 '17 at 15:10
  • I edited my code, the problem is that it don't seems to be optimized, even after 30min, the 10k*10k don't show any result – SamuelRousseaux May 10 '17 at 19:08
  • 10k * 10k cells. That is really a large number of cells. Try writing a simple loop that counts up to 10k * 10k and see how much time it takes. – Ajay Brahmakshatriya May 10 '17 at 19:09
  • With just a single loop, that goes from 0 to 10k*10k, it took 0.22s – SamuelRousseaux May 10 '17 at 19:26
  • Yes, now imagine in each iteration, there are so many function calls, conditional branches, memory accesses etc. It is bound to take a lot of time. – Ajay Brahmakshatriya May 10 '17 at 19:30
  • Well, I guess it has to take its time so :) Thank you for your help ! – SamuelRousseaux May 10 '17 at 19:32
  • At the same time, the code can be optimized a lot. Try running the compiler with the highest optimization level, Like say -O2 or -O3. It will make your code considerably faster. – Ajay Brahmakshatriya May 10 '17 at 19:33
  • -O2 and -O3 did a really great job, 1000*1000 was 43s, now 17s ! – SamuelRousseaux May 10 '17 at 19:36
  • They optimize every nook and corner of the code with the given source. Although there may be source level optimizations too. Or even change in logic to make it faster. – Ajay Brahmakshatriya May 10 '17 at 19:37
  • I'll try to optimize the code a bit more (looking for shortcut, etc...) – SamuelRousseaux May 10 '17 at 19:40
  • Just to give an update, I did some optimization in the program, now the 10000*10000 takes only 5s ! Thanks for all ! – SamuelRousseaux May 11 '17 at 14:37
  • That is great! You could add your updated code to your questions for other readers to see if some one has similar issues in the future. – Ajay Brahmakshatriya May 11 '17 at 14:39
  • Yes, an Edit and paste the new code. Do keep the original code (the problematic one) separately above for the question to be complete. – Ajay Brahmakshatriya May 11 '17 at 14:59
  • @LeVentilo your function to find the last of stack is very inefficient. Iterating every time till the end to get the last. Why don't you just store the last index. And update it every time you push or pop from the stack. You will get even faster execution – Ajay Brahmakshatriya May 11 '17 at 15:16
  • That's exactly what I did to save that much time (i used istack in the loop) – SamuelRousseaux May 12 '17 at 09:04