案例研究 - Inside World Wide Maze

Saqoosha
Saqoosha
X 首页

World Wide Maze 是一款游戏，在游戏中，您需要使用智能手机在通过网站创建的 3D 迷宫中引导滚球导航，以尝试达到其目标点。

万维迷宫

该游戏充分利用了 HTML5 的功能。例如，DeviceOrientation 事件会从智能手机检索倾斜数据，然后这些数据通过 WebSocket 发送到 PC，玩家在 PC 上通过由 WebGL 和 Web Workers 构建的 3D 空间寻找方向。

在本文中，我将准确地解释这些功能的使用方式、整体开发过程以及优化的要点。

DeviceOrientation

DeviceOrientation 事件（示例）用于从智能手机检索倾斜数据。如果将 addEventListener 用于 DeviceOrientation 事件，系统会定期调用包含 DeviceOrientationEvent 对象的回调作为参数。时间间隔本身因所用设备而异。例如，在 iOS + Chrome 和 iOS + Safari 中，大约每 1/20 秒调用一次回调，而在 Android 4 + Chrome 中，大约每 1/10 秒调用一次。

window.addEventListener('deviceorientation', function (e) {
  // do something here..
});

DeviceOrientationEvent 对象包含 X、Y 和 Z 轴的倾斜度数据，以度数（不是弧度）表示（详细了解 HTML5Rocks）。不过，返回值也会因所使用的设备和浏览器组合而异。下表列出了实际返回值的范围：

设备屏幕方向。

顶部以蓝色突出显示的值是 W3C 规范中定义的值。以绿色高亮显示符合规格要求，以红色高亮显示则偏离。令人惊讶的是，只有 Android-Firefox 组合会返回符合规范的值。不过，在实现时，考虑频繁出现的值更为合理。因此，World Wide Maze 使用 iOS 返回值作为标准，并针对 Android 设备进行相应的调整。

if android and event.gamma > 180 then event.gamma -= 360

但是，这仍不支持 Nexus 10。尽管 Nexus 10 返回的值范围与其他 Android 设备相同，但有一个错误会导致 Beta 值和灰度系数值相反。此问题将单独得到解决。（或许它默认为横向显示？）

如上所示，即使涉及实体设备的 API 设置了规格，也不保证返回的值符合这些规格。因此，在所有潜在设备上测试它们至关重要。这也意味着可能会输入意外的值，这就需要创建解决方法。World Wide Maze 会在教程第 1 步中提示初次使用玩家的设备校准设备，但如果它收到意外的倾斜度值，则将无法正确校准到零位置。因此，它具有内部时间限制，如果玩家无法在该时间限制内校准，系统会提示玩家切换到键盘控件。

WebSocket

在 World Wide Maze 中，您的智能手机和 PC 是通过 WebSocket 连接的。更准确地说，设备之间通过中继服务器建立连接，即智能手机到服务器再到 PC。这是因为 WebSocket 无法将浏览器直接相互连接。（使用 WebRTC 数据通道可以实现点对点连接，并且无需中继服务器，但在实现时，此方法只能与 Chrome Canary 版和 Firefox Nightly 搭配使用。）

我选择使用名为 Socket.IO (v0.9.11) 的库来实现，该库包含在连接超时或断开连接时重新连接的功能。我将其与 NodeJS 结合使用，因为这个 NodeJS + Socket.IO 组合在多项 WebSocket 实现测试中展现了最佳的服务器端性能。

按数字配对

  1. 您的 PC 会连接到服务器。
  2. 服务器会为您的 PC 提供一个随机生成的数字，并记住数字和 PC 的组合。
  3. 在您的移动设备上，指定一个号码并连接到服务器。
  4. 如果指定的号码与已连接的 PC 上显示的号码相同，则表示您的移动设备已与该 PC 配对。
  5. 如果没有指定的 PC，则会出现错误。
  6. 当数据从移动设备传入时，它会发送到与之配对的 PC，反之亦然。

您也可以改为从移动设备进行初始连接。在这种情况下，设备只是反转了。

标签页同步

Chrome 专用的“标签页同步功能”可进一步简化配对过程。借助此功能，用户可以轻松在移动设备上打开在 PC 上打开的网页（反之亦然）。PC 接收服务器发出的连接编号，并使用 history.replaceState 将其附加到网页的网址。

history.replaceState(null, null, '/maze/' + connectionNumber)

