The PathingFinding Graph

寻路都可以使用数据结构图中的一种类型来表示：有方向非负权重图。

GRAPHS

图是有两种元素类型：

• 节点：常常被画成点或者圆圈
• 连接线：连接点的线
  图是由一堆点和一堆先组成的。在寻路里每一个节点代表这一个区域或者位置信息啥的，连接线代表角色可以行走的路径。

我的寻路就是确定角色当前在那个节点，要去往那个节点，找到怎么从角色节点到目标节点的所有连接线。把所有连接线加起来就是我们的寻路路径。

WEGHTED GRAPHS

前面我们知道了怎么找到寻路路径，但是路径可能会是有多种方式。那我们如何选出最优的路径呢？

其中有一种方式就是在每一条连接线上都增加一个数值。这个数值常常叫做权重，有的游戏设计里叫做花销。

权重一般代表时间或者距离，当然很多开发者也会把权重的数值设置成一个复合参数，也就是把时间、距离和其他因素混合成一个数值。

使用权重我们就可以在多个路径中选取权重和最小的路径。

如果我们是需要从A点到C点，可以直接看出来有两条路径：

• A -> B -> C : 权重和为9
• A -> D -> B -> C ：权重和为16

所以我们选择第一个。

DIRECTED WEIGHTED GRAPHS

两个节点A,B如果是有连接线联通，在一般的图里既是A可以走到B，B可以走到A。假设有一种情况，角色从二楼直接跳到一楼，但是不能从一楼直接跳到二楼。这个时候的连接线就需要增加一个方向的属性，这样的图可以叫做方向权重图。

Data Structure

我们可以简单的把图抽象为：

class Graph:
    # An array of connections outgoing from the given node.
    function getConnections(fromNode: Node) -> Connection[]

class Connection:
    # The node that this connection came from.
    fromNode: Node
    # The node that this connection leads to.
    toNode: Node

    # The non-negative cost of this connection.
    function getCost() -> float