序言

Tilemap，也就是瓦片地图，是一种在游戏设计和应用开发中常用的技术，特别是在2D游戏中。这种技术允许你创建复杂的二维世界，同时保持相对较小的资源需求。

最常见的Tilemap是由正方形网格组成的，可以用二维矩阵来表示。矩阵中元素为1表示对应位置有方块；元素为0表示没有方块。

本文试图研究这样一个问题：给定一个Tilemap，如何提取出它对应的Polygon Shape。这个polygon对应了Tilemap的碰撞边界，可以被 box2d 等物理引擎所使用。一个简单的例子如下图所示。

二维数组，Tilemap图形和对应的Polygon Shape

实际的场景

实际的场景往往不像上述例子那样简单，我们需要考虑算法在任意Tilemap上的适用性。其中最典型的三种情况是：非连通、自交的和内嵌的。

  • 对于非连通的Tilemap，需要为每一个连通分量提取一个Polygon Shape
  • 对于自交的情况，此时两个方块以对角形式连接，需要正确处理顶点重叠的问题
  • 对于内嵌的情况，需要为外圈和内圈各生成一个Polygon Shape，它们有着相反的顶点序

添加图片注释，不超过 140 字（可选）

顶点序

我们在上述例子中提到了「顶点序」，它表达了polygon路径面向「外侧」或「里侧」这样的概念。顶点序可以是顺时针或者逆时针。

在本文中，我们规定逆时针顶点序（简称逆时针序）表示polygon面向外侧，而顺时针序表示polygon面向里侧。区分外侧和里侧是十分重要的，它决定了polygon的碰撞边界接受哪个方向的力，这和它的表面法线有关。

在处理这些polygon时，总是记得它们是**有方向的（Directional）。**如果顶点绕行顺序错误，将会产生意料之外的行为。如果你想了解更多细节，可以阅读：box2d的 Collision Module 部分。

box2d 以逆时针序面向外侧，顺时针序面向里侧

正文

有了这些前置概念，我们可以开始设计具体的算法了，代码部分将给出Python 3的实现参考。

输入与输出

  • 算法输入一个二维数组，数组中的每个元素表示对应坐标是否有方块
  • 算法输出一个路径列表，表示这个Tilemap中提取的所有Polygon Shape
  • 输出的每个Polygon Shape以逆时针或顺时针序排列的顶点坐标表示
1
2
def get_polygon_shapes(map: list[list]) -> list:
    """输入一个二维数组，返回所有的Polygon Shape"""

提取边界

Polygon Shape必然由方块的边界部分组成，因此第一步先提取所有边界上的点和边。

如何判断一个点或者一条边是否处于方块的边界上呢？

一个正方形有四条边，一条边最多被两个方块所共享。**未被共享的边在边界上，而被共享的边在内部。**如下图所示，蓝色边被A、B两个方块共享，而红色边不被共享。

添加图片注释，不超过 140 字（可选）

因此，我们可以通过统计边的重数，重数为1的边处于边界上。再从边界边上提取出边界上的顶点，将它们存储到self.vertices和self.edges中。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class _Vertex:
    def __init__(self, x: int, y: int, neighbors: list, count: int):
        self.x = x
        self.y = y
        self.neighbors = neighbors
        self.count = count

    def __repr__(self):
        return f'({self.x}, {self.y})'

class _Edge:
    def __init__(self):
        self.count = 0
        self.cell_pos = None

class Solver:
    def add_edge(self, x, y, z, w, cell_pos: tuple[int, int]):
        t0 = (x, y, z, w)
        t1 = (z, w, x, y)
        self.edges[t0].count += 1
        self.edges[t1].count += 1
        self.edges[t0].cell_pos = cell_pos
        self.edges[t1].cell_pos = cell_pos

    def __init__(self, map: 'Tilemap'):
        self.map = map
        self.vertices = {}
        self.edges = defaultdict(_Edge)
        for y in range(map.height):
            for x in range(map.width):
                cell = map.get_cell(x, y)
                if cell is None:
                    continue
                # put edges into `self.edges`
                self.add_edge(x, y, x+1, y, (x, y))
                self.add_edge(x, y, x, y+1, (x, y))
                self.add_edge(x+1, y, x+1, y+1, (x, y))
                self.add_edge(x, y+1, x+1, y+1, (x, y))
        # keeps only edges with 1 count
        self.edges = {k: v for k, v in self.edges.items() if v.count == 1}
        # put vertices into `self.vertices`
        for x, y, z, w in self.edges.keys():
            self.vertices[(x, y)] = None
            self.vertices[(z, w)] = None

