Xcode与C++之游戏开发：人工智能算法

人工智能算法在游戏中被用于决定计算机控制的实体的行动。常用的游戏人工智能算法包括行为状态机、寻路算法、两个玩家轮流博弈中常用的游戏树。

状态机

对于非常简单的游戏，比如之前编写的 Pong 游戏，游戏 AI 都有相同的行为。在整个游戏中，行为都没有发生什么改变。

稍微复杂一点的游戏，不同时间里，不同场景地点中，游戏 AI 的行为也会发生变化。比如在经典的吃豆人 Pac-Man 中，每个幽灵就有三种行为，追赶玩家、散开（一开始的时候）、逃离玩家。行为之间的变化的经典实现就是状态机。

自动贩卖机也是一种状态机。另外，状态机的非常有名，图灵的计算机模型就是基于状态机的。状态机图灵完备，理论上可以实现一切可计算的功能。

状态机设计

定义状态、进入状态时候的操作和退出状态转换操作最终构成状态机。实现游戏 AI 最重要的问题是状态之间如何转换。例如，NPC 在预定义的路径上巡逻，发现了玩家，就会开始攻击玩家。巡逻是一个状态，发现玩家后，就转换到了攻击状态。如果玩家可以发动攻击，NPC 有可能被杀死。死亡本身也是一种状态。

我们可以设计一个 AIComponent 来实现上述的状态行为。首先定义三个状态，巡逻（Patrol）、死亡（Death）、攻击（Attack）：

enum class AIState
{Patrol,Death,Attack
};

然后就可以创建一个 AICompoent 类拥有 AIState 这个成员数据，还可以分开定义每个状态的更新函数。

最简单的实现大概类似这样：

void AIComponent::Update(float deltaTime)
{switch (mState) {case AIState::PatrolUpdatePatrol(deltaTime);break;case AIState::Death:UpdateDeath(deltaTime);break;case AIState::Attack:UpdateDeath(deltaTime);break;default:break;}
}

为了实现状态的转换，可以实现一个函数 ChangeState，大体思路就是传入一个新状态，然后函数先退出原有状态，设置成新状态，进入新状态：

void AIComponent::ChangeState(AIState newState)
{// 退出当前状态（调用该状态的 Exit 函数）mState = newState;// 进入新的状态
}

上面的这种实现非常简单，但有问题。第一，不具备伸缩性。添加更多的状态同时降低 Update 和 ChangeState 的可读性。另外，为每一个状态设置 Update、Enter、Exit 函数也会让代码难以追踪。

有可能多个 AI 共享同一个状态，例如巡逻 Patrol，但上面这种处理显然很难进行复用。因此，我们可能不该把数据和操作分离开，而应该使用一种面向对象的思维将状态设计成类。

使用类实现状态

为了实现状态的可扩展，将状态本身抽象成为一个基类：

class AIState
{
public:AIState(class AIComponent* owner): mOwner(owner) {}// 特定状态行为virtual void Update(float deltaTime) = 0;virtual void OnEnter() = 0;virtual void OnExit() = 0;// 获取状态的名字virtual const char* GetName() const = 0;
protected:class AIComponent* mOwner;
};

通过 mOwner 成员变量，可以将 AIState 联系到特定的 AIComponent 上。下面，定义 AIComponent：

class AIComponent : public Component
{
public:AIComponent(class Actor* owner);void Update(float deltaTime) override;void ChangeState(const std::string& name);// 添加新状态void RegisterState(class AIState* state);
private:// 映射状态名到 AIState 实例std::unordered_map<std::string, class AIState*> mStateMap;// 当前状态class AIState* mCurrentState;
};

注意，AIComponent 有一个哈希表映射名字到 AIState 实例的指针，同时也保持有一个指向当前状态的指针。RegisterState 函数将 AIState 的指针添加到映射上：

void AIComponent::RegisterState(class AIState* state)
{mStateMap.emplace(state->GetName(), state);
}

AIComponent::Update 非常直截了当，调用当前状态的 Update 函数就可以了：

void AIComponent::Update(float deltaTime)
{if (mCurrentState){mCurrentState->Update(deltaTime);}
}

ChangeState 稍微要做的事情多一些，首先要调用 OnExit 函数退出当前状态，然后在哈希表中找到新状态，并调用 OnEnter 。

