本系列为笔者初学c/c++和游戏AI开发的学习过程，算法为主，不涉及到具体的游戏开发软件学习(如unity，虚幻4等),若有错误请在评论区留下批评意见。

• 语言：c/c++ (11及以上)

• 平台：macOS mojave

• 编译器：vs Code / g++

图与路径规划

一、图

1.1 图的定义

图(Graph)是由顶点和连接顶点的边构成的离散结构。在游戏中，图则常常被用来表示点和点之间的路径。

  如图1，路径点称为节点（node，顶点），连接节点的路线称为边（edge），或弧（arc）。

  通过游戏角色运动的路径表示为图，我们就可以通过各种图算法来计算出两点之间的最短路径（或其他条件），然后驱动游戏角色沿着计算好的路劲刚移动。

  一个图G能被规范化的定义为，通过边的集合E进行连接的节点（或顶点）的集合N。

G = {N，E}

1.2 图的性质

  图的基本性质：

• 有向图：只能从一个节点到另一个节点，这两个节点称作有序对（Ordered pair），用来                表示边的方向。可表示为从源节点（source node）到目标节点（destination                    node）。

• 无向图：两个点之间可以来回运动，没有方向限制。

• 加权图：点和点之间的边是有重要性区别的，若把每个点看做一件事，那边的权重意味着                完成这件事的重要性。

• 有/无环图：环是针对有向图而言的，有环就是从一个点出发，一定能够找到一条路径回                  到这个点；反之若找不到，则是无环图。

• 连通图：无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立，那                么就是强连通的。

• 图密度：边与节点的比率决定了一个图是稀疏的还是致密的。
  

1.3 图的数据结构

  在计算机中，图主要由两种数据结构来表示：

• 邻接矩阵：用一个二维矩阵来表示图的连接关系，通常用0来表示两个点之间没有连接。                可以高效的查找两个节点间是否有连接，但对稀疏图会消耗大量的内存空间。

• 邻接表：对于每一个当前节点，一个邻接表图存储一个链表以包含所有它的邻边。邻接表             存储稀疏图可以节省内存空间，但每次查找都需要遍历一次链表，产生额外开销。

1.4 图在游戏中的应用

1.4.1 导航图  

  导航图（Navgraph）是这样一种抽象结构，它包含了在一个游戏环境中智能体可能访问的所有的位置和这些位置之间的所有连接。

  导航图的每一个节点通常都表示一个关键区域的位置，或一个环境的对象，每条边代表这些点之间的连接，且边通常是有权重的。

1.4.2 依赖图

  在含有资源管理系统的游戏类型中，依赖图发挥着重要作用，它被用来描述玩家可以利用的不同的资源之间的依赖关系，即完成每种资源所必须的先决条件。

  举个例子，在游戏中，玩家必须先制造武器库，然后他才能制造武器。这里的武器库和武器就是两种不同的资源，武器资源依赖于武器库资源。

  除此之外，用依赖图设计的游戏人工智能，如即时战略游戏中，电脑可以根据玩家目前建造的资源而决定下一步骤的决策行为，设计出具有针对性的策略行动。

  比如玩家建造了步兵军营，电脑就会从克制步兵的资源中选取一样或几样来建造，设计出针对性的克制玩家的策略。

  但是我们要注意的一点是，游戏人工智能设计，并不是要设计出能百分百完胜玩家的超级智能，而是要设计出一个可供玩家挑战并战胜的陪玩。

  战胜玩家并不是我们的目的，这太容易办到了。难的是如何在胜利和失败之间取得平衡，让玩家永远处于跃跃欲试的兴奋状态中，让他们能从游戏中获得满足感，并渴望去挑战更高的难度。

  这点在Sim Hui Tee的论文《DEVELOPING PARALLEL DEPENDENCY GRAPH IN IMPROVING GAME BALANCING》里有了很好的体现，他解释了依赖图在游戏平衡中的应用。

1.4.2 状态图

  状态图用在表示一个系统的每一个可能的状态以及状态之间的转换。一个系统潜在的状态的集合被叫做状态空间。

  在这里，有状图知识点的讲解和应用。

参考：

• 《游戏人工智能编程案例精粹》

• 《算法导论》

• 相关代码下载    https://github.com/linpeijie/GameToy