A87C7C18-10BB-CAA0-162F-73E309953547.jpg

  对于大多数的游戏来说,内容的消耗都是开发商非常棘手的问题,而随机生成地图的做法则大大增加了游戏的可重复性,并且可以丰富玩家的体验。最近,海外一名资深开发者在博客中分享了他做随机生成地图的方式,以下请看编译的博客内容:
  这篇博客主要解释的是一个做随机生成地图的技术,之前TinyKeepDev也进行过简略的描述,但我这里会用更多的细节和步骤来解释这个做法,总体来说,整个算法的运行方式可以用下面的gif图表示:

2015122802035792962.gif

  生成房间
  首先,你要生成一些宽和高不同的房间,随机地放在一个圈内。TKdev的算法用了比较常见的方法随机生成房间尺寸,我认为这是一个不错的想法,因为它可以为你带来更多的参数可供使用,使用不同的宽高比例和标准偏差可以带来外观不同的副本地牢。
  你可能需要使用到的一个函数就是getRandomPointInCircle:
  function getRandomPointInCircle(radius)
  local t = 2*math.pi*math.random()
  local u = math.random()+math.random()
  local r = nil
  if u > 1 then r = 2-u else r = u end
  return radius*r*math.cos(t), radius*r*math.sin(t)
  end
  你可以在这个链接里获得更多的信息(英文版),在此之后,你就应该可以做出像下图这样的东西了:

2015122802035748727.gif

  你需要考虑的一个非常重要的事情是,由于你(至少是概念上)在处理一个tile网格,所以你必须把所有的东西都对齐到同一个网格里,在上图的gif中tile的尺寸是4像素,意味着所有的房间位置和尺寸都必须是4的公倍数。为了做到这样,我把位置和宽高比例都放到了一个函数中,把这些数字和tile尺寸相匹配:
  function roundm(n, m) return math.floor(((n + m – 1)/m))*m end
  — Now we can change the returned value from getRandomPointInCircle to:
  function getRandomPointInCircle(radius)
  …
  return roundm(radius*r*math.cos(t), tile_size),
  roundm(radius*r*math.sin(t), tile_size)
  end
  分散的房间
  现在,我们可以说说分离的部分了。有很多的房间都混在了同一个地方,而且它们之间不能有重叠。TKdev使用了分离转向的做法,但我发现用一个物理引擎做起来更简单。在你增加了所有的房间之后,只要增加物理物体(solid physics body)匹配每个房间的位置、然后运行模拟,直到所有的物体都出于休眠状态。在gif里我是用平常的速度运行模拟,但当你们做不同关卡之间的模拟时,可以用更快的速度。

2015122802035838024.gif

  这些物理物体本身并没有和tile网格相联系,但当设定了房间位置并且和随即指令放到一起的时候,你就会得到这些并不重叠的房间,而且这些房间与tile网格是匹配的,下面的gif对此进行了展示,蓝色外形是物理物体,在它们和房间之间总有一些不匹配,因为他们的位置始终是分散的。

2015122802035863638.gif

  当你希望创造水平或者垂直分布的房间时,这样的做法可能会出现一个问题,比如我现在在做的游戏:

201512280203583936.gif

  游戏里的战斗都是水平向的,所以我的游戏当中大多数的房间都更更宽,但可能没有那么高。问题在于,物理引擎如何解决这些比较长的房间在一起的时候出现的冲突:

2015122802035976156.gif

  你们可以看到的是,地牢变得非常高,这并不是理想中的状况。为了解决这个问题,我们可以一开始就把这些房间按带状分布而不是环形,这可以确保地牢本身有合适的宽高比例:

2015122802035934057.gif

  为了在这个带状区域里随机分布,我们只要把getRandomPointInCircle函数进行改变,把分布点放到椭圆形中即可,在gif里我使用的椭圆形宽度为400,高度为20):
  function getRandomPointInEllipse(ellipse_width, ellipse_height)
  local t = 2*math.pi*math.random()
  local u = math.random()+math.random()
  local r = nil
  if u > 1 then r = 2-u else r = u end
  return roundm(ellipse_width*r*math.cos(t)/2, tile_size),
  roundm(ellipse_height*r*math.sin(t)/2, tile_size)
  end
  主房间
  下一步主要是解决哪些房间是主房间或者中心房间,哪些是附属房间。TKdev的方法是非常不错的,你只需要挑选超过一定宽高比阀值的房间即可,在下面的gif里,我用的阀值是1.25,也就是说,如果平均宽和高是24,那么超过宽和高30的房间都会被选择。

2015122802035912454.gif

  三角剖分(Delaunay Triangulation)+图形
  现在,我们把所有选中房间的中间点找出来然后放到剖分程序中,你可以自己做这个过程,也可以找有经验的人分享这方面的资源。我在做游戏的时候比较幸运的是Yonaba已经做了这个过程。你们可以在界面中看到:

2015122802040081121.gif

  在有了这些三角形之后,你随后就可以生成一个图形,这个过程可以非常简单地给你带来图形信息数据结构或者数据库。如果你没有做过,那么房间物体或者结构最好有独特的ID,这样你就可以把这些Id加到图形中,而不是来回复制。
  最小化生成树(Spanning Tree)
  在此之后,我们从图形中生成了一个最小化的生成树,需要再强调一次的是,你可以自己做也可以找有经验的人去做(前提是和你使用的同一种编程语言)。

2015122802040020578.gif

  最小化生成树可以确保地牢中所有的主房间都是可达的,但同样将让这些房间的连接方式和此前不一样。这是很有用的,因为我们通常都不希望做一个连接太紧密的地牢,但也不希望做成不可达的孤岛。然而,我们又不希望地牢只是一个平行的路径,所以我们现在要做的就是为剖分图形增加一些边界:

2015122802040082238.gif

  这可以增加更多的路径和循环,这会让副本地牢变得更加有趣。TKdev当时是增加了15%的边界,而我发现8-10%是更好的选择,当然,这主要取决于你希望这些副本地牢之间的连接密度是怎样的。
  走廊
  最后,我们希望为地牢增加走廊,为此,我们检查了图形中的所有节点,然后在相邻的节点之间我们可以创造直线,如果这些相邻节点排列比较平行的话,我们就可以做一个水平线。如果这些节点比较垂直,我们可以做垂直线,如果这些节点没有相邻也没有平行或者垂直,我们可以做2跳线形成L形状。
  我测试是否相邻的标准是,计算两个节点之间的中间点,然后检查中间点X或者Y的属性是否在节点的边界之内,如果在,我就可以从这个中间点创造这条线,但只能在一个轴上。

700F9E9E-E4B7-F42A-E9BD-9D3D6A78C16B.jpg

  在上图中,你们可以看到所有情况下的例子,节点62和47之间有一个平行线,60和125之间有一个垂直线,而118和119之间有一个L形线。另一个比较重要的是,这些都不是我创造的线,这些只是我正在画的,但我还在每个线的旁边创造了2个额外的线,确保每一个都能够与tile尺寸匹配,因为我希望游戏中的战士宽度和高度都至少达到3个tiles。
  不管怎么说,在这个过程之后,我们可以检查哪些并非主房间的房子与这些线冲突,有冲突的房间可以被加到任何你在用的结构中,而且它们还可以作为走廊的轮廓:
  根据你最初设定房间的尺寸和均匀度,你到这里就可以获得外观不同的副本地牢了,如果你希望让走廊变得更统一而且看起来不那么奇怪,那么你就应该把偏差做小一些,而且应该做一些检查,确保房间不至于太窄或者太宽。

6FDFCEFB-7C24-34EA-3260-166C5B2B173E.jpg

  作为最后一步,我们只需要增加1个tile尺寸的网格房间不缺漏掉的部分即可,需要说的是,你其实并不需要有网格数据结构或者太花哨的东西,你可以根据tile尺寸检查每条线,并且在某些列表中增加网格分布位置即可,这就是我们增加3条线(或者更多)的原因。

8A1C70EB-B33F-AD36-534E-EC284898DC37.jpg

 

2015122802040045449.gif

  接下来,我们的随机生成地图就完成了。
  总结

2015122802040133892.gif

  整个流程中我返回的数据结构是:一个房间列表(每个房间都只是带有独特ID的结构、x/y位置和宽高比);图形,每个节点对应一个房间id;真实的2D网格,这里的每个房间都是空的,可以指向主房间、走廊或者走廊间。有了这三个结构,我认为你可以做出任何类型的数据,然后找到在哪儿放门、敌人、物品,决定哪些房间里有BOSS等等。