避免堆棧溢出（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數百順序）一些空間，並通過設置堆棧指針到您的調用堆棧。然後開始遞歸。遞歸完成後，切換回原始堆棧。

但請記住，你可能需要改變線程環境塊的字段更新堆棧限制和棧基，因爲庫可以檢查對他們檢查堆棧的限制，或溢出。