提取顶点邻居

有了所有的边界点，还需要知道顶点之间的连接情况，这决定了从某个顶点出发，下一步可以选择哪些点。

为了方便，我们预处理出所有顶点的邻居，并存到_Vertex结构的 neighbors变量中。通过观察，我们可以发现有关顶点邻居的一些规律。

  1. 一个边界点要么有两个邻居，要么有四个邻居
  2. 如果该点有两个邻居，它是一个「平凡点」
  3. 如果该点有四个邻居，它是一个「自交点」

每个边界点的邻居个数

上图标记了一个Tilemap中，每个顶点的邻居数量。我们将每个顶点的邻居信息存储在顶点结构中，这些信息非常重要，因为它告诉我们一个点可能是一个自交点，从而需要特殊的处理。

对于自交点，可以将其看作是两个不同polygon的顶点的重叠。这样，一个自交点是算作两个平凡点，需要在路径中包括两次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# process vertices
for x, y in self.vertices.keys():
    neighbors = [
        z
        for z in [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
        if (x, y, z[0], z[1]) in self.edges
    ]
    assert len(neighbors) in (2, 4)
    if len(neighbors) == 4:
        count = 2       # self-intersecting vertex
    else:
        count = 1       # trivial vertex
    v = _Vertex(x, y, neighbors, count)
    self.vertices[(x, y)] = v

搜索顶点路径

有了前述信息的辅助，事情逐步变得明朗了起来。你很容易想到使用DFS来搜索顶点的路径，每当DFS经过一个顶点，就可以从顶点的邻居列表中选取下一个顶点。

不过，现在我们只搜索顶点的路径，并不考虑路径的方向。在后续步骤中，我们将会使用额外的算法来处理顶点序，这在一定程度上可以简化实现。总之，这一步的目标是找到所有的路径。

如果当前顶点是平凡点，也就是说，它只有两个邻居，DFS直接选择未走过的那个邻居为下一个点（如果两个邻居都未走过，则随便选一个）。我们用一个count变量来记录一个点被走过的次数，它是int而不是bool，这是因为自交点算两个平凡点，需要遍历两次才算走过。

平凡点和自交点上的路径选择

如果当前顶点是自交点，则无法用这个简单的方法来判断下一步该走哪个点。自交点连接的两个polygon是视为非连通的，从一个polygon移动到一个非连通的polygon是不合法的。

这似乎是自交点产生的某种BUG。

假设我们知道当前点的上一个点，就可以确定来时的方向。只要把转移路径限制在同一个方块的表面，问题就迎刃而解了。

转移路径限制在A的表面，避免错误地转移到非连通的方块上

如图所示，在自交点附近的两次转移，都被限制在同一个方块（图中的A）的表面，这样我们就不会错误地移动到非连通的其他方块上。完整的DFS算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def dfs(self, curr: _Vertex, path: list[_Vertex]):
    assert curr.count > 0
    curr.count -= 1
    if len(path) == 0:
        prev = None
    else:
        prev = path[-1]
    path.append(curr)
    if len(curr.neighbors) == 2:
        n0 = self.vertices[curr.neighbors[0]]
        n1 = self.vertices[curr.neighbors[1]]
        if n0.count > 0 and n0 is not prev:
            self.dfs(n0, path)
        elif n1.count > 0 and n1 is not prev:
            self.dfs(n1, path)
    elif len(curr.neighbors) == 4:
        # self-intersecting vertex
        # we need prev to determine the direction
        assert prev is not None
        for n in curr.neighbors:
            n: _Vertex = self.vertices[n]
            if n is prev:   # skip prev
                continue
            cell_0 = self.edges[(prev.x, prev.y, curr.x, curr.y)].cell_pos
            cell_1 = self.edges[(curr.x, curr.y, n.x, n.y)].cell_pos
            if cell_0 == cell_1:
                # print((prev.x, prev.y), (curr.x, curr.y), (n.x, n.y))
                if n.count > 0:
                    self.dfs(n, path)
                return
        # no neighbor is available
        raise ValueError('a self-intersecting vertex has no valid neighbor')

可以想到，自交点不能作为出发点，因为自交点上的路径转移依赖于它的前一个点，出发点不满足这样的要求。

至此，核心的DFS部分就完成了。现在只需选择每一个非自交、且未被访问过的点，将它们作为出发点执行DFS，就得到了Tilemap上所有的polygon顶点路径。

确定路径方向

现在我们接近最终的目标了，还需确定每一个路径的方向。虽然我们得到的polygon路径是有序排列的，但我们并不知道一个路径是逆时针序还是顺时针序。因此，有必要求助ChatGPT。

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

ChatGPT告诉我们，有一种叫做shoelace formula的算法，它可以从顶点坐标中计算一个不自相交的多边形的面积，无论这多边形是凹的还是凸的。与此同时，面积的符号即对应着我们要求的顶点序。

1
2
3
4
5
6
7
8
def polygon_area(self, path: list[_Vertex]) -> float:
    """shoelace formula"""
    area = 0.0
    for i in range(len(path)):
        p1 = path[i]
        p2 = path[(i+1) % len(path)]
        area += (p1.x*p2.y - p2.x*p1.y)
    return area / 2.0

这个公式实在是非常神奇，十分优雅和简洁。

调整顶点序

接下来，我们调整路径为正确的顶点序，即它应该是面向「外侧」还是「里侧」。乍一看，这个答案似乎不是那么显而易见。有一种启发式算法可以做到这一点（我认为它应该是正确的）。

  1. 找到polygon路径最左上角的顶点（the most top-left point）
  2. 一些形状可能没有唯一的最左上角，选择最左的最上或者最上的最左也是可以的
  3. 如果这个点的右下方有方块，则路径面向「外侧」，应采用逆时针序
  4. 如果这个点的右下方没有方块，则路径面向「里侧」，应采用顺时针序

添加图片注释，不超过 140 字（可选）

那么，我们首先使用shoelace formula判断所有路径的顶点序，把它们统一调整为逆时针序。再应用上述启发式算法，找到应该面向里侧的路径，将它们调整为顺时针序。如此一来，所有路径的方向就是正确的了。

注1：调整路径的顶点序即是将顶点列表逆置。

注2：这个启发式算法也可以用于确定路径的顶点序。这也许是更高效的做法，但shoelace formula也很优雅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solve(self):
    res = []
    for v in self.vertices.values():
        # never use self-intersecting vertex as start
        if len(v.neighbors) == 4:
            continue
        if v.count == 1:
            path = []
            self.dfs(v, path)
            assert len(path) >= 3
            # determine the order of the path
            # get the most top-left vertex
            topleft = path[0]
            for p in path:
                if p.y < topleft.y or (p.y == topleft.y and p.x < topleft.x):
                    topleft = p
            # first make sure all the path are in the same order
            if self.polygon_area(path) < 0:
                path.reverse()
            # if it is a hole, reverse it
            if self.map.get_cell(topleft.x, topleft.y) is None:
                path.reverse()
            res.append(path)
    return res

时间复杂度

算法需要遍历二维数组的每一项，因此总的时间复杂度是 ，其中 和 分别是Tilemap的宽和高，以及若干常数因子。

最终效果

这是一个复杂的Tilemap，它同时包含了非连通，自交和内嵌的特殊情况，使用 box2d 和 Dear ImGui 绘制。

所有的polygon路径都正确地与小球产生碰撞。

结束语

本文的算法是为了易于理解和实现，并不一定*（几乎一定不是）*是最高效的做法，其他思路欢迎在评论区留言。

本文的表述可能存在错误，或是考虑不全之处，也请读者批评指正。