cs61b Proj3-BYoW

Github Repo: https://github.com/HangX-Ma/cs61b-sp21

在实现这个项目之前自己先尝试摸索着做了一些工作， 构思了一下工程结构， 但确实由于项目经验较少， 很难做到 Josh Hug 课上说的 Strategic Programming， 刚开始就对 interactWithInputString 的字符串处理部分重构了多次。 既然没办法避免 Tactical Programming， 我的想法是先看看别人实现的文件架构以及构建框架， 这样能够有个比较清晰的实现脉络。

我参考的是 YinY1 的 Proj3 实现， 但我认为具体的细节是需要自己去思考的， 文件结构的设计已经给了我足够的启发。 这篇文章就详细介绍一下地图的生成， 这块难度比较高， Phase2 关于游戏交互的我就完成了基础功能没啥好说的。

最近有些焦虑， 感受到末尾保研和前位保研的差距了， 同届的同学已经参加过之江实验室的项目， 以及百度 Paddle 的夏令营， 现在在延续他的夏令营开源项目担任助教。 而对自己来说， 规划的一整个研一时间和半个研二时间是拿来补基础课程的， 毕竟平时还有实验室任务。 不过人家确实也很认真， 每天留到快 23:00 才回宿舍。 且不说了， 之后还有一门数据库的课程要补上。

1. 文件目录

byow
  ├─Core
  │  │  Engine.java
  │  │  Main.java
  │  │  Pair.java
  │  │  Point.java
  │  │  Property.java
  │  │  RandomUtils.java
  │  │  Utils.java
  │  │  World.java
  │  │
  │  ├─Avatar
  │  │      Avatar.java
  │  │      Tofu.java
  │  │
  │  ├─HUD
  │  │      Frame.java
  │  │
  │  └─Maps
  │          Road.java
  │          Room.java
  │          Wall.java
  │
  ├─InputDemo
  │      DemoInputSource.java
  │      InputSource.java
  │      KeyboardInputSource.java
  │      RandomInputSource.java
  │      StringInputDevice.java
  │
  ├─lab12
  │      BoringWorldDemo.java
  │      HexWorld.java
  │      project3prep.md
  │      RandomWorldDemo.java
  │
  ├─lab13
  │      MemoryGame.java
  │
  ├─Networking
  │      BYOWClient.java
  │      BYOWServer.java
  │
  └─TileEngine
          TERenderer.java
          TETile.java
          Tileset.java

2. Phase1: World Generation

Phase1 要求生成随机的地图， 地图要求由不同大小的 Rooms 以及联通这些 Room 的通道构成。 一般的实现办法就是生成多个 Rooms 的区块， 然后将这些 Rooms 通过 Path 联通起来， 而如何生成 Path 真的非常考验人。 我自己尝试过用类似 Hexagon World 中扫描的方式， 让每个 Rooms 紧贴着生成， 也尝试过生成 Rooms 后用生成迷宫的方式去生成 Path， 但这些方法都不能很好的做到和 Josh Hug 给出的样例类似。

花了一天的时间考虑算法， 闭门造车真的不行， 有幸刷到了这样一篇知乎 【游必有方】一种 RogueLike 地图生成算法 作者对原文 Rooms and Mazes: A Procedural Dungeon Generator 进行了简化和翻译。 第一次了解到这种 2D 场景的类似的游戏被称为 RogueLike Game， 文章介绍的内容和 Proj3 所介绍的需求非常类似。

生成地图的主要步骤：

• 在给定大小的地图区域内随机生成一些房间；
• 将除房间以外的区域用随机生成的迷宫填充；
• 将所有房间和迷宫通过少数节点连接起来；
• 删除不必要的迷宫死胡同，降低地图复杂度。

