聊聊用算法生成《率土之滨》的世界地图

作者：王鑫然
首发知乎https://zhuanlan.zhihu.com/p/260771031

之前做战争策略游戏的时候，有过让大地图通过算法随机生成的想法，但由于各种原因，想法终没实现。现在刚好有空想想这个问题，做做思路积累。也借着这篇文章，讲讲算法方面的东西。

在传统的SLG战争策略类手游中，玩家要不断地探索大地图，向外扩张领土，击杀野怪和其他玩家，大世界地图上哪个地方是草，哪个地方是山，哪个地方是河流，都是手动一个区域一个区域的调出来的， 在《率土之滨》中同样如此，大地图的布局固定，每个服务器都一样，导致每个服务器大地图上的战略战术也一样。但如果希望每个服务器的大地图战略战术都不同，用算法该怎么去实现这个东西？

算法要实现的东西

固定的位置模块

在《率土之滨》的初始地图中，有10多个区域，这些区域之间存在边界，属于固定区域。区域间通过固定位置的桥梁或关隘进行连接。区域内部有固定坐标的城市、要塞争夺点。再算发生的大地图的过程中，要把这些有固定位置设计需求的元素考虑进去。


区域边缘

如果整张地图用算法进行连续运算，生成地貌，那么在区域的边界处，可能会出现一座面积庞大且连续的、不可通行的大山，而实际上在区域的边界处，我们仅仅需要一条细细的河流来分割区域.


地图模块种类的均衡

《率土之滨》中主要包含两种地图模块，一种是资源型地貌模块，一种是不可通行地貌模块，等级越高的资源模块，其分布越稀疏，数量越少。同等级的几种资源模块之间的数量需要保持地区分布均衡。


玩家获得资源的平衡

如果分布在不同玩家周围的资源数量不同，则会拉开前期发展速度的差距，让一部分玩家输在了起跑线上，所以算法应该保证玩家城市生成坐标附近，同等级的初始资源上的均衡，这包含数量上的均衡，以及距离上的均衡。

玩家的地区密度

一个地区如果玩家的密度过大，势必导致游戏前期，在这个地区内发生的PVP频率过高，玩家在前期没有安全稳定发展的公平环境，导致玩家密度高的地区，在游戏前期的流失率远高于玩家密度低的地区。


地图的生成

地图算法层

地图算法层分为成像层和承载层，成像层用于生成地图的地貌参数，承载层用于生成玩家真实在游戏里看到的地表上的各种物体，承载层内包含有地格层，地表基色层，资源和不可通行层、怪物层等多个算法层。

基本轮廓生成

地图轮廓的生成，用到perlin噪声，perlin噪声的两个重要参数是“振幅”和“频率”，将多个perlin噪声函数叠加起来后，就可以生成一个连续且更加自然的函数图像。


应用在空间直角坐标系后的图像大概是这样。


在一些战争策略类游戏中，大地图可能被设计成整片的海洋，陆地则被设计成孤岛，这个时候可以利用“种子生长”，从一点开始向外展开陆地。

山脉、河流、草地的定义和生成

在《率土之滨》里，地形块以格为单位，分为资源地块（平原）、山脉地块、河流地块，这三种基本地块（其他地块类型自行脑补），通过高度的定义，我们可以将perlin噪声所生成的图像下的地块，定义为这3种类型，如在空间直角坐标系中，我们将Z≥2的称为山脉，0＜Z＜2称为资源地块，将Z≤0的称为河流地块。以此定于地块。

游戏里为了让玩家对不同地块有更加清晰的认知，通常会用形状相同的素材来表示一类东西，比如山脉的形状都一样，顶多分几个不同的素材来表示山脉，所以真实游戏里生成的大概是这样。


区域的划分

在2维坐标中，在X轴上划定一个区域，就可以规定一个函数图像的范围，在空间直角坐标系中，用一个矩形就可以划定一个区域，无数个形状不同的矩形叠加在一起，则可以划定一个形状不规则的区域，函数的图像则在这个区域内生成


区域边缘的处理

规定区域的边缘为山脉地形块或河流地形块，并从这个地形块开始向外随机延伸地形块，延伸的地形块数值为0到3，对每一个随机值设定一个权重，如果想让地图边界附近有更多的山脉包围，则可以让3的权重更大，如果想让地图边界附近有更多的可通行区域，可以让0的权重更大。数值代表向边界外延伸多少个不可通行的地形块。地形块的类型以边界上的地形为基准进行映射，比如边界是河流的，则附近延伸的地形对应为山脉。


固定点的处理

《率土之滨》里的城市、要塞，属于固定点，这些点周围的区域要保持为可通行的资源地块状态，所以perlin噪声所生成的高低起伏的图像，不应该影响到这里的地形。在空间直角坐标系中，如果要形成一个高低起伏的地形，则先要给矩形网格中的点，随机生成一个单位圆梯度，再用方向向量与网格点的梯度向量做点积，最后对单个矩形四个点进行加权，得到该计算点的数值，使得数值在区域内平缓过渡，从而绘制出噪声图谱，如果不希望一个区域有高低起伏，可以直接控制这个区域内网格点向量的角度。


“回”型区域的识别

在中间是可通行区域，周围是不可通行区域的地形称为“回”字型区域，回字型区域可以偶尔出现，但数量一多，就说明生成的地图是有问题的，回字型区域的数学特点是——中间地块没有路径通向到所有的关键点（关键点可以取关隘），用“广度优先搜索”算法可以表示出路径可通行状态和路径长度。


“桶”型区域的识别

这种地形的数学特点是——中间的点与其相邻的“筒壁”上的点，距离关键点的距离差很大，用“广度优先搜索”算法计算出每一个点距离每一个关隘的距离，根据连续多个点的距离差的大小，可以识别这种地形。


资源地块的分布

如果资源地块的距离过近，就会在某个地方形成资源田的聚集，导致这个区域的PVP压力增大，《率土之滨》的外围州，属于初始区域，这个区域中，玩家要进行前期的发展，需要更加和平稳定的资源采集环境，所以要均衡这些地区的资源分布，可以利用“泊松圆盘”来构建这种分布。


用“米切尔最佳候选”算法，可以近似的构建“泊松圆盘”，这种算法是从一堆候选采样点中选取一个最佳采样点。做法是，第一轮先撒一堆点，这个点称为“已固定采样点”，之后在采样区域内随机生成固定数量的“候选采样点”。在“已固定采样点”和“候选采样点”之间画一条线，线段长度记为M，最终从“候选采样点”中选出一个M值最大的点，作为“最佳候选采样点”。第一轮结束后，“最佳候选采样点”被标记为“已固定采样点”，之后继续下一轮，不断循环，直到充满整个样本地图。


最终选出一堆“已固定采样点”，作为资源分布点，不同等级的资源点则在资源分布点中按照给定比例随机分布。

玩家分布

在《率土之滨》中，玩家的初始城市会占掉地面3*3的格，所以玩家之间初始城市中心坐标的最小地块直线距离是5格（没有半格的概念，中间留一格为了美观）。以任意玩家的城市中心点为中心，直径为5，画一个圆，也就是说，在这个圆内不能出现其他玩家的初始城市坐标。


同时，需保证每名玩家初始城市周围的资源数量保持一定范围内的均衡，在《率土之滨》中，资源地块的数量远远大于玩家的数量，所以可以利用已选出的“资源分布点”，采样出所有临近点之间距离大于等于5的点，作为玩家初始城市坐标的生成样本。


原文：https://zhuanlan.zhihu.com/p/260771031