星际争霸中，玩家需要按照合理的顺序去建造单元，以尽快形成所需的战斗力。不过，找到最优的建造顺序并不简单，需要做权衡。例如，玩家可以先建造一些工人，让工人去采集资源，工人越多收集资源的速度就越快，从而尽快达成建造的条件，然而建造工人也需要消耗时间，太多工人也是浪费，因此需要找出一个合理的建造方法。

本文内容主要结合UAlbertaBot的代码和相关的论文《Build-order Optimization in StarCraft》进行分析，论文地址如下：

https://www.aaai.org/ocs/index.php/AIIDE/AIIDE11/paper/viewFile/4078/4407

星际争霸游戏中，工人在采集矿石

建造目标的产生

UAlbertaBot的策略管理器（StrategyManager）会根据当前局势去选择一种策略（具体方法后续再探讨，这里先关注建设相关），每种策略包含该策略下需要有哪些单元。

例如，如果AI选择神族（protoss），策略管理器有可能产生一个叫ZealotRush的策略，这个策略对应以下的建造目标，包含一些Probe（工人）、Pylon（水晶塔）、Gateway（兵营）和Zealot（狂热者，一种攻击单位）。

["Probe", "Probe", "Probe", "Probe", "Pylon", "Probe", "Gateway", "Gateway", "Probe", "Probe", "Zealot", "Pylon", "Zealot", "Zealot", "Probe", "Zealot", "Zealot", "Probe", "Pylon", "Zealot", "Gateway", "Probe", "Pylon", "Probe", "Zealot", "Probe", "Zealot", "Zealot", "Zealot", "Zealot", "Pylon", "Probe", "Zealot", "Zealot", "Zealot" ]},

Probe相当于工人

当AI选择的策略有变更、或者玩家某些单元被歼灭时，就需要更新建造顺序。而ProductionManager便会根据StrategyManager的建造目前去建设。源码中，上层通过如下接口给ProductionManager设置建设目标。

void ProductionManager::setBuildOrder(const BuildOrder & buildOrder);

再通过performBuildOrderSearch方法做深度搜索，最终获得最优建造顺序。

ProductionManager::performBuildOrderSearch()

对游戏的抽象

程序将游戏的建造部分抽象成“游戏状态”和“动作”，并使用搜索算法来计算最优解。

状态

对于游戏状态，抽象成 S=(t,R,P,I) ，各含义如下：

• t是一个数值，代表游戏的时间（帧数）
• R是一个向量，代表各种资源占用情况，例如当前游戏有3个兵工厂，其中两个是可用的，另一个进行生产，一分钟后才变为可用
• P是一个向量，存放已经安排但尚未执行的动作，例如正在建造补给站，还需30秒才能建完
• I是一个向量，指示工人的状态。例如有8个工人正在挖晶体矿（mineral），另有3个正在收集油矿（gas）

通过抽象，程序便能够使用较为简单的数值来表达游戏状态，虽然这样的表达简化了很多内容，却也降低了计算量，游戏AI程序的运行速度不能太慢，才能够做到实时操控

动作

• 对于建造有关的操作，使用 a=(δ,r,b,c,p) 来抽象，各个符号的含义如下
• δ 是一个数值，代表动作的持续时间（帧数），例如建一个士兵需要10秒
• r、b、c代表执行该动作的各种先决条件，其中 r 指required（需要建好哪些东西），b指borrowed（需要借用哪些资源），c指consumed（需要消耗的资源）。
• p指执行该动作后会产生的东西

举例来说，对于“生产一个神族的龙骑兵”（Produce Protoss Dragoon）这么一个动作，而言

• 生产总共需要600帧，所以δ = 600
• 必须先有建有控制核（Cybernetics-Core）才能建造，所以r = {Cybernetics-Core}
• 建造过程中需使用兵营，“借用”兵营的生产力一小段时间，因此b = {Gateway}
• 建造它需要消耗125个晶体矿，50个铀矿，还算2个人口，因此c = {125 minerals, 50 gas, 2 supply}
• 动作执行完毕会产生一个龙骑士，因此p = {1 Dragoon}

玩法的抽象

在实际的游戏中，建造过程和收集资源的过程都较难用数学去表达，因为建造和收集过程中，需要派遣工人，让工人走到目的地，然后建造或收集，对于收集，工人还需要把矿物拿回基地，这个过程会涉及资源的位置、地图寻路，比较复杂。因此，做了一些适当的简化，如下所示。

• 对于晶体矿收集，固定设置为每个工人每帧收集0.045个
• 对于油矿收集，固定设置为每个工人每帧收集0.07个
• 对于每个建筑，默认加上4秒的建造时间，以模拟工人走路花费的时间

状态转换

对于游戏的状态转换，做出如下三种抽象：

1. S′←Sim(S,δ) ，模拟从状态S开始，没有操作的经过δ时间，最后变为S'状态
2. δ←When(S,R) ，当前状态为S，它需要R资源，该抽象计算出达成该资源所需的时间δ，例如有3个工人在收集矿石，它需要多少时间才满足建一个兵营
3. S′←Do(S,a) ，当前状态为S，且执行动作a的条件已满足，执行动作a，使状态变为S'

综合起来即可得到状态转换函数 S′=Do(Sim(S,When(S,a)),a)，既想执行动作a，先计算满足条件所需的时间，然后等待条件满足，最后执行。

搜索算法

在做好抽象定义之后，即可从当前游戏状态（S）开始，找出达成建造目标（G）的方法，具体是通过深度优先搜索（depth-first recursive search），递归遍历当前状态下可能的发生的动作，具体算法如下：

• 2-4行：其中的TimeElapsed是为算法效率考虑，限制它执行的时间，以适应游戏的实时性；
• 9-17行：递归搜索的过程，遍历S下可能执行的动作（while S has more children do），针对该动作形成的新局面S'，递归调用（ DFBB(S') ）。其中h←eval(S')是启发式评估的过程，目的是加快搜索速度，只对S'+h
• 5-7行：当遍历到目标局面G，即返回最优的动作序列bestSolution。

这么做法还有个问题，实际游戏是多个动作并行处理，不过要做到并行处理动作的计算量很大，算法中采用串行来模拟并行，公式如下所示，即将a和b动作的并行视为有顺序的执行。

Do(S,a+b)=Do(Do(S,a),b)

UAlbertaBot将以上算法封装成一个成为BOSS的子系统，上层可以直接调用，输入当前局势和目标，它会返回搜索到的动作序列。

文章会分如下几篇

1. 架构和规则，宏观介绍UAlbertaBot的原理
2. 建造顺序搜索，介绍使用深度搜索算法去找到最优建造顺序的方法
3. 战斗模拟评估，介绍模拟队伍作战评估能否获胜的方法
4. starterbot，一个最简单的机器人，从中理解最基础星际AI的写法
5. 策略制定，策略制定部分的代码分析
6. 建造实现，生产、建造相关系统的代码分析
7. 战斗实现，战斗相关代码分析
8. 寻路算法，地图相关代码的分析

下面又到广而告之的时间啦，《Unity3D网络游戏实战》是一本很好的书籍，作者花费很多时间编写的呢，教你从零开始开发一款多人对战游戏，很有特色。网上其他资料大多教怎么做单机游戏，而这本书会说明制作网络游戏的方法，很值得阅读。