本系列为笔者初学c/c++和游戏AI开发的学习经历，练习为主，不涉及到具体的游戏开发软件学习(如unity，虚幻4等),适合刚入门的小伙伴一起学习探讨，欢迎在评论区留下意见。

• 开发语言：c/c++ (11及以上)

• 开发平台：macOS mojave / Linux

• 编译器：vs Code / g++

本章节知识点：

• queue

• list

• 启发式搜索

3.处理地图

3.1 启发式搜索

启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

----百度百科

严格意义上，前两个步骤已经可以生成一张完整的随机洞穴类地图，但这样生成的地图或多或少会出现一些细小的洞穴或者墙壁，不够美观。

因此我们可以通过启发式搜索，来找出需要的某类区域，实现方法可归纳为：

1. 对某个点，若其上下左右四个点中有符合条件的点，则将该点(该点是上下左右四个点之一)加入搜索队列，否则丢弃；

2. 从搜索队列中取出一个点，执行1的操作；

3. 重复1和2，直到队列为空，也就是一定区域内再也找不到符合条件的点为止。

这样，我们通过启发式搜索，就可以将地图中某一类区域全部标记出来，如图1所示：

3.2 代码实现

首先，我们将处理地图分为两个操作，一是清除数量小于5的墙壁；二是清除数量小于15的地面，如图2所示：

其中，清除区域的函数processRegion(),如图3所示：

• pointType: 要清除的区域的标记，1为墙壁，0为地面

• thresholdSize: 要清除的区域的大小

• !pointType：清除方式为，若是1则改变为0，反之亦然；

其中，通过getRegions()函数获取指定区域的集合，如图4所示：

代码实现如图5,图6：

• Coord：自定义结构体，用来存储地图上的具体的某个点的xy坐标值，如图5所示
  

• regions: 二维列表，其形式为 [[区域1的全部点]，[区域2的全部点]]

• mapFlags：计算过程中对地图上的点进行标记

• getRegionPoints函数：计算具体的某个区域的全部点

最后，getRegionPoints函数具体计算哪些点是属于同一个区域，如图6所示：

• queue队列：存储下一步需要搜索判断的点，从上下左右四个点中选择

• points列表：存储属于某个区域的全部点，最后返回该列表

到这里，一张可用于Roguelike游戏的洞穴类地图已经基本生成完成，后续便可以往洞穴里面添加各种元素，如陷阱、宝箱、怪物等。

当然到这一步，地图上是有可能存在互不相通的多个洞穴区域的(如图4)，我们可以往洞穴中放入传送点来实现两个洞穴区域的连通，也可以继续通过算法来在不同洞穴区域之间生成可以通过的“道路”。

不同区域之间的连通算法有很多种，大多可以归纳到迷宫算法里面，下一章节笔者将运用相似的思想，来简单实现不同区域的连通方法。

参考：https://www.youtube.com/watch?v=xYOG8kH2tF8

相关代码下载：https://github.com/linpeijie/GameToy/tree/master/GameAI/Map