如果启用了“标签页同步”功能，系统会在几秒后同步网址，并在移动设备上打开同一页面。移动设备会检查所打开网页的网址，如果附加了号码，就会立即开始连接。这样您就无需手动输入号码或使用摄像头扫描二维码。

延迟时间

由于中继服务器位于美国，因此从日本访问该服务器会导致智能手机的倾斜数据到达 PC 前大约延迟 200 毫秒。与开发期间使用的本地环境相比，响应时间明显延迟，但插入低通滤波器（我使用了 EMA）等方法可将响应时间提高到不显眼的水平。（在实践中，还需要使用低通滤波器来实现演示；来自倾斜传感器的返回值包含大量噪声，这些值应用于屏幕时会导致大量抖动。）这不适用于跳转，因为跳转操作明显非常缓慢，但无法解决此问题。

我从一开始就预计会出现延迟问题，因此我考虑在世界各地设置中继服务器，以便客户端能够连接到距离最近的可用服务器（从而最大限度地缩短延迟时间）。但是，我最终使用了 Google Compute Engine (GCE)，它当时仅在美国存在，所以这不可能。

Nagle 算法问题

Nagle 算法通常会整合到操作系统中，通过在 TCP 级别进行缓冲来实现高效通信，但我发现启用此算法后，我无法实时发送数据。（具体而言，与 TCP 延迟确认结合使用时。即使没有延迟 ACK，如果 ACK 因服务器位于海外等因素而延迟到一定程度，也会出现相同的问题。）

Android 版 Chrome 中的 WebSocket 并未出现 Nagle 延迟问题，包括用于停用 Nagle 的 TCP_NODELAY 选项，但在 iOS 版 Chrome 中使用的 WebKit WebSocket 却没有启用此选项。（使用同一 WebKit 的 Safari，也存在此问题。该问题是通过 Google 向 Apple 报告的，并且 WebKit 的开发版显然已解决了该问题。

出现此问题时，每 100 毫秒发送的倾斜数据会合并成块，每 500 毫秒才会到达 PC。在此类情况下，游戏无法正常运行，因此它通过让服务器端以较短的时间间隔（大约每 50 毫秒）发送一次数据来避免这种延迟。我认为，以较短的时间间隔接收 ACK 会使 Nagle 算法误认为可以发出数据。

Nagle 算法 1

上面的图表显示了实际接收数据的时间间隔。它表示数据包之间的时间间隔；绿色表示输出间隔，红色表示输入间隔。最小值为 54 毫秒，最大值为 158 毫秒，中间接近 100 毫秒。在这里，我使用的 iPhone 带有位于日本的中继服务器。输出和输入均约为 100 毫秒，操作顺畅。

Nagle 算法 2

相比之下，此图表显示的是在美国使用服务器的结果。虽然绿色输出区间稳定在 100 毫秒，但输入区间在 0 毫秒的低值和 500 毫秒的高值之间波动，这表明 PC 正在分块接收数据。

ALT_TEXT_HERE

最后，此图表显示了让服务器发出占位数据来避免延迟的结果。虽然其性能不如使用日本服务器，但很明显输入间隔在 100 毫秒左右保持相对稳定。

出现错误？

尽管 Android 4 (ICS) 中的默认浏览器具有 WebSocket API，但它无法连接，从而导致 Socket.IO connect_failed 事件。它在内部超时，而且服务器端也无法验证连接。（我没有单独使用 WebSocket 对此进行测试，因此可能存在 Socket.IO 问题。）

扩缩中继服务器

由于中继服务器的作用没有那么复杂，因此纵向扩容和增加服务器数量应该并不困难，只要您确保同一台 PC 和该移动设备始终连接到同一服务器即可。

物理学

在游戏中，球的移动（滑降、与地面相撞、与墙壁碰撞、收集物品等）全都在 3D 物理模拟器中完成。我使用了 Ammo.js（一个使用 Emscripten 将广泛使用的 Bullet 物理引擎移植到 JavaScript 中）和 Physijs 一起用作“Web Worker”。

Web Worker

