避免堆栈溢出（C中的迷宫发生器）

Question

我目前正在使用深度优先搜索算法在C中编写迷宫生成器。它运行得非常好，我对结果很满意，但是当我将迷宫的尺寸推得太远（超过2000x2000）时，它给了我一个堆栈溢出。

我知道这是由于在算法中使用的递归性，但我真的不知道我该怎么避免这个问题...

这里就是递归发生程序的示例：

* INT 显示目录由随机化的4个数字（1，2，3和4）

X和Ÿ在地图上都

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); 
    } 
} 

的坐标，并有高达功能（其他的都几乎是相同的）：

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); 
    } 
} 

编辑： 所以我也做了同样的迭代，用定制堆栈来存储坐标。它工作的很好，但我不知道如果10k * 10k迷宫如果无限循环，或者如果它真的很长（1000 * 1000需要43s，10k * 10k我在1000s停止了该程序）

反正有我可以优化它吗？ 这里的新代码：

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; 
    } 
} 

而新兴起来的功能：

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); 
} 

编辑：工作迭代程序自定义堆栈（全工）

这里是一个样本最终的代码！

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); 
    } 
} 

和高达功能

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); 
} 

我可以上传的完整代码在GitHub上，如果有人感兴趣的！

Answer 1

堆栈空间通常很小，并不足以容纳来自所有递归调用的大量堆栈帧。但另一方面堆有很多空间（几乎所有的虚拟地址空间）。

因此，您可以创建一个自定义堆栈，其中只保存相关数据。

然后，您可以使用while循环来处理堆栈上的每个实例。您的代码是DFS的一个版本。查找如何在不递归的情况下执行DFS。

基本的想法是，你从一个空的堆栈开始，并推动它的第一个坐标。

然后重复以下步骤，直至有堆栈上的元件（使用while循环）。

1. 从栈中弹出一个元素
2. 执行操作这一点
3. 添加邻居到堆栈中，如果他们符合条件（类似于您在递归使用什么提示：见你什么时候打电话递归，你检查什么条件）。
4. 重复如果堆栈不为空。

还有另一种方法，如果你想避免所有的代码，但准备牺牲可移植性。

您可以在堆上分配（MBS数百顺序）一些空间，并通过设置堆栈指针到您的调用堆栈。然后开始递归。递归完成后，切换回原始堆栈。

但请记住，你可能需要改变线程环境块的字段更新堆栈限制和栈基，因为库可以检查对他们检查堆栈的限制，或溢出。