設(shè)計要求

? ? ? ?生成類似如圖n行m列的迷宮，起點為（2，1），終點為（n-1，m），用C/C++原因設(shè)計自動尋路算法并可視化尋路過程。

基礎(chǔ)功能：生成隨機迷宮/從文件讀取迷宮/自動尋路

進階：尋找最最短路徑/手動操控迷宮/帶有怪物的迷宮/含有倒計時的迷宮

底層數(shù)據(jù)結(jié)構(gòu)

? ? ? ?迷宮最重要的是地圖，我們存一個int Map[N][N]數(shù)組，表示迷宮在Map[i][j]表示i行j列是什么，我讓i和j從1開始，最左上角是(1,1)，第二行第一個是(2,1),第一行第二個是(1,2)，以此類推，當(dāng)然你也可以從0開始。

? ? ? ?在程序開頭對不同物品進行宏定義可以增強程序可讀性，當(dāng)然也可以用枚舉類型。我的上下左右定義的數(shù)字和方向數(shù)組下標相同，進一步簡化程序。

生成迷宮（kruskal最小生成樹）

? ? ? ? 如圖，令紅點永遠為墻，白點永遠為路，當(dāng)然還要初始化起點終點。藍點為可能存在的邊，抽象為一張網(wǎng)格圖，給每條邊加上隨機的邊權(quán)，用最小生成樹算法打通藍邊，可以在最后再隨機額外打通幾條邊。這樣雖然不能生成某些類型的地圖，但是容易實現(xiàn)并且地圖美觀，還不會產(chǎn)生大量道路聚集的區(qū)塊。代碼較長，可以在最后完整代碼的random_map()函數(shù)里看

打印地圖

我們需要用到一些不常見函數(shù)，比如隱藏光標，移動光標，清空命令行現(xiàn)實內(nèi)容等。

注意打印地圖的時候不要每次都全清空，不然會閃爍，也不要每次全打印，否則輸出耗時過久，我用了putchar輸出優(yōu)化，但是最重要的還是每次打印只在有變化的地方修改，建議寫一個在你的坐標(x,y)處打印的函數(shù)，計算好你的坐標如何調(diào)整到命令行光標坐標

自動尋路（dfs）

? ? ? ? 主要用到遞歸回溯的方法，如果走到終點就結(jié)束遞歸，如果回溯，說明后面的路線均為死路，要把地圖標記為Fail，注意遞歸和回溯的時候都需要打印地圖，另外打印地圖前一定要用Sleep(100)函數(shù)暫停100毫秒，可以很好地顯示過程，不然一瞬間就跑完了。具體dfs不細講了，如果無法理解的話可以找點視頻或者問問身邊的大神。

? ? ? ? 這里用到一個重要技巧，就是方向數(shù)組枚舉四個方向，主要枚舉四個方向的時候一定要判斷下一個點是否合法，在之后任何需要移動的地方，都要記得判斷！

我這里輸出“Me”物件的代碼位置可以微調(diào)，來改變結(jié)束時，終點處打印的是"End"還是“Me”

手動迷宮

主要用到了讀取鍵盤的函數(shù)，注意讀取上下左右鍵的時候回讀到兩個量，其中第一個應(yīng)該忽略，因此我寫了自己的讀取鍵盤函數(shù)。在讀鍵盤之前清空緩沖區(qū)，可以有效避免之前額外按鍵的影響，比如你想實現(xiàn)一個結(jié)束后按任意鍵繼續(xù)，但是你在看它自動走的時候隨便按了下鍵盤，等他走完之后，就任意鍵繼續(xù)的功能就會受到影響。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?getch()是讀取鍵盤按鍵，在下圖頭文件中

主要程序可以用一個while(還未到終點)繼續(xù)走;來實現(xiàn)，讀取鍵盤的時候，如果讀到合法按鍵，就產(chǎn)生功能，上下左右方向鍵的值可以在我的代碼里面看。你也可以加入額外功能，比如esc退出，r重玩，z撤銷......

最短路徑

? ? ? ?主要用了bfs，用隊列來實現(xiàn)廣度優(yōu)先搜索，每個點只入隊列一次，設(shè)點數(shù)有N=n*m個，則時間復(fù)雜度為O(N)。同樣如果不了解bfs的話建議自學(xué)一下，dfs和bfs都是計算機專業(yè)重要基礎(chǔ)算法。

? ? ? ?記錄路徑的話可以用到類似dijstra最短路的方法，更新下一個點的時候記錄前驅(qū)predecessor，注意到前驅(qū)數(shù)組是一個二維的點到二維的點的映射，可以開一個二維的pair<int,int>數(shù)組，如果是C語言，可以寫一個結(jié)構(gòu)體Pair，然后開一個結(jié)構(gòu)體數(shù)組。

? ? ? ?記錄完前驅(qū)之后需要從終點一直沿著前驅(qū)倒退回到起點，并在地圖上記錄上一個點到這個點的方向是什么。

? ? ? ?最后再從起點開始走，如果枚舉四個方向，沿著已經(jīng)被標記過方向的路線一遍打印一遍走到終點。

怪物游走

? ? ? ? 由于存在怪物，之前生成的迷宮很難走通，因此我只允許從文件讀入怪物地圖。

? ? ? ? 這里需要用到計時函數(shù)以及鍵盤按下事件，怪物每過多少時間動一次，循環(huán)記錄時間的同時檢測是否有按鍵按下，如果有，則讀取一個，這里不要清空緩沖區(qū)，不然會不太靈敏，我也不清楚為什么。每次移動完之后需要判斷你和怪物是否相鄰/重合。

這里還要附上怪物迷宮地圖，我也沒有仔細設(shè)計可玩性較強的地圖，就隨便整了兩個。

完整代碼

? ? ? ?到這里，主要的內(nèi)容已經(jīng)講完了，我們還需要設(shè)計Menu界面來完善功能，我寫這個程序只花了一天，大概6小時，就做的不是很完善，可能還有不少bug，歡迎大家發(fā)現(xiàn)我的bug，也可以補充更多的內(nèi)容。最后附上完整源代碼。

感謝大家閱讀！