对我来说链接迷宫和房间并降低地图复杂度这块是最为困惑的和不解的， 迫不及待想要了解作者的巧妙构思了。 其实这块自然而然会想到课上介绍的 Union 的概念， 尤其是一提到联通路径的时候， 就会想到 Prim 和 Kruskal 这两个最小生成树算法。 【UE4 C++】迷宫生成——DFS、Prim、Kruskal算法实现 这篇文章介绍了几种算法在生成 Maze 时的区别， 当时我自己实现了 kruskal 的迷宫， 但效果和课程所给的相去甚远。

2.1 创建独立的 Room Areas

按照文章所述， 算法需要保证地图的宽高尺寸， 以及房间尺寸， 房间所在位置均为奇数， 这样能与生成的 Maze 路径对齐， 保证 Maze 所经过的路径与 Rooms 仅有一个 tile 的距离， 这样能够保证后续连接 Rooms 和 Maze Path 的时候的便利。

至于创建随机且不重叠的 Room Areas 的思路也很粗暴， 随机生成 Room 的尺寸以及位置， 判断生成区块是否与已存在的 Room 存在重叠， 迭代一定次数即可。 对于一个有限地图而言， 没必要迭代太多次， 越往后重叠的概率越大反倒浪费资源。 这里需要注意的一个点是, Room 之间是需要留有一个 tile 的空隙的。

Room and maze, HangX-Ma

对于 Rooms 生成我用了 Inflation 的思想， 既然需要留有一个 Tile 的间隔， 不如在生成 Rooms 时将原点位置向左下移动一个单位， 将宽和高都扩大两个单位， 想象一下一个 5x5 的格子， 膨胀为 7x7 的格子。

2.2 剩余空间填充迷宫墙

原作者基于 Karcero 尝试生成迷宫墙以及前述的房间， 发现 Room then maze 的方式会更加高效， 其实道理也非常明晰， 先生成 Maze 并进行裁剪留下的空间用以生成 Rooms 其实极大限制了 Rooms 的生成区域， 而 maze 的填充仅占用 1 个 tile， 相比较动辄几十个 pixel 开销的 Rooms 区域而言， 其发生碰撞的概率会小很多。

作者生成 Maze 的方式用了图形学中常用的 Flood Fill 算法（似乎之前听过， 但第一次系统学完数据结构还没用过）。 从一个合格的节点出发，生成迷宫， 直到这段迷宫不能继续生长为止。 然后换个合格节点继续生成， 直到整个地图被迷宫填充。

这块比较困惑的地方是如何生成用以生长 Maze Path 的节点， 作者的思路很巧妙， 他规定了整个地图的尺寸是奇数的 W x H 大小， 同样也规定了生成的 Rooms 的尺寸也是奇数的， 且 Rooms 的原点位置也是奇数， 这样在我们遍历整个地图的时候， 只要将奇数位置填充为 Wall 类型， 就能够创建潜在的生成 Maze Path 的节点， 这些节点都能够和相邻的 Rooms 对齐且相聚一个 Tile 距离， 这是非常重要的一个属性。

Essential maze path tiles, HangX-Ma

在我们遍历完整个地图后， 就能够得到充满这些潜在可能转为 Maze Path 的 Wall Tile， 此时运用 Flood Fill 算法就能生成填充 Rooms 之间间隙的 Maze Path 了。 这里的思路也是遍历整张图找之前设定的 Wall Tile， 找到之后我们在该点的上下左右四个方向中找到沿该方向行进 2 格的 Tile（保证奇数这个属性）， 这个 Tile 的属性是 Wall， 并且落在设定的地图范围内。 连接当前点和目标点时， 我们设定这些 Tiles 的属性为 Floor， 这样在遍历完整个地图后就能得到 Maze Path。

Rooms with maze path but no connections, HangX-Ma

2.3 连接 Rooms 和 Paths

此时一个重要的问题落在了面前， 如何连接 Rooms 和 Paths 使得整个地图联通。 一般来说我们都会想到用 Union 来解决这个问题， 但这里有个 trick， 我们需要将之前的各个独立的 Maze Path 视作一个单位而不单独去考虑组成 Maze Path 各个 Tiles， 所以在生成 Maze Path 的时候， 用 Kruskal Union 算法将这些组成 Paths 的 Tiles 加入联通集中， 对于 Rooms 中的 Tiles 也要进行相同的操作。 当然现在又有一个问题， 如何找到这些潜在的可成为 Passage 的 Tile？

