网格与图

编者按

本文来自游戏设计博客 Red Blob Games，由 indienova 取得授权并译制发表，原文链接见文末。

原文作者：Amit Patel
译者：St.F.K.

正文

Dijkstra 算法和 A* 算法等图搜索（graph search）算法适用于加权有向图（weighted directed graphs），即一组由带有数字权重（表示移动成本）的边连接的节点。那么，这些算法能用于网格吗？答案是肯定的：网格可以被视为图的一种特例。

或

本文介绍了基于图的寻路算法会用到的图论相关知识，以及如何表示网格。

图的性质

基于图的寻路算法需要知道有哪些地点，以及哪些地点之间相互连接。一般来讲，你掌握的信息远不止如此，你还知道地点的大小和坐标等；但实际上算法并不了解这些。它唯一了解的只有连接。

数学上的图由节点（node）和边（edge）的集合（set）构成。节点（也称顶点或对象）之间由边（也称链接，连接，矢或弧）（译注：矢或弧只用于有向图的情况）相连。对任意一张图，我们需要了解两部分内容：

图中的节点的集合（set）
每个节点连接的边的集合（set）

那么，把如上的拓扑图表示成这种形式会是什么样子呢？

节点的集合（set）：.
边的集合（set）：

注意，图的排布方式并不属于图的一部分。上方插图中表示的图和下方插图中的图是同一张图：

自己动手试试：列出图中的所有节点，再列出与每个节点相连的边。你会得到和上方几张插图一样的结果。

图搜索算法实际上并不“理解”网格的排布方式与各种属性。它们只能理解网格的连接状况。对网格其他附加属性也能够加以利用的寻路算法，要比常规 A* 算法运行速度更快。我会在另一篇文章中探讨这个问题。

下面让我们看看，怎样以图的形式，用代码来表示网格。

用图表示网格

处理正方形网格时，我们需要先写出节点的列表。当然，我们的方法并不局限于处理矩形网格，但是，考虑到简洁性，此处代码以 20x10 的矩形网格为例：

all_nodes = []
for x in range(20):
    for y in range(10):
        all_nodes.append([x, y])

这些边分别居于东，西，南，北四个方向。对每个节点，我们需要知道，哪些节点通过边与它相连。我们称这些相连的节点为邻点（neighbors，译注：按《网格沉思：游戏中的网格元素》，此处对应概念为 adjacent，故译名采用邻点。）：

def neighbors(node):
    dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    result = []
    for dir in dirs:
        result.append([node[0] + dir[0], node[1] + dir[1]])
    return result

如果你的游戏允许沿着对角线移动，那 dirs 中应该包含八个元素。

但是，我们只想让程序返回那些我们可以移动到的节点，所以我们会加入一个检查步骤：

def neighbors(node):
    dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    result = []
    for dir in dirs:
        neighbor = [node[0] + dir[0], node[1] + dir[1]]
        if neighbor in all_nodes:
            result.append(neighbor)
    return result

另一种检查方式是确认节点坐标是否都在范围内。这种检查方式只在地图是矩形时才有效。下面是给我们之前生成的 20x10 地图编写的代码：

def neighbors(node):
    dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    result = []
    for dir in dirs:
        neighbor = [node[0] + dir[0], node[1] + dir[1]]
        if 0 <= neighbor[0] < 20 and 0 <= neighbor[1] < 10:
            result.append(neighbor)
    return result

在实践中，我们还会希望在图中附加额外信息，比如某个方格能否允许通行。

变体

上面我没有细讲怎么处理边。在图论中，有以下几种对边进行处理的方法：

无向图（undirected graph）中的边同时通往两个方向。这种边在游戏地图中很常见。在上面的例子里，每条无向边，比如 B↔C，都列出了两次，一次写成 B→C，一次写成 C→B。
有向图（directed graph）中的边只通向一个方向，反过来则走不通。单向门，跳下悬崖，还有传送门等都可以构成游戏中的单向边。这种图中可以只有 B→C 的边，而没有 C→B 的边。
多重图（multigraph）可以在同一对节点之间有多条边。类比到游戏中就是既可以游过一条河，又可以划船通过同一条河。节点 B 可以有多条 B→C 的边指向节点 C。

除此之外，你还可以给节点和边标注上额外信息。寻路算法中常用的一种标注是给边加权。加权图（weighted graph）允许给图中的每条边赋予一个权重数值。在加权无向图中，我们可能会把柏油路的权重设为 1，把蜿蜒的林间小道的权重设成 4，好让寻路算法倾向于走柏油路。在加权有向图中，我们可能会把下坡的边 B→C 的权重设为 2，把上坡的边 C→B 的权重设为 5，让下坡更容易。

障碍

我们该怎么在图中标识网格里的障碍呢？一般有三种方式：

移除节点。如果障碍占据了网格中的某些格子，你可以直接从图（all_nodes）中移除对应的节点。你还得移除和这些节点相连的边：如果前面你使用“if neighbor in all_nodes”进行检查的话，这些边会被自动移除；但如果你是根据坐标 x/y 是否在范围内进行检查，那就得手动删掉这些边了。
移除边。如果障碍占据了格子间的边界，你可以往 neighbors() 函数里多加一次判断，把对应边删掉。如果障碍占据的是格子，你可以移除通向这些格子的边。
将边的权重设为无限大。如果障碍占据了格子间的边界，你可以把对应边的权重设成无限大。如果障碍占据的是格子，你可以把通向障碍物的边的权重设为无限大。你必须调整图搜索函数，让其在访问成本为无限大的节点之前退出。

如果你想在完成图的构造之后再针对障碍做出调整，使用改变权重的方式可能会更容易一些。

补充资料

为什么在寻路教程中，我一直使用网格呢？因为它们简单好用，并且在我开始做游戏那个年代极其常见。网格还能使用基于图的寻路算法。我有计划制作一些基于非网格寻路图的 Demo，但用网格更加容易解释。

上文没有涉及到边的其它表示方法。一般我会为每个节点相连的边创建一个列表（list），但你也可以定义全局的边集合（set），或用矩阵（matrix）表示，以记录哪些节点之间有边相连。详见维基百科。

上文也没有涉及图在游戏中的其它用途。尽管图搜索显而易见地适合用于地图寻路，但也可以用它解决许多别的问题。你可以用它表示地下城游戏中的房间（节点）和走道（边）。你可以用它表示社交游戏中的玩家（节点）与其好友关系（边）。你可以把可能的行为表示成图，通过搜索它来决定执行何种行为。你可以将所有可能的棋局盘面（游戏状态）表示成节点，所有可能的走棋策略（游戏操作）表示为边，然后通过搜索它的一部分，来决定如何移动棋子。你可以把 NPC 的状态表示成节点，把他们的行为表示成边。你可以（通过图来）构建 NPC 对话数据库，以表示谈话主题。在地图生成器中，你可以利用图来生成河流与道路。你可以用图来表示游戏中的经济系统，用节点表示小麦与面包，用边来表示烘培工艺。3D 多边形网格也能视为一种图。图是一种简洁的抽象。如果数据结构采用类似图的形式，你就能够复用各种各样的图算法。

还有很多关于图与图论的文章。《Plus magazine》上的许多链接讲到了图的妙用，维基百科也是不错的学习起点。

原文链接：https://www.redblobgames.com/pathfinding/grids/graphs.html
*本文内容系作者独立观点，不代表 indienova 立场。未经授权允许，请勿转载。