“迷宮探險”游戲設計詳細說明(2)

     __________________________________________________
     |                                                |__☆★
     |            上海財經大學圖書館  陳暢            | |_
     |          http://shchenchang.top263.net         | ||
     |    編程軟件，我的原創作品(含源碼和詳細說明)    | ||
     |           mail:shufechenchang@263.net          | ||
     |_______QQ:7019717(歡迎編程愛好者加我為好友)_____| ||
       |________________________________________________||
     ☆☆|_______________________________________________|




關于“迷宮探險”程序的一些問題：
******************************************************

Turbo C 中怎樣設置圖形顯示？
Turbo C 中常用圖形函數的用法？
怎樣獲取鍵盤輸入？
迷宮的數據表示法？
怎樣隨機生成一個從入口至出口只有唯一通路的迷宮？
你是怎樣知道生成的迷宮從入口至出口肯定只有唯一通路的？
入口和出口必須在左上角和右下角嗎？
迷宮通路的數據表示法？
怎樣才能找到從入口到出口的那條唯一通路？
對我程序的注解。

******************************************************


■迷宮的數據表示法？

迷宮由二維數組表示，具體圖例及說明請參見本文所附帶的“迷宮圖解.xls”文件
中的“迷宮的坐標及表示”工作表。



■怎樣隨機生成一個從入口至出口只有唯一通路的迷宮？

做法如下：

建立兩個二維數組，一個是迷宮數組，用來表示迷宮中各格子的狀態；另一個是標
記數組，在標記數組中用0和1來區分迷宮中未鋪設過道路的區域和已鋪設過道路的
格子。標記數組初始全為0。

★第1步：從迷宮中任選一個格子，把這個格子稱作“當前格子”。

★第2步：
將標記數組與當前格子坐標相同的元素標記為1，表示這個格子已被用來鋪設迷宮
道路。

★第3步：

如果從迷宮中的一個格子已經是道路中的格子，同時存在與這個格子相鄰的(在當
前格子上、下、左、右的)、未鋪設過道路的格子，就把當前格子稱作“可延伸格
子”；否則稱這個格子為“不可延伸格子”。

一個格子是“可延伸格子”還是“不可延伸格子”，可以通過檢驗標記數組來判斷
。

如果當前格子是“可延伸格子”，那么從與當前格子相鄰的、未鋪設過道路的格子
中任選一個格子，做為迷宮道路延伸的下一個格子。把這個格子稱作“新格子”。

	分四種情況。四種情況及相應的處理如下：

	☆新格子在當前格子的左邊：
		將迷宮新格子的狀態標記為2。

	☆新格子在當前格子的上邊：
		將迷宮新格子的狀態標記為1。

	☆新格子在當前格子的右邊：
		如果當前格子的狀態為0，則把當前格子的狀態標記為2；
		
否則，把當前格子的狀態標記為3。(想一想，為什么？實事上，如果這時
當前格子狀態不為0，必定為1。)

	☆新格子在當前格子的下邊：
		
		如果當前格子的狀態為0，則把當前格子的狀態標記為1；
		
否則，把當前格子的狀態標記為3。(想一想，為什么？實事上，如果這時
當前格子狀態不為0，必定為2。)

處理完成后，把新格子設為當前格子，返回第2步。

如果當前格子是“不可延伸格子”，那么從迷宮中所有“可延伸格子”中任選一個
格子，把這個格子設為當前格子，返回第2步。

如果迷宮中連一個“可延伸格子”也找不到，那么這是個好消息，因為這時候迷宮
已經建造完成了。

標記數組只是在建造迷宮的過程中用一下，然后就沒有用了。我們要的只是迷宮數
組。



你是怎樣知道生成的迷宮從入口至出口肯定只有唯一通路的？

通過我們建造迷宮的過程可以看出，迷宮中任何兩個格子都有通路相連，而且整個
迷宮不存在回路。入口和出口只是迷宮中左上角和右下角的格子，因此從入口到出
口也一定有通路相連；又因為迷宮中不存在回路，因此從入口到出口的通路是唯一
的。



入口和出口必須在左上角和右下角嗎？

看完了上面的問題，這個問題就很簡單了。入口和出口可以位于迷宮的任何置。



<未完>