Web Workers 是用于在单独的线程中运行 JavaScript 的 API。作为 Web Worker 启动的 JavaScript 作为独立于最初调用它的线程运行，因此在执行繁重任务的同时保持页面快速响应。Physijs 通过高效使用 Web Workers，帮助常规密集型 3D 物理引擎顺畅运行。World Wide Maze 以完全不同的帧速率处理物理引擎和 WebGL 图像渲染，因此即使低规格机器上的帧速率因 WebGL 渲染负载过大而下降，物理引擎本身也会多或少保持 60 fps，并且不会妨碍游戏控制。

FPS

此图片显示了在 Lenovo G570 上生成的帧速率。上面的框显示了 WebGL（图像渲染）的帧速率，下面的框显示了物理引擎的帧速率。GPU 是集成的 Intel HD Graphics 3000 芯片，因此图像渲染帧速率没有达到预期的 60fps。不过，由于物理引擎实现了预期的帧速率，因此游戏性能与高规格机器上的性能并无太大区别。

由于具有活动 Web Worker 的线程没有控制台对象，因此必须通过 postMessage 将数据发送到主线程以生成调试日志。使用 console4Worker 可在 worker 中创建等效的控制台对象，从而大大简化调试过程。

Service Worker

最新版本的 Chrome 允许您在启动 Web Worker 时设置断点，这对于调试也很有用。您可以在开发者工具的“Workers”面板中找到这些信息。

性能

多边形数量较多的阶段有时会超过 100,000 个多边形，但即使它们完全以 Physijs.ConcaveMesh（在 Bullet 中为 btBvhTriangleMeshShape）生成，性能并没有受到特别影响。

最初，由于需要碰撞检测的对象数量的增加，帧速率降低，但消除 Physijs 中不必要的处理后，性能得以提升。我们对原始 Physijs 的分支进行了这项改进。

重影

具有碰撞检测功能但对碰撞没有影响，因此对其他对象没有影响的对象在项目符号中称为“幽灵对象”。虽然 Physijs 没有正式支持幽灵对象，但可以在生成 Physijs.Mesh 后通过修改标志来创建幽灵对象。World Wide Maze 使用幽灵物体对物品和目标点进行碰撞检测。

hit = new Physijs.SphereMesh(geometry, material, 0)
hit._physijs.collision_flags = 1 | 4
scene.add(hit)

对于 collision_flags，1 为 CF_STATIC_OBJECT，4 为 CF_NO_CONTACT_RESPONSE。请尝试在 Bullet 论坛、Stack Overflow 或 Bullet 文档中搜索更多信息。由于 Physijs 是 Ammo.js 的封装容器，而 Ammo.js 与 Bullet 基本相同，因此可在 Bullet 中完成的大多数操作也可以在 Physijs 中完成。

Firefox 18 问题

Firefox 从版本 17 更新为 18 改变了 Web Workers 交换数据的方式，因此 Physijs 停止工作。该问题已在 GitHub 上报告，几天后便得到了解决。虽然这种开源效率给我留下了深刻的印象，但该事件也让我想起 World Wide Maze 是由多个不同的开源框架组成的。撰写这篇文章，是希望能为大家提供一些反馈意见。

asm.js

尽管这并不直接涉及 World Wide Maze，但 Ammo.js 已经支持 Mozilla 最近宣布的 asm.js（这并不奇怪，因为 asm.js 的创建基本上是为了加快 Emscripten 生成的 JavaScript 的速度，Emscripten 的创建者也是 Ammo.js 的创建者）。如果 Chrome 也支持 asm.js，则物理引擎的计算负载应该会大幅度减少。使用 Firefox Nightly 进行测试后速度明显加快。或许，最好在 C/C++ 中编写需要更高速度的部分，然后使用 Emscripten 将它们移植到 JavaScript。

WebGL

为实现 WebGL，我使用了最活跃的库 three.js (r53)。尽管修订版 57 在后期开发阶段已经发布，但该 API 已进行了重大更改，所以我坚持发布原来的修订版。

发光效果

为球核心和物品添加的发光效果是使用所谓的“Kawase Method MGF”的简单版本实现的。不过，虽然 Kawase 法可以让所有明亮的区域都亮起来，但 World Wide Maze 会为需要发光的区域创建单独的渲染目标。这是因为网站屏幕截图必须用于场景纹理，而仅提取所有亮区域会导致整个网站发光，例如使用白色背景。我还考虑过以 HDR 格式处理所有内容，但这次我决定不采用，因为这样会使实现过程变得非常复杂。

光晕