void AIComponent::ChangeState(const std::string& name)
{// 退出当前的状态if (mCurrentState){mCurrentState->OnExit();}// 在映射中找到新状态auto iter = mStateMap.find(name);if (iter != mStateMap.end()){mCurrentState = iter->second;// 进入状态mCurrentState->OnEnter();}else{SDL_Log("无法在映射中找到AIState %s", name.c_str());mCurrentState = nullptr;}
}

具体的状态，像巡逻 Patrol 可以通过继承自 AIState 实现：

class AIPatrol : public AIState
{
public:AIPatrol(class AIComponent* owner):AIState(owner){ }// 重写行为void Update(float deltaTime) override;void OnEnter() override;void OnExit() override;const char* GetName() const override{ return "Patrol"; }
};

就可以实现特定的 Update、OnEnter 和 OnExit。

void AIPatrol::Update(float deltaTime)
{SDL_Log("更新%s状态", GetName());// 可以做一些操作bool dead = true; // 这里只是简单示例，实际当然得弄清楚是不是死了if (dead){mOwner->ChangeState("Death");}
}

实际使用的时候需要把状态注册到 AIComponent 上。

寻路

寻路算法用于找出两个之间的路径，并且在路径中绕开障碍物。这个问题的复杂性在于可能两点之间存在大量的路径，但是这些路径中只有少数路径是最短的。

在求解寻路问题之前，我们需要找到一个表示游戏世界里 AI 路径的方式。显然，最经典的选择就是 数据结构：图的实现。这里假定读者对基本图数据结构有所了解。

我们这里使用的是邻接表实现的图结构。不同游戏也会用不同方式表示游戏世界，例如将世界划分为正方形是最简单的方法。这种实现方式在基于回合的策略游戏中非常普遍，例如：文明和X-COM。然而，对于其他很多类型的游戏，这种实现可能是不可行的。

struct GraphNode
{// 邻接表std::vector<GraphNode*> mAdjacent;
};struct Graph
{std::vector<GraphNode*> mNodes;
};

对于加权图，我们存储的则不是节点，而是边：

struct WeightedEdge
{// 哪个结点被这条边联系？struct WeightedGraphNode* mFrom;struct WeightedGraphNode* mTo;// 边的权重float mWeight;
};struct WeightedGraphNode
{std::vector<WeightedEdge*> mEdges;
};struct WeightedGraph
{std::vector<WeightedGraphNode*> mNodes;
};

广度优先搜索

广度优先搜索（BFS）可能是找出最短路径的最简单算法。算法大致的流程是这样的，给定的起点，然后将与该点关联的邻接点找出来，通常放到一个队列里。这一步完成后，相当于该点周围一圈都遍历了一边（第一层）。接下来，这个搜索圈会继续扩大到第二层。将加入队列的邻接点弹出，相同的操作，把邻接点对应的邻接点加入队列。第一圈的邻接点都取出后，意味剩下第二圈。就这样，圈子不断往外扩散，最终所有有关联的点都可以被找到。

由于是一圈一圈的扩散，因此到达目标的时候一定是最短的。这点上就是深度优先搜索和广度优先搜索的最明显的区别。

// 记录父边，防止重复
using NodeToParentMap =
std::unordered_map<const GraphNode*, const GraphNode*>;bool BFS(const Graph& graph, const GraphNode* start, const GraphNode* goal, NodeToParentMap& outMap)
{bool pathFound = false;// 保存结点的队列std::queue<const GraphNode*> q;// 取出第一个结点q.emplace(start);while (!q.empty()){// 不断从队列中取出结点const GraphNode* current = q.front();q.pop();if (current == goal){pathFound = true;break;}// 向队列中加入邻接结点for (const GraphNode* node : current->mAdjacent){const GraphNode* parent = outMap[node];if (parent == nullptr && node != start){outMap[node] = current;q.emplace(node);}}}return pathFound;
}

对于加权图，BFS 并不能保证找到最短路径，因为这个算法根本就看不懂权重。BFS 还有其他的问题，比如就算结点的方向和目标的方向相反，BFS 还是会测试这个结点。通过使用一些更加复杂的算法，可以减少寻路的时候需要测试的结点数量。

