基础 | Roguelike随机地图----洞穴类(一)

本系列为笔者初学c/c++和游戏开发时的入门博文，以算法和C/C++练习为主，不涉及到游戏开发软件(如unity，虚幻4等),适合刚入门的小伙伴一起学习探讨，欢迎在评论区留下意见。该系列重点讲述Roguelike类型游戏，在早期开发会涉及到的一些基础算法。

• 开发语言：c/c++

• 开发平台：macOS mojave / Linux

• 编译器：vs Code

一、核心内容

• 细胞自动机（Cellular Automata）

• STL库（vector，queue，list等）

• 启发式搜索

二、实现方法

一张洞穴类地图上包含两个最基本的元素：墙壁，地面。前者阻挡角色的行动，后者构成可容纳其他元素的“洞穴”。

我们最直观的的构造一个洞穴的方式，就是在墙壁中挖一个洞，这样就形成一个最简单的洞穴。但是在游戏中，一个地图往往需要一定的复杂度，来放置各式各样的元素（如怪物、陷阱、宝箱等）。因此在上述方法的基础上，我们可以通过细胞自动机算法来构造更复杂的洞穴。

由此可以形成最初的方案：

• 在大地图的墙壁上随机挖一些洞

• 每个细胞自动吞食周围一定范围内的墙壁，形成空洞

为了保证地图的随机性，我们加入一个随机数，细化后可归纳出以下的实现步骤：

1. 构建一个大地图以二维平面图表示，以二维数组存储；地图最外围一圈为墙壁不变，地图内每个点以小于0.45的概率生成墙壁，其余为地面

2. 遍历数组，对每个点执行下列规则（细胞自动机算法）：

• 对当前点，若其周围墙壁数量大于4个，则其设为墙壁

• 对当前点，若其周围墙比数量小于4个，则其设为地面

3. 遍历地图，对每个区域执行下列规则（区域为经过2之后形成的“墙壁”和"洞穴",不是单独的点，而是点的集合；启发式搜索算法）：

• 对当前区域，若该区域为墙壁且数量小于5个，则将该区域设为地面

• 对当前区域，若该区域为地面且数量小于20个，则将该区域设为墙壁

4. 遍历地图，将所有独立区域连通（也可以不连通，通过其他方式来抵达）。

三、最终成果示例

洞穴类地图的简单生成方法核心部分介绍完毕，接下来会分几章节详细讲解具体算法的实现，会给出相应的代码。欢迎有不同意见的小伙伴留言讨论。