文章目錄

1. Programming Game AI by Example
1. 1.1. 图的秘密
2. AI
3. 参考书籍
4. Reference

Programming Game AI by Example

图的秘密

图的术语

路径节点叫做节点(node)
连接节点的路线被叫做边(edge)
权包含了从一个节点移动到另一个节点所需要的开销信息

图的分类：

连通图（途中任何一个节点都可以找到一条路径到达所有其他的节点）
不连通图

图的定义：

图G的规范化的定义：通过边的集合E，节点的集合N来定义
G = {N , E}

注意：树是图的一个子集，树包含了所有的无环图

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

有向图：
一个有向图的边是有方向的。

游戏AI中的图：

导航图(Navigation Graph) （包含了在一个游戏环境中智能体可能访问的所有的位置和这些位置之间的所有连接）
依赖图(Dependency Graph) （被用来秒速玩家可以利用的不同的建筑物，材料，单元以及技术之间的依赖关系）
状态图(State Graph) （用来表示一个系统的每一个可能的状态以及状态之间的转换关系）

两种数据结构被用来表示图：

邻接矩阵（用一个二维的矩阵来表示图的链接关系，矩阵的每一个元素可以使布尔类型的，也可以是浮点类型的）
优缺点：
直观
但对于大的稀疏图来说，这种表示方法不经济，大部分矩阵元素被用来存储0
邻接表
优缺点：
对于存储稀疏图是非常有效的，不会浪费空间来存储空连接
例子：
有向图：

邻接矩阵：
Adjacency _Matrix

邻接表：
Adjacency_List

图的搜索算法：

盲目搜索(Uniformed Graph Searches) （在搜索一个图时不考虑相关的边的开销）
a. 深度优先搜索(DFS: Depth First Search) （搜索时尽可能地深入一个图。在搜索时，当它走入死胡同时，才会回溯，以回到上一个较浅的节点，在那里继续深度搜索）
注意：使用Stack来模拟，先进后出（FILO）的原则
DFS优化：
一些图可能非常深，深度优先便可能非常容易地就在错误的路径上陷得很深，因而延误了搜索。
限制深度的搜索(Limited Search)：限制深度优先搜索算法在开始回溯之前可以进行多少步的深度搜索
```
缺点： 如何设置最大搜索深度
  迭代加深深度优先搜索(Iterative Deepending Depth First Search)
```
b. 广度优先搜索(BFS：Breadth First Search) （从源节点展开以检查从它出发的边指向的每一个节点，然后再从那些刚检查过的节点继续展开）
注意：使用Queue来模拟，先进先出（FIFO）的原则
BFS缺点：
如果搜索的图非常大而且分支数很高，那么BFS就会浪费大量的内存并且表现出很低的效率。
基于开销的图搜索(cost-based graph searchs)
a. 边放松(Edge Relaxation) （从源节点到抵达目标节点的路径上的所有其他节点中搜集当前最优路径（BPFSF: Best Path Found So Far）信息。这个信息在检查新的边时得到更新。如果刚检查的边表明，如果用通过此边到达一个节点的路径取代现有的最优路径会使路程更短，那么，这条边就被加入，而路径也相应地更新）
b. 最短路径树(SPT: Short Path Tree) （从任何节点到达源节点的最短路径）

c. Dijkstra算法(Dijkstra Algorithm) （教授Edsger Wybe Dijkstra著名的寻找带全图的最短路径算法）
注意：使用一个索引的优先队列(Indexed Priority Queue)来实现。
缺点：
Dijkstra算法检查了太多的边。
d. Dijkstra算法的一个改进：A算法（Dijkstra算法通过最小化开销进行搜索。在处理搜索边界上的点时，如果估计一下他们距离目标节点的开销，并将这个信息考虑进去，那么算法的效率就可以大大提高。这个估计值被称为启发因子。）
注意： A算法和Dijkstra算法的唯一区别是对搜索边界上的点的开销的计算。被修正的到节点的开销F用来决定节点在优先队列中的位置。
F的计算：
F = G + H
G是到达一个节点的累计开销， H是一个启发因子，它给出的是节点到目标节点的估计距离。
通过用这种方法使用一个启发因子，被修正的开销会指引搜索逼近目标节点，而不是在各个可能的方向发散的搜索。这也使需要检查的边更少。因此搜索的加速是Disjkstra算法和A算法的最主要区别。
A算法的实现需要维护两个用来存储开销的std::vector，一个用来保存每一个节点的F开销，作为优先队列的索引，另一个是每一个节点的G开销。

《Artificial Intelligence for Game》 — Ian Millington

Introduction
1.1 What is AI?
Artificial intelligence is about making computers able to perform the thinking tasks that humans and animals are capable of

