cs61b实验记录（三）project 2 prim迷宫随机生成算法

Answer 1

nothing special

具体详见我的GitHub： https://github.com/BoL0150/Berkeley-cs61b/tree/main/hw1

Random对象是一个“伪随机数”生成器，它可以产生一串无穷的看起来是随机数的数字序列，调用nextInt方法获取序列中的每一个数字。

它之所以叫“伪随机数”是因为它产生的序列并不是真正随机的。我们获取不同的序列的方式是向Random的构造器中传入一个数字，这个数字被称为“seed”，如果我们用相同的seed构造Random，那么我们一定会获得完全相同的序列。

java.lang.Math中也有一个名为random()的静态方法可以生成随机数

Math.random() 方法生成[0, 1)范围内的double类型随机数；Random类中的nextXxxx(n)系列方法生成0（包括）到n（不包括）之间的随机数；

绘制地图：

从宏观上来看，主要分为这么几步：

创建一个Room类，将每一个房间当作一个对象，随机生成房间的坐标以及长和宽，然后判断房间是否重叠，

同时设置一个参数，控制房间重复生成的上限次数。 将所有生成的房间对象放在一个List中 ，因为在修建完迷宫后还需要对每一个房间与它旁边的迷宫进行打通，以便获取房间的位置和参数。

此时在房间中填GRASS以及使用两个数组的原因稍后进行解释。

我们将这一步分解来看，首先：如何在一张空的图上生成迷宫？

我们采用 prim迷宫随机生成算法 ，此算法的原理及具体实现如下：

原理：

具体实现：

生成迷宫时要注意 随机 从候选列表中选取点，否则生成的迷宫会朝着同一个方向

我们知道了如何在空的图上生成迷宫，也可以由此推断出如何在房间的周围生成迷宫

这一步没什么好说的，对每一个房间随机选取一条边上的一点向外打通，如果不符合条件（如碰到NOTHING等）就重新选取一点。

然而，此时的图中还有很多的死胡同（即三面都是墙的FLOOR），以及房间中依然是GRASS，所以我们需要填补所有的死胡同，将GRASS替换为FLOOR。

去除死胡同我们需要对每一个点，查看周围的四个点是否是WALL，然后改变这个点，再进入下一个点。这会让人想起DFS，但是原本的DFS是沿着一条路线，从一头走到另一头，对路上的每一个点都只是 依次 查看周围的点，一旦找到可以通过的点，就立马进入， 无法确定这一点周围是否有3个WALL 。只有当走到头时，扫描了周围的四个点，发现都无法通过，才会往后退。也就是说，只有后退的时候，我们才能知道某一点周围所有点的情况。而填补所有的死胡同需要我们从所有的死胡同的终点出发，向中间汇聚，一边移动一边填补。

所以我们需要将DFS改造成 前进和后退时都要查看周围所有点的情况 ，才能进行下一步。

我们还需要移除所有多余的墙，也就是四个角上没有FLOOR的WALL

最后，再添加上Player和Lock_Door就完成了

附上autograder的评分