“迷宫探险”游戏设计说明(2).txt

迷宫探险算法

                   “迷宫探险”游戏设计详细说明(2)

     __________________________________________________
     |                                                |__☆★
     |            上海财经大学图书馆  陈畅            | |_
     |          http://shchenchang.top263.net         | ||
     |    编程软件，我的原创作品(含源码和详细说明)    | ||
     |           mail:[e-mail]          | ||
     |_______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步。

如果迷宫中连一个“可延伸格子”也找不到，那么这是个好消息，因为这时候迷宫
已经建造完成了。

标记数组只是在建造迷宫的过程中用一下，然后就没有用了。我们要的只是迷宫数
组。



你是怎样知道生成的迷宫从入口至出口肯定只有唯一通路的？

通过我们建造迷宫的过程可以看出，迷宫中任何两个格子都有通路相连，而且整个
迷宫不存在回路。入口和出口只是迷宫中左上角和右下角的格子，因此从入口到出
口也一定有通路相连；又因为迷宫中不存在回路，因此从入口到出口的通路是唯一
的。



入口和出口必须在左上角和右下角吗？

看完了上面的问题，这个问题就很简单了。入口和出口可以位于迷宫的任何置。



<未完>