左上方显示了第一个通道，其中发光区域单独渲染，然后应用模糊处理。右下角显示第二次遍历，其中图像大小缩小 50%，然后应用模糊处理。右上图显示了第三轮图像，在这一过程中，图像再次被缩小了 50%，然后进行了模糊处理。然后，将三张图片叠加，形成最终的合成图片，显示在左下角。对于模糊处理，我使用了 three.js 中的 VerticalBlurShader 和 HorizontalBlurShader，因此仍有进一步优化的空间。

反光球

对球的反射基于 three.js 中的示例。所有方向均以球的位置进行渲染，并用作环境地图。每次球运动时，环境地图都需要更新，但由于以 60 fps 的帧率更新需要耗费大量资源，因此每三帧更新一次。结果不像更新每一帧那样顺畅，但除非特别指出，否则几乎无法察觉到差异。

着色器、着色器、着色器...

WebGL 要求所有渲染使用着色器（顶点着色器、fragment 着色器）。虽然 Three.js 中包含的着色器已经支持各种效果，但若要进行更加复杂的着色和优化，编写自己的着色器是不可避免的。由于 World Wide Maze 使 CPU 一直处于物理引擎状态，因此我尝试利用 GPU 来尽可能多地使用阴影语言 (GLSL) 编写代码，即使通过 JavaScript 进行 CPU 处理会更加轻松也是如此。海浪效果自然依赖于着色器，目标点的烟花和球出现时使用的网格效果自然也会如此。

着色器球

以上内容来自球出现时使用的网状效果测试。左边的线索是游戏内使用的线索，由 320 个多边形组成。中间的那个包含大约 5,000 个多边形，右侧的那个使用了大约 300,000 个多边形。即使有这么多的多边形，使用着色器进行处理也能保持 30 fps 的稳定帧速率。

着色器网格

这些小项目分散在场景上，全部集成到一个网格中，而单个移动则依赖于着色器移动每个多边形的尖端。测试的目的是了解存在大量对象时性能是否会受到影响。这里布置了大约 5,000 个对象，由大约 20,000 个多边形组成。性能没有受到任何影响。

poly2tri

场景根据从服务器收到的轮廓信息形成，然后通过 JavaScript 进行多边形化处理。三角测量是此流程的一个关键部分，通过 Three.js 实现效果不佳，并且通常会失败。因此，我决定自行集成一个名为 poly2tri 的不同三角测量库。事实证明，Three.js 以前明显尝试过相同的操作，所以我只需注释掉部分代码即可让它正常运行。因此，错误显著减少，允许游戏阶段也随之增加。偶然性错误仍然存在，由于某种原因，poly2tri 通过发出提醒来处理错误，所以我将其修改为抛出异常。

poly2tri

上图显示了如何对蓝色轮廓进行三角化，并生成红色多边形。

各向异性过滤

由于标准各向异性 MIP 映射会同时缩小水平轴和垂直轴上的图像大小，因此从倾斜角度查看多边形会使 World Wide Maze 阶段远端的纹理看起来像水平拉长的低分辨率纹理。此维基百科页面右上角的图片就是一个很好的例子。实际上，需要更多水平分辨率，WebGL (OpenGL) 会通过一种称为各向异性过滤的方法解析该分辨率。在 third.js 中，将 THREE.Texture.anisotropy 的值设为大于 1 会启用各向异性过滤。不过，此功能属于扩展功能，可能并非所有 GPU 都支持此功能。

优化

正如这篇 WebGL 最佳做法文章也提到的，提高 WebGL (OpenGL) 性能的最关键方法是尽量减少绘制调用。在《World Wide Maze》开发初期，游戏内的所有岛屿、桥梁和护栏都是独立的物品。这有时会导致超过 2,000 次绘制调用，使复杂的阶段变得笨重。然而，一旦我把相同类型的对象都打包到一个网格中，绘制调用次数就减少了 50 左右，从而显著提升了性能。

我已使用 Chrome 跟踪功能进一步优化过。Chrome 开发者工具中包含的性能分析器在一定程度上可以确定方法的整体处理时间，但跟踪记录可以告诉您每个部分所花费的时间，精确到 1/1000 秒。如需详细了解如何使用跟踪功能，请查看这篇文章。

优化