1.1.2 Game AI
Pacman [Midway Games West, Inc, 1979] – state machine
Warcraft –[Blizzard Entertainment, 1994] – Path finding

AI three basic needs:

Move
Movement refers to algorithms that turn decisions into some kind of motion
Decision making
Decision making involves a characterworking out what to do next
Strategy
Strategy refers to an overall approach used by a group of characters – e.g. Harf-Life
Note:
Not all game applications require all levels of AI

1.2.5 Agent-Based AI
Agent-based AI is about producing autonomous characters that take in information from the game data, determine what actions to take based on the information, and carry out those actions

1.3 Algorithms, Data Structures, and Representations
1.3.1 Algorithms

Tactical and Strategic AI
6.1 Waypoint Tactics
6.1.1 Tactical Locations

12.4 Real-Time Strategy
待续……

AI

前面提到的图主要是用于寻路方面(e.g. A*)的知识储备。

接下来要提到的AI主要是涉及到角色AI行为决策的实现，本章主要以学习状态机，分层状态机以及行为树来理解AI中行为决策的几个常用实现方式加深AI行为决策学习理解，更多更深入的学习可参考《Artificial.Intelligence.for.Games》书籍。

状态机

游戏中，一般人物或者游戏的状态都是有限的，这里我们可以使用状态机把这些有限的状态抽象出来，然后把各自的逻辑写在对应的状态中。一来逻辑清晰，二来各状态之间的关系也清晰。

打个比方：

游戏状态划分:

游戏初始状态(刚进游戏的第一个状态，负责初始化所有模块引导进入游戏)
游戏更新状态(热更新的一个状态，负责处理热更新相关)
游戏UI状态(游戏玩法外的一个状态，比如游戏主城时候)
游戏Loading状态(切换场景加载显示Loading图的过渡状态)
游戏GamePlay状态(具体的某个玩法状态，比如选择关卡后进去的具体玩游戏状态)
游戏暂停状态(顾名思义暂停游戏的一个状态)
游戏退出状态(关闭退出游戏时的一个状态，可以做一些游戏清除保存工作)

GameStateMachine

这里就只放几个核心代码：

StateMachine.cs(状态机管理类)

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class StateMachine<T> where T : class {

    /// <summary>
    /// 状态机拥有者
    /// </summary>
    protected T mOwner;

    /// <summary>
    /// 当前游戏状态
    /// </summary>
    private StateTemplate<T> mCurrentState;

    /// <summary>
    /// 当前游戏状态的int值(为了状态机通用这里没有写成特定Enum)
    /// </summary>
    public int CurrentStateValue
    {
        get
        {
            return mCurrentStateValue;
        }
    }
    private int mCurrentStateValue;

    /// <summary>
    /// 游戏状态机Map
    /// </summary>
    private Dictionary<int, StateTemplate<T>> mStatesMap;    

    public StateMachine(T owner)
    {
        mOwner = owner;
        mCurrentState = null;
        mCurrentStateValue = -1;
        mStatesMap = new Dictionary<int, StateTemplate<T>>();
    }

    /// <summary>
    /// 设置拥有者
    /// </summary>
    /// <param name="owner"></param>
    public void setOwner(T owner)
    {
        mOwner = owner;
    }

    /// <summary>
    /// 消息响应处理
    /// </summary>
    /// <param name="message"></param>
    public void handleMessage(MessageData message)
    {
        if(mCurrentState != null)
        {
            mCurrentState.onMessage(message);
        }
    }

    /// <summary>
    /// 游戏更新
    /// </summary>
    public void update()
    {
        if (mCurrentState != null)
        {
            mCurrentState.executeState();
        }
    }

    /// <summary>
    /// 注册游戏状态
    /// </summary>
    /// <param name="state"></param>
    /// <returns></returns>
    public bool registerState(int stateenum, StateTemplate<T> state)
    {
        if (mStatesMap.ContainsKey(stateenum))
        {
            Debug.LogError(string.Format("已经注册过状态:{0}", stateenum));
            return false;
        }
        else
        {
            mStatesMap.Add(stateenum, state);
            return true;
        }
    }

    /// <summary>
    /// 是否已经注册过特定状态
    /// </summary>
    /// <param name="stateenum"></param>
    /// <returns></returns>
    public bool hasRegisterSpecificState(int stateenum)
    {
        return mStatesMap.ContainsKey(stateenum);
    }

    /// <summary>
    /// 移除状态
    /// </summary>
    /// <param name="stateenum"></param>
    /// <returns></returns>
    public bool removeState(int stateenum)
    {
        if (mStatesMap.ContainsKey(stateenum))
        {
            mStatesMap.Remove(stateenum);
            return true;
        }
        else
        {
            Debug.LogError(string.Format("状态:{0}未注册，无法移除！", stateenum));
            return false;
        }
    }

    /// <summary>
    /// 清除所有注册的游戏状态
    /// </summary>
    public void clearAllStates()
    {
        mStatesMap.Clear();
    }

    /// <summary>
    /// 切换游戏状态
    /// </summary>
    /// <param name="stateenum"></param>
    /// <param name="param">状态切换参数</param>
    /// <returns></returns>
    public bool changeToState(int stateenum, params object[] param)
    {
        if (mStatesMap.ContainsKey(stateenum))
        {
            if (mCurrentState != null)
            {
                mCurrentState.exitState();
            }
            mCurrentState = mStatesMap[stateenum];
            mCurrentStateValue = stateenum;
            mCurrentState.setOwner(mOwner);
            mCurrentState.enterState(param);
            return true;
        }
        else
        {
            Debug.LogError(string.Format("未注册游戏状态:{0}", stateenum));
            return false;
        }
    }

    /// <summary>
    /// 清除所有数据状态
    /// </summary>
    public void clearAll()
    {        
        mCurrentState = null;
        mStatesMap.Clear();
        mOwner = null;
    }
}

