用 JS 制作随机地图（一）

[ajccom]

用 JS 制作随机地图（一）

我个人比较喜欢游戏，虽然常年在电商行业工作，但是平时利用闲暇时间会做做 JS 小游戏之类的玩意。这里我会花一系列的篇幅讲述如何用 JS + canvas 制作随机地图。

使用随机地图的好处

开始一个项目之前我们需要明确一下为何需要这个项目。随机地图在不少游戏中都有使用，比如经典的 DQM 系列（《勇者斗恶龙——怪物篇》）、英雄无敌系列等。它可以带给我们玩家许多意料之外的惊喜，而且由于地图难以预测，每一次游戏都会像是一次新的冒险，大大增强了游戏的趣味性。

英雄无敌 3 地图

地图网格与 Voronoi 图

首页我们需要给地图制作出一系列“格子”，用以填充地图本身。这里我们选着了一种叫做 Voronoi 图 的空间划分算法。这种算法可以根据我们给到的随机点，产生对应的个数的划分区块。

Voronoi 图，其中的黑点就是给到的随机点

百度百科上对这种算法的描述是：

计算几何里的一种基于距离的平面划分方法。在平面上有n个不重合种子点，把平面分为n个区域，使得每个区域内的点到它所在区域的种子点的距离比到其它区域种子点的距离近。每个区域称为该种子点的 Voronoi 区域。Voronoi 图是 Delaunay 三角剖分的对偶图。Voronoi 图的每条边是由相邻种子点的垂直平分线构成，在边上的点到两个种子点的距离相等。

虚线图形即上面提到的 Delaunay 三角

利用 D3 实现 Voronoi 图

D3 是一款强大的数据处理工具，它内置有对 Voronoi 图的实现，我们可以直接拿来用（当然 github 上也有很多独立的实现）。

//include d3.js

//初始化 voronoi 图的随机划分区域
var voronoi = d3.geom.voronoi().clipExtent([[0, 0], [width, height]]);

/**
 * _getVoronoiPaths 生成 voronoi 图图形数组
 * @return {Array} [[[x, y], [x, y], [x, y]], [...] ... ]
 */
function _getVoronoiPaths (points) {
  voronoiPaths = voronoi(points || _createRandomPoints())
  return voronoiPaths
}

这里 _getVoronoiPaths 方法会返回一个三维数组，最大的数组包含了 N 个多边形的集合，每一个多边形包含了组成该多边形的点的集合。

D3 官方示例可以参看这里

通过添加任意多个随机点，我们就可以得到一张被划分成 N 个区域的网格图。

设置 1000 个随机点后的效果

规则化网格

上面产生的图形存在着很大的不规则性，我们希望网格中的每一个区域的形状能够更加相似，这也更符合我们的审美。

规则化 Voronoi 图 并不是一件复杂的事情，只要将每个多边形的重心作为集合重新生成 Voronoi 图，这样反复多次，即可得到我们想要的图形，这种方法被称为 “劳埃德松弛”。所以我需要做的是通过多次调整随机点位置后得到一次比较规则的 Voronoi 图。

劳埃德松弛变化过程

获取一个凸多边形的重心十分的简单，公式见 Wikipedia。

/**
 * _getPolygonCentroid 获取多边形重心
 * @return {Array} [x, y]
 */
function _getPolygonCentroid (points) {
  var temp = points.slice(0), area = 0, result = [0, 0], l = temp.length

  // get polygon area
  temp.map(function (current, i) {
    var next = temp[i + 1 >= l ? 0 : (i + 1)]
    area += (current[0] * next[1] - next[0] * current[1])
  })
  area = area / 2

  //get polygon centroid
  temp.map(function (current, i) {
    var next = temp[i + 1 >= l ? 0 : (i + 1)]
    result[0] += ((current[0] + next[0]) * (current[0] * next[1] - next[0] * current[1]))
    result[1] += ((current[1] + next[1]) * (current[0] * next[1] - next[0] * current[1]))
  })

  result[0] = result[0] / 6 / area
  result[1] = result[1] / 6 / area

  return result
}

完成获取多边形重心的函数后，我们就可以设计松弛函数了。函数主要是对已有的多边形集合做一次转化，将多边形的重心作为一个集合传给 _getVoronoiPaths 方法以获得一个新的多边形集合。

/**
 * _relax 对 voronoi 图进行松弛操作
 * 获取 paths 中的各个多边形的中心点作为一个集合，并作为下次生成 voronoi 图的点集合
 * @params {Array} paths 上一次 voronoi 图的 paths
 * @params {Number} times 执行松弛次数
 * @return {Array} [[[x, y], [x, y], [x, y]], [...] ... ]
 */
function _relax (paths, times) {
  if (times === 0) {return paths}

  times = times || 1

  var centroidPoints = paths.map(function (points) {
    return _getPolygonCentroid(points)
  })

  paths = _getVoronoiPaths(centroidPoints)

  _relax(paths, times - 1)
}

利用 _relax 函数对原图形进行 3 次重复操作之后，我们得到的 Voronoi 图 效果比之前的规则多了（是不是很像石榴果实的排列）。

总结

这节我们主要学习了使用空间划分算法 Voronoi 图 生成地图网格。在执行多次劳埃德松弛后整个网格的视觉效果得以提升。下期我会讲述如何使用噪点，对地图的每个区域进行权值划分，呈现地图的各种地形。

这里查看本节的完整示例

参考文章

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
https://en.wikipedia.org/wiki/Lloyd's_algorithm
https://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon