用C語言生成心形迷宮

用C語言生成心形迷宮

來自專欄 Neolay Coding

今天是520，送大家一顆心(#^.^#)~希望大家喜歡~biu~

本文將教大家如何用C語言生成心形迷宮。

生成心形當然要用到心形曲線方程了，比較好看的心形曲線方程是(x^2+y^2?1)^3?x^2 y^3=0，用它畫出來的心形長這個樣子，是不是很漂亮~

我們今天就要用這個心形的輪廓作為迷宮的邊界，進而生成一個心形迷宮。既然我們要用到迷宮的輪廓，那我們只生成實心的心形是不行的，我們還要生成鏤空的心形，大家可以嘗試使用不同的方法繪製鏤空的心形。

我用的方法是初始化一個表示心形範圍的數組，使用二重循環遍歷所有格點，判斷當前格點的上下左右四個方向的相鄰格點是否都還在範圍內，如果有一個方向超出了範圍，就把這個格點繪製成方塊，進而繪製出一個鏤空的心形。

!(area[i][j - 1] && area[i][j + 1] && area[i - 1][j] && area[i + 1][j]) //判斷條件

在正式講心形迷宮之前，我們先來看一個普通的迷宮，因為普通迷宮的生成方法和心形迷宮的生成方法是一樣的，只是在進行繪製的時候會有所不同。掌握了隨機迷宮的生成原理，大家就可以生成任意形狀的迷宮了~

https://www.zhihu.com/video/981416032866611200

如果讓大家把剛才看到的迷宮抽象成計算機當中的一個數據結構，通過觀察不難發現，與之對應的數據結構就是樹。我們生成這個迷宮的過程其實是一個生成樹的過程，所以我們可以把迷宮的生成問題轉換為圖的遍歷問題，因為圖的遍歷結果就是一棵生成樹。我們這裡用到的圖結構，是一個生成迷宮時常用的圖結構。從圖中可以看到初始狀態下的路徑和牆，其遍歷方式是多樣的，但每個結點只能被訪問一次。

我的方法是使用隨機隊列作為輔助的數據結構對這個圖進行廣度優先遍歷，隨機打通一些牆，最終的路徑會是一棵樹，將迷宮的入口和出口固定地設置為路徑，進而生成一個隨機迷宮。通過此種方法生成的迷宮一定有唯一通路。

大家可以通過視頻直觀的感受一下隨機迷宮的生成過程。

https://www.zhihu.com/video/981425374303068160

為了展示，我在之前視頻中所示的迷宮還加入了類似遮罩動畫的效果。一個簡單的遮罩示例如下，大家可以嘗試用自己的方式實現，並用到迷宮生成的展示中。

https://www.zhihu.com/video/981423606424858624

我使用的方式是對於當前沒有遍歷到的格點不給予顯示，隨著遍歷的進行逐個顯示出已遍歷到的格點。

對於迷宮的求解，相信大家在數據結構課上都已經學習過，這裡就不詳細展開描述，其本質仍然是圖的遍歷問題。所謂走迷宮的過程，其實就是從圖的某一個結點到達另外一個結點，如果遍歷完成之後仍沒有到達預設的終點，說明迷宮是無解的。對於評論區里提到的廣度優先遍歷，我也做了兩個不同版本的演示，需要注意的是，廣度優先遍歷得到的路徑需要記錄前驅結點。

我這裡使用的是遞歸的方法繪製出廣度優先遍歷出的迷宮路徑，大家可以自己嘗試實現。

https://www.zhihu.com/video/981428261666013184 https://www.zhihu.com/video/981429054305644544

另外還可以與深度優先遍歷的版本進行比較，注意演示的時間不代表演算法的運行效率。

https://www.zhihu.com/video/981429371600486400

深度優先遍歷和廣度優先遍歷的搜索策略是不同的。深度優先遍歷儘可能地先對縱深方向進行探索，直到走到死胡同才回頭，通常使用棧這種數據結構，後入先出；而廣度優先遍歷輻射狀地遍歷其周圍較廣的區域，直到最終在某一條搜索路徑上找到迷宮的解，可用於求最短路徑，通常使用隊列這種數據結構，先入先出。這兩種遍歷方式使用了不同的數據結構，在視頻演示中可以直觀地看出其各自特點。

對於評論區以及私信中提到的控制台顏色問題，在控制台屬性中設置即可。

另外關於控制台屏幕閃爍的問題，可以通過清屏和隱藏游標的函數來解決。

可參考以下兩個函數

void gotoxy(int x, int y);void hideCursor();

完整代碼已上傳至github，歡迎star，歡迎fork~

我也是才學數據結構，代碼難免有不足之處，如發現任何bug或有其他修改建議，歡迎和我聯繫~

neolay/HeartMaze?

github.com

我的相關回答

你看過／寫過哪些有意思的代碼？?

www.zhihu.com

文章轉載請註明出處~

最後祝大家520快樂(*^▽^*)！

推薦閱讀：