利用位运算进行Tilemap的快速模式匹配

背景

最近在做一个地图生成的功能。其中有一个基础功能要先解决:在格子的地图上刷了相关的地形之后,如何根据实际的格子分布自动补全和更新边缘的形状,例如海滩的tile两面接山的情况下,就要有个弧形的边缘,而不是一条直的海岸线。这个功能在早期的2d的游戏中非常常见,因为当时的游戏都是tile-based的。

大概在3年前,unity还没有将2d-tilemap做成一个完整的包的时候,我自己写过一套。不过因为年代过去的有点久了,代码不太找得到了。于是准备重新写一下,看看有没有新思路。而且现在Unity自己的tilemap系统也非常完善了,不如也参考一下。

Unity的方案

Unity的这套系统并不是包含在默认的tilemap package中的,而是放在tilemap 2d-extras项目中的,在RuleTile.cs中包含了更新规则的实现。它支持为某一种地形建立一组rule,每个rule对应一种模式,根据每个格子周围的8格(或者15格)的分布情况来决定当前格子应该匹配哪一种规则。值得一提的是,它也支持旋转,镜像等方法进行模式匹配。即可以将多种分布情况映射到同一种tile上。

  • 绿色的箭头代表该格子内的tile需要格子中心处的tile为同一种
  • 红色的叉代表该格子内的tile需要格子中心处的tile为不同种
  • 如果没有标记,代表该格子内的tile无论是不是和中心tile一样都可以算作符合条件

我简单看了一下源码,发现主要是朴素的匹配。即对于每个Rule,每个旋转和镜像的情况分别将分布情况匹配一遍。
对于旋转,每次都要应用一个旋转矩阵来进行偏移向量的变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public bool RuleMatches(TilingRule rule, Vector3Int position, ITilemap tilemap, int angle)
{
var minCount = Math.Min(rule.m_Neighbors.Count, rule.m_NeighborPositions.Count);
for (int i = 0; i < minCount ; i++)
{
int neighbor = rule.m_Neighbors[i];
Vector3Int positionOffset = GetRotatedPosition(rule.m_NeighborPositions[i], angle);
TileBase other = tilemap.GetTile(GetOffsetPosition(position, positionOffset));
if (!RuleMatch(neighbor, other))
{
return false;
}
}
return true;
}

这样的好处是代码简单易懂。但是问题就是更多的只是适合离线的编辑,因为每次要更新一个格子都需要做相当多的判断(更何况更多的时候,还需要更新周围相邻的格子)。

而我们要做的功能涉及到地图的动态生成,对性能会有要求,于是想着能不能对其进行一个优化和精简。

利用编码

虽然地形的拼接有很多种规则,对于大部分的地形来说,用下图所示的15种规则就能生成一个完整的地图。

并且这里我们不需要使用镜像,光靠旋转就能完成(代价是可能会多出一个模式)

有了这15中模式,我们需要找到一种方式将它表示出来以便后面进行模式匹配。

对于模式匹配,我最喜欢的方式包含两个要素
1.将一个特征信息进行编码。编码的好处是能大幅缩小特征向量的大小,模式匹配的空间要求也下降。我们只需比较两个编码是否相同就能完成模式的匹配,通俗的说就是将原本逐个比较变成一次比较一个Integer。
2.找到一个快捷的方法能将编码进行变换。由于这里我们只用旋转就能解决所有的模式匹配,所以我们就只需要找到一种映射,可以将旋转映射为一种编码的变换。
还有一点就是如果能一次性编码完成,并直接匹配那更好,即相当于有一个O(N)的复杂度

对于第一点,最简单的方法是为每一个相邻的格子分配一个二进制位,这样能保证它们各自的信息不重叠。由于一个格子的状态实际上有三种:和当前中心格相同,不同,或者无关。如果用三个状态来保存虽然直观,但是会要求更大的编码空间以及损失很多位运算的便利特性。所以我决定还是将“无关”这种情况用掩码mask来处理。
0:和当前中心的tile不同(对应前面图中的绿色箭头)
1:和当前中心的tile相同(对应前面图中的红色叉)

