36
2D-六边形瓦片地图的随机生成-腾讯游戏学院
source link: http://gad.qq.com/article/detail/286283
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
好久不见。
这是第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版本的发布，其中刚好包含了对六边形瓦片的支持。但是尝试后发现对于遮挡关系很难灵活控制（可能是我没有找到合适的方法），最终还是放弃了这个功能。
| 写在最后
最近疏于锻炼，有点胖了。
感谢你能看到这里，下回见，祝好。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK