c - 避免堆栈溢出(C 中的迷宫生成器)

Question

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

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

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

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

x和y是 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);
    }
}

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

编辑:使用自定义堆栈的工作迭代程序(完整工作)

这是最终代码的示例!

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. 如果堆栈不为空，则重复此操作。

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

您可以在堆上分配一些空间(大约 100 MB)，并通过将堆栈指针设置为您的调用堆栈。然后开始你的递归。递归完成后切换回原始堆栈。

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