第二就是我们应该如何决定每一格对应的二进制位的位置?
对于一个2d的旋转,其实就是将原来的坐标(偏移向量)乘以一个矩阵
$$
\begin{bmatrix}
cos(\theta) & sin(\theta)\\
-sin(\theta) & cos(\theta)
\end{bmatrix}
$$
因为每次都是旋转90°,所以就相当于每次把(x, y) -> (-y, x),这也是Unity中函数的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public virtual Vector3Int GetRotatedPosition(Vector3Int position, int rotation)
{
switch (rotation)
{
case 0:
return position;
case 90:
return new Vector3Int(position.y, -position.x, 0);
case 180:
return new Vector3Int(-position.x, -position.y, 0);
case 270:
return new Vector3Int(-position.y, position.x, 0);
}
return position;
}

但是这样的变换不太适合编码。再仔细观察之后,我们可以重新打乱编码顺序,不再以平时的逐行编码的方式去为每个格子编码,而是按照旋转的顺序来编码

我定义了两个循环的圈,并将开头定在了右上角,并且旋转方向是顺时针。注意内外两个圈的编码需要分别放到高低4位上,避免数据污染

每当要将一个pattern顺时针旋转90°的时候,其实就是将对应位“左移”一位。
这样一来,就解决了我们前面所说的要求。但是这只是基本理论,还需要注意一下实现的细节

到这里,前两点已经达成。但是复杂度稍微比O(N)大了一些:虽然免除了复杂的旋转矩阵,但是还是要进行旋转操作也即还带了一个常数级别的n。不过这篇文章里先不谈这个进一步的优化了。

实现细节

因为我们这个旋转操作是循环的,所以我们实际上做的不是“左移”位运算,而是一个包含高低各4位的编码的循环左移。
对于一般的循环左移,可以用公式
(x << n) | (x >> (len - n)) 来表示。但是我们这里的循环左移是按高低位分别进行的,所以需要做一个mask来处理。
我们当然可以将高4位和低4位拆开来分别用循环位移来处理,但是我为了节省一步操作,就一起处理了。
高4位的mask实际上就是原本的11110000左移并截掉头部(这样做可以防止低4位因为左移而对高4位产生污染),同时再并上低四位的00001111(因为低4位左移的时候不需要担心右方的位左移进行污染)
同理,低4位的mask是原本的00001111右移(不再需要手工把末尾截取),同时再并上高4位的11110000(因为高4位右移的时候不需要担心左方的位右移进行干扰)

1
2
3
4
5
6
7
private int RotateCode(int _code, int _count)
{
_count %= 4;
int highMask = 240 << _count & 255 | 15;
int lowMask = 15 >> (4 - _count) | 240;
return (_code << _count & highMask) | (_code >> (4 - _count) & lowMask);
}

我们每次旋转之后得到一个新的编码,然后和模式编码进行异或操作,如果为0就说明新的编码和模式编码一致了。
对于前面提到的无论相同或者不同都可以满足条件的情况,我们只用对异或后的结果&一个mask即可。
注意:我们直观上理解的时候,应该是旋转模式编码以和当前编码相对应,但是由于还有一个mask,旋转起来不方便。所以就反向旋转当前分布的编码
这里的返回值是指要旋转几次才能和模式编码相同,-1代表匹配失败

1
2
3
4
5
6
7
8
9
10
private int IsMatched(int _inputCode, int _patternCode, int _maskCode)
{
for (int rotCnt = 0; rotCnt < 4; ++rotCnt)
{
int curCode = RotateCode(inputCode, rotCnt);
if (((curCode ^ _patternCode) & _maskCode) == 0)
return rotCnt;
}
return -1;
}

我们要判断某一格的话,就依次和15个模式编码对比一下,找到匹配的就可以了。这里返回用的是个二维向量,第一个是表示是第几个模式tile,第二个是代表旋转了几次

1
2
3
4
5
6
7
8
9
10
11
12
private Vector2Int GetMatchedTile(Vector2Int _pos)
{
int inputCode = GetCodeAt(_pos);

for (int i = 0; i < 15; ++i)
{
int resultCnt = IsMatched(inputCode, patternCodes[i], maskCodes[i]);
if (resultCnt >= 0)
return new Vector2Int(i, resultCnt);
}
return new Vector2Int(-1, -1);
}

这里主要用3个函数就完成了原本几百行的比较代码,而且性能上也会更快。感觉也许还有更快的位运算的规律可以挖,此文也只是抛砖引玉。

我依稀记得我之前的做法是根据周围格子直接对当前分布进行编码,即在某个方向上的格子会直接将影响应用到编码上,这样会速度更快(即更接近O(N)),但是边界情况比较多,处理起来如果不小心容易写出bug,可读性也会低一些。不过还是看项目具体需求,如果需要更快的性能,可以考虑一次遍历即得到编码的方式