StateTemplate.cs(状态模板类)

using UnityEngine;
using System.Collections;

/// <summary>
/// 游戏物体状态抽象基类
/// </summary>
public class StateTemplate<T> where T : class {

    /// <summary>
    /// 状态拥有者
    /// </summary>
    protected T mOwner;

    /// <summary>
    /// 设置状态拥有者
    /// </summary>
    /// <param name="owner"></param>
    public void setOwner(T owner)
    {
        mOwner = owner;
    }

    /// <summary>
    /// 获取状态拥有者
    /// </summary>
    public T getOwner()
    {
        return mOwner;
    }

    /// <summary>
    /// 进入当前状态
    /// </summary>
    /// <param name="param">状态运行参数</param>
    public virtual void enterState(params object[] param)
    {

    }

    /// <summary>
    /// 执行当前状态
    /// </summary>
    public virtual void executeState()
    {

    }

    /// <summary>
    /// 退出当前状态
    /// </summary>
    public virtual void exitState()
    {

    }
}

GameBaseState.cs(游戏状态基类)

/*
 * Description:             GameBaseState.cs
 * Author:                  TONYTANG
 * Create Date:             2018/12/09
 */

using UnityEngine;
using System.Collections;

/// <summary>
/// 游戏状态基类
/// </summary>
public class GameBaseState : StateTemplate<GameManager>
{
    /// <summary>
    /// 进入当前状态
    /// </summary>
    /// <param name="param">状态运行参数</param>
    public override void enterState(params object[] param)
    {
        loadRes(param);
    }

    /// <summary>
    /// 执行当前状态
    /// </summary>
    public override void executeState()
    {

    }

    /// <summary>
    /// 退出当前状态
    /// </summary>
    public override void exitState()
    {
        unloadRes();
    }

    /// <summary>
    /// 加载相关资源
    /// </summary>
    protected virtual void loadRes(params object[] param)
    {

    }

    /// <summary>
    /// 释放所有资源
    /// </summary>
    protected virtual void unloadRes()
    {

    }
}

代码就不详细说明了，看一眼大概就能明白了。

优点：

对于状态不多不复杂的来说，可以把状态逻辑划分很清晰，易于维护

缺点:

对于复杂拥有过多状态的情况来说，维护成本高不方便管理(横向扩展不利于维护)

针对缺点1的方案可以考虑HFSM(分层状态机)，通过细分大小状态机来进行更加细致的状态机分类。

结论：

FSM(有限状态机)更适合于状态数量不多不复杂的情况(e.g. 游戏状态分类)

分层状态机

详细HFSM参考

行为树

行为树是本章AI决策的重点，考虑到篇幅过长，所以另起一篇博客来详解行为树在Unity里的实战学习。

详情参考:

行为树-Unity)

行为树实战

目标：

实现一个简易的行为树，深入理解行为树的原理和实现
配套一个简易的节点编辑器(支持可视化编辑和调试)

实现：

目标1通过自行实现一个简易版
目标2基于Unity原生GUI API来实现可视化节点编辑器

数据管理

黑板模式

可以简单的理解成一个共享数据的地方。

抽象行为树

待添加……

行为中断

待添加……

节点编辑器

待添加……

参考书籍

《Programming Game AI by Example》 — Mat Buckland
《Artificial Intelligence for Game》 — Ian Millington

Reference

FSM（状态机）、HFSM（分层状态机）、BT（行为树）的区别

走停人生路

做着独立游戏梦，坚持走在游戏开发道路上的人

Artificial-Inteligence-Study

Programming Game AI by Example

图的秘密

图的术语

图的分类：

图的定义：

AI

状态机

分层状态机

行为树

行为树实战

数据管理

抽象行为树

行为中断

节点编辑器

参考书籍

Reference