游戏中使用的大多数寻路算法都类似于 BFS，都是每次迭代的时候把邻接点加入到数据结构中。只不过，不同的寻路算法用不同的顺序评估结点。

启发式搜索

大多数时候，像 BFS 那样遍历所有结点是不现实的。实际使用搜索算法的时候，通常会使用一些启发式策略来简化搜索量。启发式算法通常追求的通过提供一个近似的结果，却能极大提高效率。在寻路中，启发式估计的是结点到目标结点之间的估计成本。利用启发式策略，可以更加快速的找到路径。

我们引入一个启发式函数 $h(x)$ 来评估结点 $x$ 到目标结点的成本。如果启发式函数始终小于或者等于结点 $x$ 到目标的实际成本，这是可以接受的。如果启发式方法偶尔高估了实际的成本，这是不可以接受的。

对于正方形的网格，有两种计算启发式常用的方法：

• 曼哈顿距离（Manhatan distance）：曼哈顿距离假设对角线运动是无效，如果对角线运动是有效的，曼哈顿距离通常会高估成本，从而使得启发式算法不能被接受。

对于 2D 网格，曼哈顿距离的计算方法如下：
$$h(x)=|start.x-end.x|+|start.y-end.y|$$

• 欧几里得距离（Euclidean distance）：欧氏距离可能是大家最熟悉的，欧几里得距离可以轻松适用于更加复杂的世界，相比而言，曼哈顿距离更适合方形网格。

h ( x ) = ( s t a r t . x − e n d . x ) 2 + ( s t a r t . y − e n d . y ) 2 h(x)=\sqrt{(start.x - end.x)^2 + (start.y - end.y)^2} h(x)=(start.x−end.x)2+(start.y−end.y)2 ​

两种启发式算法的差异，图中灰色方块是墙壁，不能直接穿过。注意，两个启发式算法都低估了实际成本，原因是因为启发式算法对邻接表是一无所知的。但这没问题，因为我们需要的就是下界。

欧氏距离作为启发式函数总是可以用的，因为我们都知道两点之间，走直线是最短的。曼哈顿距离就不一定了。但是，曼哈顿距离更加高效，因为它不涉及平方根。

欧几里得距离作为启发式算法高估真实成本的唯一情况就是游戏允许进行非欧几里得运动，比如在关卡中的两个节点之间进行传送。

最佳优先搜索（Greedy Best-First Search）

BFS 使用队列（先入先出）决定下一个结点。GBFS 使用是 $h(x)$ 来决定下一个结点。听起来很合理，但是 GBFS 无法保证得到的是最短路径。

显然，如果一开始就向下，会得到更短的路径。

尽管 GBFS 不能保证最优，但是理解这个算法还是有必要的。因为在这个基础上稍微改改，就得到了 A* 算法。

GBFS 不是使用单个队列，而是在搜索中使用两组结点。开集（open set）包含需要进一步查找的结点，闭集（close set）中的结点就不再需要进一步查找。但是，无法保证开集或者闭集上的某个结点最终会出现在路径上。这些操作只是便于剪枝。

对于开集，需要进行删除和测试；对于闭集，只需要进行成员关系测试。为了加快测试，可以简单的使用布尔值来跟踪特定的结点是在开集还是闭集。

对于开集，可以使用优先队列。这里简单一点，就直接使用 vector。和 BFS 一样，GBFS 同样需要在搜索过程中记录临时数据。

struct GBFSScratch
{const WeightedEdge* mParentEdge = nullptr;float mHeuristic = 0.0f;bool mInOpenSet = false;bool mInClosedSet = false;
};

定义一个映射，键是指向结点的指针，值是 GBFSScratch 的实例：

using GBFSMap =
std::unordered_map<const WeightedGraphNode*, GBFSScratch>;

GBFS 算法，一开始定义一个开集：

 std::vector<const WeightedGraphNode*> openSet;

之后，需要一个变量来跟踪当前的结点，即目前评估的结点。一开始，current 是起始结点，然后可以在闭集中标记。

// 设置起点，并且在闭集中标记
const WeightedGraphNode* current = start;
outMap[current].mInClosedSet = true;

接下来就是 GBFS 迭代的过程了。循环里主要做这几件事：

