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

Question

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

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

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

*int dirs 由 4 个随机数字组成（1、2、3 和 4）

x 和 y 是地图坐标

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

还有up函数（其他都差不多）：

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 需要 43 秒，10k*10k 我在 1000 秒时停止了程序）

有什么可以优化的吗？这是新代码：

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

以及新的 up 函数：

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：使用自定义堆栈的工作迭代程序（完全工作）

这是最终代码的示例！

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

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

因此您可以在那里创建一个自定义堆栈，其中只包含相关数据。

然后您可以使用 while 循环来处理堆栈中的每个实例。您的代码是 DFS 的一个版本。查看如何在没有递归的情况下进行 DFS。

基本思想是从一个空堆栈开始，然后将第一个坐标压入其中。

然后重复以下步骤，直到栈中有元素（使用while循环）。

从堆栈中弹出一个元素
对该点执行操作
如果邻居满足条件，则将它们添加到堆栈中（类似于您在递归中使用的内容。提示：看您何时调用递归，检查什么条件）。
如果堆栈不为空则重复。

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

您可以在堆上分配一些 space（100 MB 的数量级）并通过将堆栈指针设置为它来使其成为您的调用堆栈。然后开始你的递归。递归完成后切换回原始堆栈。

请记住，尽管您可能必须更改线程环境块的字段以更新堆栈限制和堆栈基数，因为库可能会检查它们以检查堆栈是否在限制内或已溢出。

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

Avoiding stack overflow (Maze generator in C)

c

stack-overflow

maze