Avoidance (maze generator in C)
I am currently writing a maze generator in C using a depth search algorithm. It works very well and I'm happy with the result, but when I push the maze dimensions too far (over 2000x2000) it gives me a stack overflow.
I know this because of the recursiveness used in the algorithm, but I really don't know how I can avoid this problem ...
Here's an example of a program in which the recursive expression occurs:
* int dirs consists of 4 randomized numbers (1, 2, 3 and 4)
x and y - coordinates on 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 is a function (others are about 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 thing iteratively using a custom stack for the stock coords. It works fine, but I can't figure out if 10k * 10k is a maze, if an infinite loop, or if it's really very long (1000 * 1000 takes 43s, 10k * 10k, I stopped the program for 1000 seconds)
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 (complete work)
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 the 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 complete code to github if anyone is interested!
source to share
Stack space is usually small and usually not enough to store the many stack frames from all recursive calls. But the heap on the other hand has a lot of space (almost all of your virtual address space).
This way, you can create your own stack that only contains the relevant data.
The cam then uses a loop while
to process each instance on the stack. Your code is the DFS version. See 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 next steps until there are no items on the stack (use a while loop).
- Move an item from the stack
- Perform an operation for this point
- Add neighbors to the stack if they satisfy the condition (similar to what you used in recursion. Hint: see when you call recursion which condition you are testing).
- Repeat if the stack is not empty.
There is another way if you want to avoid all the code but are willing to sacrifice portability.
You can allocate some space on the heap (about 100s MB) and make this call stack by setting the stack pointer to that. Then start recursion. Once the recursion is complete, return to the original stack.
Remember though, you may have to change the Threading Environment field to update the stack limit and stack base, because libraries can check them to see if the stack is at limit or overflowed.
source to share