制作背景

大一结束的暑假经常喜欢写各种程序，有一天，好友 Rutubet 要求我们两个人进行一场编程比赛，比赛的内容是：用自己熟悉的语言做一个游戏：生成二维随机俯视地形，能够让主角在地形中进行移动，地图由“墙体”、“空气”方块组成，就像“Minecraft”一样，只不过是二维的，像“推箱子”小游戏的那种地形。选做内容是：保存地图，读取地图，新的方块，生成处处可达的地形。比赛时间是两个小时。

生成处处可达的地形的意思就是说，比如在一个推箱子中游戏关卡中，每一个空气方块都是主角能够到达的地方，地图里没有一个“空穴”，就是没有一个封闭的、进不去的地方，处处都是连通的。（这一项本来是必须做的，但是考虑到了时间和难度，我们都同意将它改为选做了）

我们两个人在比赛内都没做这个处处可达的效果，但是我在比赛时间外经过一番思考，增添了这个功能。

主要思路

对于处处可达的地形生成，我是这样做的（没有参考任何相关资料，自己设计的，可能有不妥的地方）：

做一个能够判断地形是否是处处可达的判断函数，这个函数实现后，生成地形的时候就很轻松了。

生成地形的时候就在一个全是空气的地图里的随机位置上丢一个墙体，然后调用这个判断函数，如果丢一块墙体这个操作使得整个地图由通达状态变成了不通达状态，就“撤销”这一步操作，即把丢到的位置改为空气方块。

（后来我在做成功的时候，又想到了一种效果，那就是可以直接丢一个2x2的大墙体，或者一个更大的接近圆形的墙体块作为每次丢的内容，甚至还可以丢各种形状的大墙块，只要丢的大墙块本身自己不是闭合的，就可以，比如说丢一个空心的o形墙就不行。在撤销的时候，会直接把这个丢的内容中含有墙的方块对应的地图上的位置变成空气方块，可能丢的内容有一部分已经在墙上，有一部分不在墙上，但是这一丢导致了地图变成了非处处可达状态，于是就会把刚刚丢在空气里的和丢在墙上的墙体都变成空气，即：会出现撤销的时候会把墙直接吃掉一部分的这种效果，不过这并不影响处处可达的结果，反而我觉得这就是我想要的效果）

上述步骤执行很多很多次，每丢一个方块就判断一次处处可达，等到丢的方块非常多的时候，就生成了一个处处可达的地形了。（我知道这样很费时间，但是我认为这是非常好想到并且比较容易实现的方法了，我于是抱着看看效果的心态先就做出来）

那么接下来的重点就放在实现那个地形处处可达的判断函数了。

在想判断函数的时候我想到了一幅画面，在空气方块中滴一滴墨水，这个墨水开始向四周扩散，但是会受到墙体的阻碍，等墨水扩散完毕了之后，如果所有的空气方块都被墨水所侵染，那么整个地图就是处处通达的，否则就说明有的地方墨水无法触及，整个地图不是处处通达的。

根据上面的想法，只要遍历整个地图里的每一个方块，只要一找到空气方块，就开始执行“滴墨水”的操作，实时统计被墨水感染的方块的数量，如果被墨水感染的数量等于空气方块的数量，那么判断函数就通过了。

那么接下来的重点就放在怎么实现墨水扩展上了

我们把每一个被感染的空气方块想象成一个“哨兵”、“传播者”或者“拓荒者”。（也许是因为高中英语有一个这个单词记忆的比较深刻，所以就给变量名这么取名了），这个拓荒者是一个类对象，它有很多的属性和功能。

首先它能向周围（给上下左右四个格子，不能斜着）传递信息，让更多的拓荒者诞生，那么我们就给它一个directions属性，用来表示它接下来会向哪个方向发射信息，这时候就有问了，每个拓荒者不都是向周围四个方向上发射信息吗？不用这个属性也无妨。但是这只是第一个拓荒者，它是向四个方向传播的，第二代拓荒者就不是了，第二代拓荒者中位于最开始拓荒者右边的新的拓荒者它就没有必要再往左侧传递信息了，（因为它就是从左边传来的信息诞生出来的，所以它只需要向右，上，下三个方向传递信息。）

拓荒者有以下属性：

• 位置（表示自己在地图中的作标位置）

• 是否是第一个拓荒者isFirst（第一个拓荒者比较特殊，因为它的传播方向有四个，其他的都是三个）

• 受到的信息massage（表示这个拓荒者是从上一个拖航这的哪个方向上传来的，这属性决定它接下来发消息的三个方向，如果是第一个拓荒者，那么它没有收到消息，就用(0, 0)来表示没有）

• 接下来的传播方向directions（一般是三个，但是如果是第一个拓荒者，那么它就有四个方向）

• 是否工作isWorking（用来在接下来迭代的过程中方便遍历每一个拓荒者用）

整个传播的过程需要三个一维列表，也用于表示拓荒者的三种状态：

1. workingPioneerArray：里面存放正在工作中的拓荒者，每次遍历的时候只遍历这个数组就可以了

2. pioneerArray：里面存放工作完成的拓荒者，最终统计数量的时候直接len这个列表就可以了

3. nextWorkingPioneer：里面存放下一步中才开始执行工作的拓荒者，也就是当前一步中刚诞生的

还需要一个二维数组，这个二维数组和地图一样大，相当于又建立了一个只表示拓荒者有无的图层：

• pioneerFlag[Y][X]：里面存放所有不同状态的拓荒者，这个用于防止拓荒者传播的时候出现两个拓荒者重复站在一个位置上

接下来

只要循环直到没有工作中的拓荒者了，就结束了，循环执行什么操作呢？

循环遍历执行每个拓荒者的传播操作，就是遍历每一个拓荒者的传播方向属性，如果这个传播方向上的对应的位置上既不是不可走上去的墙体，同时在pioneerFlag对应位置上没有拓荒者，满足这两个条件就可以让这个位置上的拓荒者诞生，并让诞生的拓荒者添加到nextWorkingPioneer。怎么让拓荒者诞生？就创建一个新的拓荒者类的实例，传入相应参数就可以了，但是注意需要根据massage属性来确定它接下来的传播方向

遍历结束后需要对三个列表进行内容上的修改：

• 每遍历结束一个拓荒者，这个拓荒者的工作就结束了，让它的isWorking属性改为False，并将它添加到pioneerArray。

• 每迭代一次，即遍历完所有工作中的拓荒者一波，就需要让nextWorkingPioneer中的拓荒者覆盖workingPioneerArray，并清空nextWorkingPioneer中的拓荒者。

详细信息可以看代码

效果截图

源代码

此源代码为整个项目的所有源代码

总结与反思

我的这种算法时间复杂度太大，空间复杂度也不小，因此还需要改进。

我还需要学习一些相关算法知识，纯自己做出来的感觉有些地方可能有点冗余。