网格与图

作者:St.F.K.
2022-12-07
12 7 4

编者按

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

  • 原文作者:Amit Patel
  • 译者:St.F.K.

正文

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

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

图的性质

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

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

  1. 图中的节点的集合(set)
  2. 每个节点连接的的集合(set)

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

  1. 节点的集合(set).
  2. 边的集合(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,让下坡更容易。

    障碍

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

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

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

    补充资料

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

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

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

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


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

    近期点赞的会员

     分享这篇文章

    St.F.K. 

    自由译员做工中;喜欢打电动,随机翻译各类内容 

    您可能还会对这些文章感兴趣

    参与此文章的讨论

    1. virmint 2022-12-07

      哇 可以交互耶 好酷

    2. sdjdasha 2022-12-09

      哇 可以交互耶 好酷

    3. St.F.K. 2022-12-09

      哇 可以交互耶 好酷

    4. mnikn 2022-12-12

      用图来描述对话树很方便,虽然对话树一般都是采用树的结构,不过由于用图也可以退化成树的结构,所以我更喜欢用图的结构,还很方便跳转任意对话节点。

    您需要登录或者注册后才能发表评论

    登录/注册