2D-六边形瓦片地图的随机生成
发表于2018-08-18
好久不见。
这是第16篇与游戏开发有关的文章。
| 写在最前
最近在工作之余挤出些时间完成了2D-六边形瓦片地图的随机生成，在此做一下总结（特别是将犯过的错误也记录下来）。
需要提前声明的是，本文只对思路进行了梳理，并不包含任何代码，并且只适用于2D六边形(或四边形)瓦片地图。
| 初衷
当时虽然简单实现了目的，但后来自己也感到世界地图的呈现并不十分完美，恐怕也就只值95分。为了精益求精且给自己找点事做，便想对大地图的呈现方式做些微调。
之前略有瑕疵的世界地图
| 为何选择2D
素材好找，地图较大时绘制的开销也不会很大。
| 为何选择六边形瓦片
组合种类多，且六边形的表现效果略好于四边形（个人感觉）。
其实，最主要的原因是木有素材，在Unity商店中找了一圈后发现选择实在不多，因此最终决定使用2D+六边形瓦片地图的表现形式。我是从素材出发调整项目，有点本末倒置实属无奈。
我选择了一套很精致的六边形瓦片，结合这套素材的特点，我对组成地图的瓦片进行了简单的分类。
使用上述瓦片组成的地图，除了具备了一般瓦片地图的特点外，还会根据地块间的连接情况，显示道路。
| 想要实现的目标
1、指定尺寸后生成地图，地图上随机分布着各种类型的地块。
2、英雄随机出生在城市里，会自己选择目的地并进行探索。
3、可通行的地块间有道路相连。
由于英雄的探索逻辑之前的文章已经阐述过，这里就不再赘述，本文重点介绍地图的随机生成。
请先看下最终随机生成的效果
雪地
沼泽
森林
沙漠
| 名词解释
先做一下名词解释，以便后文理解：
格子：可想象为插地块的槽，如5x5的地图，在初始化时会有25个空的格子等待用地块填充。
地块：一个被确定了用途的格子，可以是一个城市、村庄或是一座山等，注意它只是数据，并不能直接显示。
瓦片：配合地块显示的图片，如这个地块是城市，便会在上面放置一个城市的六边形瓦片(图片)。
功能地块：城市、村庄、可探索地块。
普通地块：可以通行但并没有功能的地块，也是唯一可铺设道路的地块。
障碍地块：不可以通行也没有功能的地块。
配合图片更易理解
| 走过的弯路
起初，我的思路是：
1、随机生成若干障碍地块。
2、随机生成功能地块，并在生成时随机通行方向。
3、遍历1～2步生成的地块，围绕它们生成普通地块，并在生成时随机通行方向。
4、遍历所有普通地块，遍历时检查围绕它的六个地块，若周围地块存在道路，但无法与当前被遍历的地块连接(通过寻路器判断)，则连接它们(通过寻路器连接)，以保证所有地块之间都是相通的。
随机地图生成的步骤图
1~3:生成基本地块
4:连接地块
围绕中心生成普通地块并随机通行方向
| 存在的问题
地图虽然是随机生成，但是道路混乱，很多路口的连接毫无逻辑，与现实中道路的情况有差距。
通过上图不难发现，地图上总会存在些莫名其妙的岔路，不仅影响美观，同时会在一定程度上加大寻路的尝试次数。
经过几次尝试后，最终还是从鲁迅先生那里找到了一些灵感，想到了解决方法。
| 他是这样讲的
不好意思，弄错了，应该是下面这句。
| 两个关键点
1、道路的存在是为了连接目的地，因此不如尝试从结果出发。
2、人生并没有很多次可以选择的机会，只会在几个岔路口中作出选择，并一直走下去，直到终点。
| 调整后的生成步骤
1、随机若干城市、村庄、探索地块
从结果出发，生成一定数量的功能地块，随机分布在地图上。
2、随机若干岔路
注意，岔路是普通地块。
3、连接岔路和功能地块
遍历每个岔路，连接离它最近的城市、村庄或探索点。此举的目的是为了将整个地图分割成几个相对独立的小块，也保证了每个目的地只有一条通路可以到达。
4、清除没有连接功能地块的岔路
移除没有用到的岔路，是为了避免后期连接时出现太多道路分支。
5、就近连接岔路
将此前分割的几块小地图连接起来，我使用的方法是：遍历每一个岔路，并查找与其最近的普通地块，如果通过寻路无法到达，则连接它们。
6、做一次连接检测
选择从一个功能地块出发，尝试到达其他所有的功能地块，如果都可以联通即为通过；如果发现有联通失败的功能地块，可以选择找到连接这个功能地块的岔路，重新做一次步骤5，或重新随机生成一次地图。
7、补齐剩余的地块
遍历所有格子，找到没有填充地块的格子，全部填充为障碍地块。
8、根据地块类型及信息，铺设瓦片
连起来看一遍
| 修改后的优点
每个功能地块只有一条路可以到达，地图整洁，分支少，也提升了寻路效率。
| 不足之处
1、一些道路和功能地块的连接关系可能存在不自然
可通过设置每一种瓦片的通路方向解决这个问题。
2、在为障碍地块放置瓦片时风格过于零散
可通过调整随机方式或增加二级瓦片风格解决这个问题。
将不能玩的小游戏的大地图替换后的局部表现
至此，英雄可在新地图中愉快的玩耍了，他们很开心，就像过年了一样，恭喜。
| 其他
除了上述主要内容外，还有些琐事没有记录在正文内，就写在下面吧。
| 瓦片遮挡关系
本文跳过了很多内容，比如在铺设瓦片时如何调整瓦片间的遮挡关系。因为它们并非本文想要说明的重点，而且比较容易实现，就没有做详细的说明。我使用简单粗暴的SortingLayer+OrderInLayer的方法来控制，只是道路需要特殊处理一下，注意一下瓦片所在行即可。
| 寻路器
地图寻路器至少应该具备以下两个功能：
1、传统寻路
在已经铺设好地块的地图上进行寻路，并没有什么特别之处。
2、铺路
可以从目的地到终点进行铺路，在地图没有构建好之前会被经常使用，它的原理是在传统寻路中，对地块采用较特殊的处理方式：
当格子里有地块信息时，如果这个地块是功能地块，则统一认为是障碍地块，无法通行，以避免破坏之前生成的功能地块；
当格子里的地块是普通地块或没有地块信息时，则均认为是可以六向通行的普通地块。
铺路得到的结果，是考虑绕过了功能地块的最近路径，因为一个功能地块只能有一条通路到达；反之如果允许铺路结果通过功能地块，那么功能地块可能会变成一个岔路，看起来会很乱。
调用铺路的地方可根据寻路结果，按照路径及通路方向生成新的地块或重构普通地块的通路情况，以实现从目的地到终点的联通。
| 寻路的优化
在这我使用了A-Star寻路，六边形与四边形并没有什么差别，只是多了两条边而已。
网上有很多关于A-Star的介绍，这里就不再赘述，只是说一下我做的修改，可以稍微提高一些寻路速度。当然，如果你一点都不了解A-Star，跳过这段即可。
1、移除了关闭列表。
我为每个地块设置了一个通用的对象位置，这样在判断某一个地块是否为关闭时，只要尝试访问这个地块上保存的对象即可，可以减少一次遍历操作。
2、尝试记录一个此好的选择
在将一个地块周围的地块加入开启列表时，会尝试记录一个次好的选择。当最好的地块已经走不通时，无需从开启列表中循环遍历来挑选下一个最好的地块，直接选择刚才次好的地块即可。
3、保持探索方向
尽量从上次探索的方向继续探索，如从地块A走到地块B，地块B在地块A的三点钟方向，那么在查找地块B周围的地块时，优先从三点钟方向开始遍历。若沿着这个方向的地块还不错(可以被选择)，那么应该优先选择它做为下一个地块，因为通向目的地的路多是直的。
当然，网上也有很多关于A-Star算法的优化方法，篇幅有限，这里就不再列举了。
| 瓦片管理器
建立一个瓦片管理器是很有必要的。
1、瓦片管理器管理所有的瓦片信息，每个地块只需凭借一个ID即可从瓦片管理器中获取瓦片信息。
2、瓦片管理器将封装对资源管理器的调用，需要使用瓦片的对象无需关心瓦片是如何被加载的，后期如更换资源管理方式时，修改范围小。
| 混合多种风格的地图
为了实现即有特点又无特点的地图风格，也就是类似“五彩斑斓的黑”的效果。我建议把瓦片风格进行细致的分类，这样在生成地图时既可以选择统一的风格，也可以进行多重风格混搭(当然前提是混合的风格要搭配，你需要具备一定的审美水平，最好能找个美术妹子来分类和把关)。
结合素材特点对瓦片进行风格分类
一张混合了雪山和火山两种风格的地图
还有一个小插曲，在实践了初版方案后，碰巧赶上了unity2018.2版本的发布，其中刚好包含了对六边形瓦片的支持。但是尝试后发现对于遮挡关系很难灵活控制（可能是我没有找到合适的方法），最终还是放弃了这个功能。
| 写在最后
最近疏于锻炼，有点胖了。
感谢你能看到这里，下回见，祝好。