以上是为球的反射创建环境映射的轨迹结果。将 console.time 和 console.timeEnd 插入 three.js 中看似相关的位置，会得到一个如下所示的图表。时间从左到右流动，每一层都类似于一个调用堆栈。在 console.time 中嵌套 console.time 可以实现进一步测量。顶部的图表表示优化前，而底部表示优化后。如上图所示，在预先优化期间，系统会分别针对渲染 0-5 调用 updateMatrix（尽管该单词被截断）。不过，我对其进行了修改，使其仅调用一次，因为只有在对象位置或方向发生变化时才需要此过程。

跟踪进程本身会占用资源，因此，过多插入 console.time 可能会导致实际性能出现显著偏差，进而难以精确定位需要优化的方面。

效果调整工具

由于互联网的特性，此游戏很可能会在规格差异很大的系统上运行。2 月初发布的找寻前往奥兹国的路径使用名为 IFLAutomaticPerformanceAdjust 的类，根据帧速率的波动按比例缩小效果，帮助确保流畅播放。World Wide Maze 基于相同的 IFLAutomaticPerformanceAdjust 类构建，并按以下顺序缩小特效，以使游戏过程尽可能流畅：

  1. 如果帧速率低于 45 fps，则环境地图会停止更新。
  2. 如果帧速率仍低于 40 fps，则渲染分辨率会降低至 70%（表面比率的 50%）。
  3. 如果帧速率仍然低于 40 fps，则消除 FXAA（抗锯齿）。
  4. 如果帧速率仍然低于 30 fps，则会消除发光效果。

内存泄漏

使用 Three.js 来简洁地删除对象有点麻烦。但是，单独保留这些变量显然会导致内存泄漏，所以我设计了以下方法。@renderer 是指 THREE.WebGLRenderer。（Three.js 的最新版本使用一种略有不同的取消分配方法，因此，可能无法原样使用。）

destructObjects: (object) =>
  switch true
    when object instanceof THREE.Object3D
      @destructObjects(child) for child in object.children
      object.parent?.remove(object)
      object.deallocate()
      object.geometry?.deallocate()
      @renderer.deallocateObject(object)
      object.destruct?(this)

    when object instanceof THREE.Material
      object.deallocate()
      @renderer.deallocateMaterial(object)

    when object instanceof THREE.Texture
      object.deallocate()
      @renderer.deallocateTexture(object)

    when object instanceof THREE.EffectComposer
      @destructObjects(object.copyPass.material)
      object.passes.forEach (pass) =>
        @destructObjects(pass.material) if pass.material
        @renderer.deallocateRenderTarget(pass.renderTarget) if pass.renderTarget
        @renderer.deallocateRenderTarget(pass.renderTarget1) if pass.renderTarget1
        @renderer.deallocateRenderTarget(pass.renderTarget2) if pass.renderTarget2

HTML

就我个人而言，我觉得 WebGL 应用最棒的是能够用 HTML 设计页面布局。在 Flash 或 OpenFrameworks (OpenGL) 中构建 2D 界面（例如得分或文字显示）很困难。Flash 至少有一个 IDE，但如果您不熟悉，OpenFrameworks 会比较难（使用 Cocos2D 之类的工具可能会更容易）。另一方面，HTML 支持使用 CSS 精确控制所有前端设计方面，就像构建网站一样。虽然复杂效果（例如粒子凝结成徽标）是不可能的，但在 CSS Transforms 的功能范围内，一些 3D 效果是可能实现的。World Wide Maze 的“GOAL”和“TIME IS UP”文字效果在 CSS Transition 中使用缩放进行了动画处理（通过 Transit 实现）。（显然，背景渐变使用的是 WebGL。）

游戏中的每个网页（标题、结果、排名等）都有自己的 HTML 文件，当这些文件作为模板加载后，系统会在适当的时间使用适当的值调用 $(document.body).append()。有一个问题是，无法在附加之前设置鼠标和键盘事件，因此在附加之前尝试 el.click (e) -> console.log(e) 无法实现。

国际化 (i18n)

使用 HTML 对创建英文版也很方便。我选择了使用 i18next（一个 Web i18n 库）来满足国际化需求，无需修改即可直接使用。

对游戏内文本的编辑和翻译是在 Google 文档电子表格中完成的。由于 i18next 需要使用 JSON 文件，因此我将电子表格导出为 TSV，然后使用自定义转换器对其进行转换。我在发布前进行了很多更新，因此从 Google 文档电子表格自动执行导出会大大简化操作。

