技术干货：如何高效实现地图自动拼接功能
发表于2016-04-06
一、介绍
这篇文章提供了一个诸如RPG Maker、星际争霸关卡编辑器的自动拼接功能的算法和数据结构。当地图编辑器提供了这个功能，能显著加快内容创建的节奏。
二、背景
基于tile的图像现在已经是2d游戏的标志了，因为早期的2D游戏使用有限的tile来表现一个大的2D环境。这很自然地会让图像块状并且重复。但是，高超的图像艺术家会通过巧妙地设计来避免这些问题。
一个类似的技术需要使用供过渡的tile，比如草地-水，草地-荒漠等如上图所示的块。但是，把这些过渡块手工放置在合适的位置工作量非常大。一个复杂的地图编辑器会允许用户标记哪些块，然后自动混合。
三、自动拼接
大部分自动拼接几何包括14个块，包括内部块和外部块（比如全部是草地和全是水的）、上、下、左、右边界、四个外角以及四个内角。这里的算法还要两个额外的块一共16个。
这个算法认为一个块是由四象限构成的。每一个象限或者角都属于一方（水或者草地）。所有可能的组合共有2 x 2 x 2 x 2 = 16。这16种组合可用4位的2进制数字b3 b2 b1 b0 来表示。每一位b I 对应一个角的类型。如下图所示，分别对应左上、左下、右上和右下。
使用4位索引，可以按如下排序：
这个过程也可以反过来，用4位序列来决定角的类型。这在下一节中给出了一个算法。为简便起见，假设地图只有这16种情况，并可用4位序列索引。
四、自动拼接算法
1、当一个新的tile被放置到地图中的时候，可以从它8个邻居的情况来推断它对应的是哪个4位索引
2、对于4个与新tile共享一条边的4个tile(上下左右)，新的4位索引被构建，2位来自新的tile，2位来自与共享边离得远的tile。新的4位索引会有限的让这tile进行过渡
3、类似的算法也发生在剩下4个块（左上，左下，右上，右下）。
4、与新块临近的块都已经计算了新的4位索引。
进一步考虑
除了上面的算法，还有以下问题需要考虑
· 边缘块：必须小心处理边缘或者角落的地图，因为他们的周围经常少于8个
· Tile组织：上面的算法假设4位索引直接对应tile索引。如果不是这样或者索引不连续，就需要建立一个图片和4位索引之间的双向查找。
· 变种：尽管这样过渡比较光滑了，但是观察者还是能看到重复的图样，可以把一个4位索引对应多个图片来解决这个问题。
五、实现
这篇文章没有理论没有包括任何示例代码，但是读者可以从这个开源地图编辑器tIDE（http://tide.codeplex.com）来研究这个自动拼接算法。
加入GAD的核心用户QQ群：484290331，各类活动奖励任你拿，最新资讯任你读，众多教学任你免费学，如此好地方赶紧加入吧！另VR专属群：476511561，专业VR技术分享，专业导师指导为你答疑解惑，大型小型活动奖励等你拿，免费学习赚奖励的天地，欢迎你加入哟！