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