由于网页是使用 HTML 构建的，因此 Chrome 的自动翻译功能同样可以正常运行。然而，它有时无法正确检测语言，而是将其误认为完全不同的语言（例如，越南语），因此该功能目前已停用。（可使用元标记将其停用）。

RequireJS

我选择了 RequireJS 作为我的 JavaScript 模块系统。该游戏的 10,000 行源代码分为大约 60 个类（即咖啡文件），并编译成单独的 js 文件。RequireJS 会根据依赖项以适当的顺序加载这些单独的文件。

define ->
  class Hoge
    hogeMethod: ->

上面定义的类 (hoge.coffee) 可以按以下方式使用：

define ['hoge'], (Hoge) ->
  class Moge
    constructor: ->
      @hoge = new Hoge()
      @hoge.hogeMethod()

要正常使用，应在 moge.js 之前加载 hoge.js，而且由于“hoge”被指定为“定义”的第一个参数，因此始终会先加载 hoge.js（在 hoge.js 加载完成后回调）。这种机制称为 AMD，任何第三方库都可用于同一类型的回调，只要它支持 AMD 即可。即使是那些不使用该属性（例如 three.js），只要预先指定依赖项，它们也会以类似的方式表现。

这与导入 AS3 类似，因此不会显得那么奇怪。如果您最终得到的文件依赖性更多，可以采用此解决方案。

r.js

RequireJS 中包含一个名为 r.js 的优化器。此操作会将主 js 与所有依赖 js 文件捆绑在一起，然后使用 UglifyJS（或 Closure 编译器）将其压缩。这样可以减少浏览器需要加载的文件数和总数据量。World Wide Maze 的 JavaScript 文件总大小约为 2 MB，并且可以通过优化 r.js 来缩减到 1 MB 左右。如果游戏可以使用 gzip 分发，则此大小会进一步缩减至 250 KB。（GAE 有一个问题，不允许传输 1 MB 或更大的 gzip 文件，因此该游戏目前是以 1 MB 的纯文本未压缩的形式进行分发。）

场景建造商

阶段数据按如下方式生成，且完全在美国境内的 GCE 服务器上执行：

  1. 要转换为阶段的网站的网址通过 WebSocket 发送。
  2. PhantomJS 截取屏幕截图，然后以 JSON 格式检索和输出 div 和 img 标记位置。
  3. 根据第 2 步中的屏幕截图和 HTML 元素的定位数据，自定义 C++（OpenCV、Boost）程序会删除不必要的区域、生成岛屿、将岛屿与桥梁连接、计算护栏和项目位置、设置目标点等。结果会以 JSON 格式输出并返回给浏览器。

PhantomJS

PhantomJS 是一个没有屏幕的浏览器。它可以在不打开窗口的情况下加载网页，因此可用于自动化测试或在服务器端截取屏幕截图。其浏览器引擎是 WebKit，Chrome 和 Safari 也使用引擎，因此，它的布局和 JavaScript 执行结果也与标准浏览器大致相同。

通过 PhantomJS，使用 JavaScript 或 CoffeeScript 编写您要执行的流程。捕获屏幕截图非常简单，如此示例所示。我当时使用的是 Linux 服务器 (CentOS)，因此需要安装字体才能显示日语（M+ 字体）。即便如此，字体渲染的处理方式也与 Windows 或 Mac OS 中不同，因此同一字体在其他计算机上的显示效果可能会有所不同（但差异微乎其微）。

检索 img 和 div 标记位置的方法基本上与标准网页中一样。也可以顺利使用 jQuery。

stage_builder

我最初考虑使用更基于 DOM 的方法（类似于 Firefox 3D 检查器）来生成场景，然后尝试在 PhantomJS 中进行 DOM 分析等操作。但最终，我确定了一种图像处理方法。为此，我编写了一个使用 OpenCV 和 Boost 名为“stage_builder”的 C++ 程序。它会执行以下操作：

  1. 加载屏幕截图和 JSON 文件。
  2. 将图片和文字转换为“岛屿”。
  3. 建造桥梁来连接岛屿。
  4. 消除了创建迷宫的必要桥梁。
  5. 放置大型内容。
  6. 放置小物品。
  7. 放置护栏。
  8. 以 JSON 格式输出定位数据。

下面详细说明了每个步骤。

加载屏幕截图和 JSON 文件

常用的 cv::imread 用于加载屏幕截图。我测试了几个 JSON 文件的库，但使用 picojson 似乎最易于使用。

