一段時間之前看了 computerphile 的 Maze Solving 影片，在走迷宮的演算法外，更好奇那些迷宮是怎麼生成出來的。就試試用最單純的 DFS 來實做看看。然後用函式庫將其輸出成圖片，能比較清楚地看到結果。

資料結構

先將迷宮視為一堆格子組成的二維陣列，每個格子紀錄自己左邊與上方是不是有牆壁，如此一來就不需要紀錄重複的資訊。

Depth First Search (DFS)

先隨機選擇一個格子作為起點，以相同的機率向四周生長，直到無路可走，才退回上一格，一直到所有格子走過為止。在此有兩種退回的方法：

1. 退回前一格
2. 退回上個轉角

後者可以減少 DFS 需要的深度，但可能會影響格子是否有分岔的機率（？

直接將結果印出會像是這樣：

#########################################
#     #       #           #   #         #
### # ####### # ### ##### # # ######### #
#   #       # # # #     # # #   #     # #
# # ####### # # # ##### ### ### # ##### #
# # #         # #     #     # #   #     #
# # ########### ### ######### ##### # ###
# # #     #   #   #               # #   #
# ### # ### # ### ############# # ##### #
#     #     #                   #       #
#########################################

輸出為圖片

一開始是使用之前在繪圖程式設計時用到的 stb 圖片函式庫，可惜的是他並沒有辦法輸出 gif，也就無法輸出迷宮生成的過程。

Google 了一下找到了 gifenc 能夠輸出 gif ，不過因為他是純 C 的函式庫，使用 g++ 編譯時會有語法上的問題，所以在使用時必須在 .cpp 中宣告：

extern "C"{
    typedef struct ge_GIF {
        uint16_t w, h;
        int depth;
        int fd;
        int offset;
        int nframes;
        uint8_t *frame, *back;
        uint32_t partial;
        uint8_t buffer[0xFF];
    } ge_GIF;
    ge_GIF *ge_new_gif(const char*, uint16_t, uint16_t, uint8_t*, int, int);
    void ge_add_frame(ge_GIF*, uint16_t);
    void ge_close_gif(ge_GIF*);
}

並事先使用 gcc 將函式庫編譯成物件檔，在編譯時再將物件檔與主要的 cpp 檔一起編譯。

g++ -std=c++17 main.cpp gifenc.o -o dfs

邊界限制

在生成迷宮時必須要不斷檢查是否跑出邊界，在最簡單的情況就是長寬的範圍，但如果使用圖片來作為限制會有什麼樣的結果呢？

試試噗浪的logo

這次碰到的新東西

1. 將函式的遞迴呼叫轉為使用堆(stack)實做

   一開始寫的 DFS 是用遞迴硬幹，結果迷宮開大一點就 stackoverflow 了。觀察下每個階段使用到的資訊，然後改成用 stack 來實做以避免不必要的函式呼叫，這也讓迷宮的大小可以開到超過 100x100 。

2. 在 C++ 中使用純 C 的函式庫

3. 使用 C++17 的一些新東西：

   • if constexpr : 控制編譯的模式
   • auto [a, b] = f() : 一次回傳兩個值