|
作者:王鑫然
首发知乎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
|
|