将图片和文字转换为“小岛”

阶段 build

以上是 aid-dcc.com 的“新闻”部分的屏幕截图（点击即可查看实际尺寸）。图片和文本元素必须转换为岛屿。为了隔离这些部分，我们应删除白色背景，也就是屏幕截图中最普遍的颜色。完成后，如下所示：

阶段 build

白色部分是潜在的岛屿。

文本太细且锐利，因此我们使用 cv::dilate、cv::GaussianBlur 和 cv::threshold 加粗文本。图像内容也缺失，因此我们将根据 PhantomJS 的 img 标记数据输出，用白色填充这些区域。生成的图像如下所示：

阶段 build

文本现在形成了合适的聚类，每张图片都是一个合适的孤岛。

建造桥梁来连接岛屿

一旦岛屿准备就绪后，就会通过桥梁连接起来。每个岛会在左侧、右侧、上方和下方寻找相邻的岛屿，然后将一座桥连接到最近岛屿的最近点，最终结果如下所示：

阶段 build

消除不必要的桥梁以创建迷宫

保留所有桥梁会使舞台变得过于简单，因此必须消除某些桥梁才能制造迷宫。系统会选择一个岛（例如左上角的那个）作为起点，并且删除连接到该岛的除一座桥（随机选择）之外的所有桥。然后，对通过其余桥梁连接的下一个岛屿执行相同的操作。一旦路径到达不通之处，或回到以前去过的岛屿，就会回到过去的点，方便前往新岛屿。所有岛屿都通过这种方式得到处理后，就完成了迷宫。

阶段 build

放置大型内容

每个岛上都会放置一个或多个大型项目，具体取决于其尺寸，从距离岛屿边缘最远的点中进行选择。虽然不是很清楚，但这些要点以红色显示如下：

阶段 build

在所有这些可能的点中，左上角的那个点被设置为起点（红色圆圈），右下角的点被设为目标（绿色圆圈），最多选择 6 个其余点作为大型项目放置位置（紫色圆圈）。

放置小物品

阶段 build

沿着与岛屿边缘之间的固定距离沿线放置适当数量的小型物品。上图（并非来自 aid-dcc.com）以灰色显示投影的放置位置线，这些线是偏移的，离岛边缘有固定间隔。红点表示小项的放置位置。由于此图片来自处于开发阶段的版本，因此这些项以直线形式排列，但最终版本会将这些项分布在灰色线条两侧的更加不规则。

放置护栏

护栏基本上是沿着岛屿的外界放置的，但是在桥梁上必须切掉护栏以便进入。事实证明，Boost Geometry 库有助于简化几何图形计算，例如确定岛屿边界数据与桥梁两侧线条的交汇位置。

阶段 build

岛屿的绿线是护栏。这张图片可能很难看清，但桥处没有绿线。这是用于调试的最终图片，其中包含所有需要输出为 JSON 的对象。浅蓝点表示小块区域，灰点表示建议的重启点。当小球落入海洋时，游戏会从最近的重新开始点继续。重启点的排列方式与小物品的排列方式大同小异，它们以固定间隔与岛屿边缘保持固定的距离。

以 JSON 格式输出定位数据

我还使用了 picojson 进行输出。它将数据写入标准输出，然后调用方 (Node.js) 会接收该输出。

在 Mac 上创建要在 Linux 中运行的 C++ 程序

这款游戏在 Mac 上开发并在 Linux 中部署，但是由于 OpenCV 和 Boost 同时适用于这两种操作系统，因此一旦建立了编译环境，开发本身就并不困难。我使用 Xcode 中的命令行工具在 Mac 上调试了构建，然后使用 automake/autoconf 创建了一个配置文件，以便在 Linux 中编译构建。然后，我只需在 Linux 中使用“configure && make”即可创建可执行文件。由于编译器版本差异，我遇到了一些特定于 Linux 的错误，但使用 gdb 能相对轻松地解决它们。

总结

可以使用 Flash 或 Unity 制作这类游戏，从而带来诸多优势。不过，此版本不需要插件，而且事实证明 HTML5 和 CSS3 的布局功能非常强大。请务必为每项任务提供合适的工具。我个人很惊讶，这款游戏完全以 HTML5 打造而成。尽管它在许多方面都有所欠缺，但我非常期待它在未来的发展。