其实和之前的思路很类似， 也是要扫描整个图， 当扫到 Rooms 和 Paths 之前的空白区域的时候我们就开始进行筛选， 检查这个节点的上下左右四个方向的相邻节点是不是不为 Nothing 属性， 如果符合条件的相邻节点的数量大于两个， 说明这是一个潜在的 Passage Tile， 加入候选的集合中。

之后我们就随机选取潜在的 Passage Connector， 如何该 Tile 还不在 Kruskal Union 中， 就将该 Tile 加入 Kruskal Union 中。

Rooms with maze path and connections, HangX-Ma

2.4 优化生成的地图

• 地图过于拥挤

  现在生成的地图和样例所给的相去甚远， 太拥挤了， 有没有办法将生成的 Maze Path 缩小一些？ 我的比较粗浅的想法就是限制之前的 Wall Tiles 锚点的位置， 在判断是否落在地图范围内的时候就直接缩小地图的比例， 例如设定一个 GEN_RATIO 的系数约束生成区域。

• Dead End 过多

  地图中出现很多死胡同是很糟心的， 这也是之前的 Maze Path 的一个重要问题， 需要一种算法去优化生成的 Maze Path 以减少死胡同的数量。 得益于之前地图的奇数尺寸的设定， 判断死胡同的方式很简单， 只需要检查这个点的邻居点是否有 3 个 Tile 的属性都是 Nothing， 这说明这个 Tile 没能够与另一个区域直接相连。

  那么， 在遍历整张图找相应的 Dead End 的时候， 我们可以将其邻居点中不为 Nothing 的点作为下一个检查点或以此为下个检查方向， 直到死胡同消失或者达到我们设定的处理次数限制后， 我们再继续遍历地图。

• 生成地图的墙

  前面将 Rooms 以及 Paths 都生成并优化了， 却发现有些灵魂缺失， 原来是关键的墙体没有生成。 再来一次暴力全图搜索， 找到不是空白的 Tile， 这次我们需要检查这些 Tile 的八邻居节点， 将这些节点中为 Nothing 属性的 Tile 设置为 Wall 属性。

最后生成的地图如下所示：

Optimized world, HangX-Ma

3. 写在最后

原来是想边写 Blog 边做 Proj3 的， 结果人懒了硬是拖了两个星期才写写成了总结。 感觉整个设计如果深挖还会遇到很多未知的困难， 但就是这样一个初具雏形的游戏却让我在初期感到束手无措， 这种感觉做 Proj2 的时候也有。 但相较于 Proj2 的严格要求， Proj3 的发挥空间和余地都很足， 难度上也简单一些。 虽然这俩 Proj 为了提升效率我都去借鉴了别人的框架， 虽然都很有收获， 但思考的机会少了。

总的来说， cs61b 给我的提升非常大， 在数据结构基础这块至少已经有了一个底子， 最近刷 LeetCode 的时候就明显感觉到学的内容能用得上， 并且很多设计思路都在实际使用的时候得到了思维上的强化。 cs61b 虽然学了很久， 但确实是一门不能急躁的课， 每个 slides 都要仔细阅读， discussion 以及 examprep 有精力有时间一定得自己独立去做， 这样印象会很深！

说一句题外话， 有些同学可能看到 cs61b 用的是 java 语言就觉得生疏， 或者日后用不着就不想学。 其实每个语言都有其各自的特性， 我有一个很明显的感受， 学完 java 的基础特性之后对面向对象的很多概念有了很深的理解， 尤其是 discussion 讲基类和子类的函数调用那块。 甚至我觉得最近很火的 Rust 有很多特性也是借鉴了 java。 当然语言这块在精不在多， 能博采众长是好事， 也需要潜心钻研不断深耕。

就写到这儿， 日后再多复习复习课件， 温故而知新！