1. 找出当前结点的所有邻接结点；（不包括闭集里的）
2. 对于没有在开集里的结点，评估它的成本。

    do{// 添加邻接点到开集for (const WeightedEdge* edge : current->mEdges){GBFSScratch& data = outMap[edge->mTo];// 只加入不在空集里的结点if (!data.mInClosedSet){// 设置邻接点的父边data.mParentEdge = edge;if (!data.mInOpenSet){// 计算结点启发式成本，添加到开集data.mHeuristic = ComputeHeuristic(edge->mTo, goal);data.mInOpenSet = true;openSet.emplace_back(edge->mTo);}}}// 如果开集已空，所有路径已经穷尽if (openSet.empty()){break;}// 在开集中找到最小成本的点auto iter = std::min_element(openSet.begin(), openSet.end(),[&outMap](const WeightedGraphNode* a, const WeightedGraphNode* b) {return outMap[a].mHeuristic < outMap[b].mHeuristic;});// 设置 current 结点，并从开集移动到闭集current = *iter;openSet.erase(iter);outMap[current].mInOpenSet = false;outMap[current].mInClosedSet = true;} while (current != goal);

最后，判断是否找到了路径：

// 我们找到路径了没？
return (current == goal) ? true : false;

A* 搜索

GBFS 不能保证找到最短路径，但是稍微修改一下评估函数，就可以得到著名的 A* 算法。A* 算法添加了一个路径成本（path-cost），即从开始结点到给定结点的实际成本。使用 $g(x)$ 表示结点 $x$ 的路径成本。A* 算法会选择最小的 $f(x)$ 值，这个值就是 $g(x)$ 路径成本和 $h(x)$ 启发式成本的总和：
$$f(x)=g(x)+h(x)$$

在几个前提条件下，A* 算法能找到最优路径。首先前提肯定是两个结点之间确实存在路径。评估函数成本的不能大于实际成本。最后，边的权重大于等于0。

要实现 A* 算法，首先定义 AStarScratch 结构，和GBFS的类似，区别仅仅是多了一个 mActualFromStart 来存储 $g(x)$ 的值。

struct AStarScratch
{const WeightedEdge* mParentEdge = nullptr;float mHeuristic = 0.0f;float mActualFromStart = 0.0f;bool mInOpenSet = false;bool mInClosedSet = false;
};

添加结点到开集时，A* 必须计算路径成本 $g(x)$。选择结点的适合，挑选是 $f(x)$ 值最低的。$g(x)$ 的值则依赖于它的父结点的 $g(x)$ 值。

 do{// 添加邻接结点到开集for (const WeightedEdge* edge : current->mEdges){const WeightedGraphNode* neighbor = edge->mTo;// 获取暂存数据AStarScratch& data = outMap[neighbor];// 只检查不在闭集里的if (!data.mInClosedSet){if (!data.mInOpenSet){// 不在开集中，所以父结点必定是当前的data.mParentEdge = edge;data.mHeuristic = ComputeHeuristic(neighbor, goal);// 实际成本是父结点成本加边的成本data.mActualFromStart = outMap[current].mActualFromStart +edge->mWeight;data.mInOpenSet = true;openSet.emplace_back(neighbor);}else{// 计算当前结点成为父结点时的新实际成本float newG = outMap[current].mActualFromStart + edge->mWeight;if (newG < data.mActualFromStart){// 采用这个结点data.mParentEdge = edge;data.mActualFromStart = newG;}}}}// 如果开集为空，所有路径已经穷尽if (openSet.empty()){break;}// 在开集中找到成本最低的结点auto iter = std::min_element(openSet.begin(), openSet.end(),[&outMap](const WeightedGraphNode* a, const WeightedGraphNode* b) {// 计算 a/b 的 f(x) 值float fOfA = outMap[a].mHeuristic + outMap[a].mActualFromStart;float fOfB = outMap[b].mHeuristic + outMap[b].mActualFromStart;return fOfA < fOfB;});// 设置当前结点并移到闭集current = *iter;openSet.erase(iter);outMap[current].mInOpenSet = true;outMap[current].mInClosedSet = true;} while (current != goal);

Dijkstra 算法

Dijkstra 算法中，只有一个源点，没有目标结点（所谓的单源最短路径算法）。Dijstra 会计算从源结点到图中可达的结点之间的距离。

可以把上面的A* 代码转换成 Dijkstra 算法。首先，把 $h(x)$ 启发式函数删除，意味着 $h(x)=0$。之后，删除目标结点，使得循环在开集为空的时候停止。然后从头开始计算每个结点的 $g(x)$ 路径成本。

上述表述和Dijkstra 算法的作者 Edsger Dijkstra 对这个算法表述略有不同，但功能是一样的。有的 AI 教科书称这种方法为统一成本搜索。有意思的是，Dijkstra 算法的发明早于 GBFS 和 A* 。但在游戏中，A* 这样的启发式算法更受欢迎，因为搜索的结点数量通常都会比 Dijkstra 算法少。

寻路

一旦寻路算法生成了路径，AI 需要根据路径进行移动。可以把路径抽象成一系列的点。我们可以实现 MoveComponent 的子类 NavComponent。在此之前，MoveComponent 已经可以让 actor 移动了。NavComponent 仅仅需要旋转 actor 朝向正确的方向就可以了。

void NavComponent::TurnTo(const Vector2& pos)
{Vector2 dir = pos - mOwner->GetPosition();// -y 是因为 y 轴是朝下的float angle = Math::Atan2(-dir.y, dir.x);mOwner->SetRotation(angle);
}

NavComponent 有个 mNextPoint 变量跟踪路径中的下一个点。

void NavComponent::Update(float deltaTime)
{if (mNextNode){Vector2 diff = mOwner->GetPosition() - mNextNode->GetPosition();if (Math::NearZero(diff.Length(), 2.0f)){mNextNode = mNextNode->GetParent();TurnTo(mNextNode->GetPosition());}}MoveComponent::Update(deltaTime);
}

游戏树

像井字棋这种游戏就不同于实时游戏，首先，有两个玩家，而且是交替进行下子。其次，游戏是对抗性的，两个玩家互相对抗。这种类型的游戏所需要的 AI 和实时游戏完全不同。这种类型的游戏需要某种方式对整个游戏状态进行表示，并且这种状态可以告诉 AI 决策。一种最典型的实现就是游戏树。

在游戏树中，根结点代表当前游戏的状态。每条边代表游戏中的一个动作，并且将转入一个新的游戏局面（状态）。

在根结点中，当前玩家（也被叫做 max player）可以选择下子位置（图中有三个有效的下子位置），游戏状态也会发生相应的转移。在这之后，就轮到对手（也被叫做 min player）下子。就这样，到了叶子结点，就可以得到最终的输赢。

对于像井字棋这种游戏，只需要使用一个二维数组就可以表示：

struct GameState
{enum SquareState { Empty, X, O };SquareState mBoard[3][3];
};

一个游戏树结点存储子树列表和当前游戏状态：

struct GTNode
{std::vector<GTNode*> mChildren;GameState mState;
};

井字棋（tic-tac-toe）的游戏树结点数量最多只有 $9!=362880$，跟围棋这个级别是完全没法比的。对于复杂的局面，根本不可能把整个游戏树的都保存下来。现在我们假定的是完整的游戏树，实际中，如果处理非完整的游戏树也是一个重要的话题。

Minimax

minimax 算法评估一个两个玩家的游戏树，从而确定当前玩家的最佳决策。Minimax 假设每个玩家都会作出对自己最有利的选择。分数都是从大玩家（max player）角度来看的，因此大玩家会尝试让自己的分数最大化，而小玩家（min player）会努力地让大玩家的分数最低化。

实现过程就是递归遍历子树的过程。对于大玩家，找到最大值；对于小玩家，找到最小值：

float MaxPlayer(const GTNode* node)
{if (node->mChildren.empty()){return GetScore(node->mState);}float maxValue = -std::numeric_limits<float>::infinity();for (const GTNode* child : node->mChildren){maxValue = std::max(maxValue, MinPlayer(child));}return maxValue;
}float MinPlayer(const GTNode* node)
{if (node->mChildren.empty()){return GetScore(node->mState);}float minValue = std::numeric_limits<float>::infinity();for (const GTNode* child : node->mChildren){minValue = std::min(minValue, MaxPlayer(child));}return minValue;
}

上述代码只是找出选择，确定下一步的选择的代码是分离的：

const GTNode* MinimaxDecide(const GTNode* root)
{// 找出子树的最大值，并存下局面const GTNode* choice = nullptr;float maxValue = -std::numeric_limits<float>::infinity();for (const GTNode* child : root->mChildren){float v = MinPlayer(child);if (v > maxValue){maxValue = v;choice = child;}}return choice;
}

非完整游戏树

如果是围棋或者是象棋，生成完整的游戏树是不可能的。幸运的是，稍微改一改 minimax 代码就可以解决不完整游戏树。

首先，操作的是不再是游戏树的结点，而是游戏状态。接下来，不是遍历子结点，而是遍历当前的游戏状态下可能的下一个动作。这些是在 minimax 执行的时候生成而不是事先计算好。

换句话说，暴力已经不适用了，需要采取一种启发式的方法。然而，这也意味着可能得到的不是最优解。因为是在不完整的信息下作出的近似决策，就可能会导致最终的失败。

一种降低结点数量的方法就是限制每次递归的游戏树的深度：

float MaxPlayerLimit(const GameState* state, int depth)
{if (depth == 0 || state->IsTerminal()){return state->GetScore();}float maxValue = -std::numeric_limits<float>::infinity();for (const GameState* child : state->GetPossibleMoves()){maxValue = std::max(maxValue, MinPlayerLimit(child, depth - 1));}return maxValue;
}

近似评估局面用的启发式方法不同游戏，有不同的选择。大多数游戏也会为 AI 设置时间限制。这意味着有必要在深度和启发式算法的本身的复杂度之间取得平衡。

Alpha-Beta 剪枝

Alpha-beta 剪枝是 minimax 算法的优化。平均意义上，它会减少需要评估的结点数量。实际中，这就意味着可以增加最大深度而无需增加计算时间。

Alpha-beta 剪枝添加了两个变量，一个是 alpha，一个 beta。alpha 保证的当前 max player 的最高得分；beta 是保证当前 min player 的最高得分。也就是说，alpha 和 beta 是分数的上下界。

一开始，alpha 被初始化成负无穷；beta 被初始化成正无穷。这是两个玩家最糟糕的值：

const GTNode* AlphaBetaDecide(const GTNode* root)
{const GTNode* choice = nullptr;float maxValue = -std::numeric_limits<float>::infinity();float beta = std::numeric_limits<float>::infinity();for (const GTNode* child : root->mChildren){float v = AlphaBetaMin(child, maxValue, beta);if (v > maxValue){maxValue = v;choice = child;}}return choice;
}

基于上述的 MaxPlayerLimit，可以实现 AlphaBetaMax：

float AlphaBetaMax(const GTNode* node, float alpha, float beta)
{if (node->mChildren.empty()){return GetScore(node->mState);}float maxValue = -std::numeric_limits<float>::infinity();for (const GTNode* child : node->mChildren){maxValue = std::max(maxValue, AlphaBetaMin(child, alpha, beta));if (maxValue >= beta){return maxValue; // Beta 剪枝}alpha = std::max(maxValue, alpha);}return maxValue;
}

类似的，可以得到 AlphaBetaMin：

float AlphaBetaMin(const GTNode* node, float alpha, float beta)
{if (node->mChildren.empty()){return GetScore(node->mState);}float minValue = std::numeric_limits<float>::infinity();for (const GTNode* child : node->mChildren){minValue = std::min(minValue, AlphaBetaMax(child, alpha, beta));if (minValue <= alpha){return minValue; // Alpha 剪枝}beta = std::min(minValue, beta);}return minValue;
}

需要注意一下，对子树的计算顺序会影响到剪枝的结点数量。这意味着即使深度限制一致，不同的开始状态也会产生不同的执行时间。如果有固定时间限制，可能会出现时间到了，AI 不知道怎么行动的问题。一种解决方法是迭代加深，在不断叠加深度下多次运行算法，例如现在深度为3的时候进行运算，然后深度为4，接着深度为5。如果时间到了，那么就返回上一个迭代的结果，这样至少不会让 AI 不知所措。

小结

游戏人工智能足够写一本书来描述了。上述这些是比较经典的游戏人工智能算法。下一节尝试写一个带基础 AI 功能的塔防游戏。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！