DOTA游戏中的智能装备合成算法的设计与实现

吴德堪，周春良（宁波大红鹰学院信息工程学院，宁波 315175）

DOTA游戏中的智能装备合成算法的设计与实现

吴德堪，周春良
（宁波大红鹰学院信息工程学院，宁波 315175）

0　引言

目前DOTA中有超过152种不同的装备，每一件装备具有其各自的金钱价格，上至五六千下至50金不等。装备大致可分为三种：基础装备、合成装备、消耗品。

基础装备：是指价格一般不高且直接可以购买的装备；

合成装备：区分于基础装备，是指需要通过一件或多件基础装备加上零个或一个合成卷轴来进行合成的高级装备；

消耗品：顾名思义是指类似于药水、守卫、传送卷轴之类的具有使用次数限制的道具，显然此类道具不在装备合成的范围之内。

就是这样简简单单的通过多个低等级装备合成一个高等级装备的方式，大大增加了游戏的趣味性和扩展性，彻底改变了之前单一的直接购买装备的形式。虽然人们不难地设计了这样的一种游戏规则，但是要在游戏中具体地实现它并非易事［1］。

1　简单合成算法

1.1简单合成算法的一般式模型

为了增加游戏的趣味性和代入感，同时也为了防止不同装备在合成过程中可能出现的混淆问题，在DOTA中引进了“卷轴”的概念，部分装备在合成的过程中需要购买欲合成装备的合成卷轴才能合成该装备。

首先我们先列出所有可能的装备合成类型如下［2］：

a+…=C

a+…+合成卷轴=C

n*a+n*b+…=C，n∈［0，∞）

n*a+n*b+… +合成卷轴=C，n∈［0，∞）

对应实例：

圣者遗物+恶魔刀锋=圣剑

圣者遗物+水晶剑+代达罗斯之殇合成卷轴=代达罗斯之殇

治疗指环+两个回复戒指+抗魔斗篷=挑战头巾

两个秘银锤+黯灭合成卷轴=黯灭

我们对其进行优化，因为可以将合成卷轴看成一种不具备任何属性的“基础装备”，它与其他所有基础装备一样需要用金钱购买，只是它不具备任何功能。然后我们将多个相同种类的装备相乘看做相加，即（N*A）-＞（A+A+A+…+A（N个A）），之所以这样做是为了尽量非特殊化，这对于后面的代码编写思路有着很大的帮助，而且现在就可以看出来这样做的好处了：经过我们的两步优化工作，我们已经将四个式子合并成为了一个一般式：

在实现合成算法之前必须要建立装备的数据结构模型，这个数据结构模型应该告诉计算机两件事情：“哪些装备能合成哪个装备”和“哪个装备能被哪些装备合成”。所以这个数据结构模型大致可以表示为如下图所示：

图1　

DOTA是在魔兽争霸3引擎下的自定义地图，其脚本语言并非是面向对象的C++，而是倾向过程化的以创建触发器的形式为主导的JASS语言。不仅仅在DOTA中，而且这种道具合成的元素还存在于各大DOTA类游戏中，其编程语言更是不一。不过万变不离其宗，其中的逻辑道理都是相同的，接下来我们逐条解析。

1.2简单合成算法的实现

在简单合成算法中，假设我们需要合成一个物品A，我们称之为目标物品。首先，我们有一个检查函数，来判断玩家持有的物品是否符合合成条件，我们称这个函数为ItemUpgradeCondition。其次，我们给这个函数输入两个参数，一个是英雄句柄，一个是目标物品的ID（或种类、或句柄、或标记，这取决于数据结构中物品之间的联系方式，例如在DOTA中就是用256进制的物品序号作为关键钥匙）。

在ItemUpgradeCondition中，我们首先得到两个形参：英雄句柄和目标物品的ID，通过之前建立的数据结构模型，我们顺着目标物品的ID能够找到所需配件，例如“A+B+C+D=目标物品”，或者“A+A+A+B=目标物品”。接着在英雄的身上依次寻找是否拥有所需条件，若条件全部满足则返回真，否则为假。若返回为真则还需在返回之前记录下依次寻找到的物品句柄，这样以便于接下来的操作［3］。

当一个英雄做了一个有可能合成物品的动作时，例如购买物品、拾取物品，则运行ItemUpgradeConidition函数，若检查结果为真，则将记录内的物品删除，并给予目标物品，即完成合成。若为假则不做任何动作。

2　智能合成算法

在游戏突飞猛进发展的今天，对于上述的简单合成算法，早已不能满足玩家的需求。因为仅使用上述的算法，会出现一个非常不友好的人机交互问题，更是当今DOTA仍然存在的一个巨大的漏洞：当玩家拥有足够金钱并且想要合成高级装备时，仍需依次购买配件，例如合成魔杖需要：树枝+树枝+树枝+魔棒+魔杖卷轴。不仅如此，更糟糕的是，在DOTA游戏规则中，一名英雄只能同时携带6件物品，超出时便不能拾取物品并出现系统提示“物品栏已满”。甚至实战情况的更加复杂，DOTA中还存在运输信使和储藏室，玩家的物品可能不在自己身上而放置在信使中，甚至可能掉落在地上或者暂时共享给队友使用（例如医疗指环）。

对于这样的情况，我们得采用更加智能的算法来解决玩家实际操作中遇到的问题。我们将这复杂的情况进行分析得出：玩家在合成物品时总存在多余的步骤，例如：（1）在金钱足够时还需使用金钱购买中间道具如用来合成魔杖的树枝；（2）得将物品放置在自己身上才能进行合成判定；（3）若金钱只够购买中间道具仍需玩家手动操作，尽管系统已经知道了玩家的目标道具。

针对这三种多余的步骤，我们采取以下的解决方案：（1）在金钱足够时，自动为玩家购买中间道具。（2）自动寻找可能范围内归玩家所有的中间道具。（3）若金钱不够购买目标道具却能够购买中间道具时自动为玩家分发合适的中间道具，而不是提示“金钱不足”。

因此我们改进ItemUpgradeCondition函数：我们将是否持有中间道具拓展为两个或命题：持有中间道具或持有等量金钱，前者优先级大于后者，若前者为否则需并记录金钱数量。当所有条件都为真，则扣除统计的金钱数量，此时玩家便不需要原本的自助操作了。每当一个物品被创建、删除时都记录其持有者和所有者。并且每一位玩家拥有自己的所拥有的物品列表，当一个物品被自己所拥有或失去时则从自己的物品列表中添加或删除该物品。

3　实例

例如玩家身上携带了5件物品并剩余一个空位，欲购买一件新的物品——魔杖，看似轻而易举的情况却在DOTA中实际操作得将其余物品一件一件地扔在地上以空出4个空位，然后再依次购买树枝、树枝、树枝、魔棒，最后点击魔杖卷轴来完成新增一件魔杖物品的操作。

在《英雄争霸》这款魔兽地图中，改进后的智能物品机制已经被应用到实际中，在任何复杂的情况下，玩家合成高级物品所需的多余操作步骤都已被弃除，如上述例子，在智能的装备合成系统下，无论玩家处于没有足够格子放置中间物品或是中间物品暂时不在身上时，只要你一次点击的操作，智能系统就会自动为你找到所需条件。

4　结语

这一系列的改进离不开一个根本原因：以玩家为出发点。正是解决了玩家在操作游戏中遇到的不舒服的问题，才能确保玩家能够享受到应有的乐趣。这就是智能的装备合成系统的作用所在。

［1］吕森林.教育游戏产业研究报告［J］.中国远程教育，2004

［2］曹晶瑜.学习者特征分析对教育游戏设计的启示［J］.天水师范学院学报，2010

［3］丁展.Visual C++游戏开发技术与实例［M］.北京：人民邮电出版社，2001

DOTA Equipment Synthesis；Intelligent Algorithm；JASS Language

Design and Implementation of Intelligent Equipment Synthesis Algorithm in DOTA Game

WU De-kan，ZHOU Chun-liang
（College of Information Engineering，Ningbo Dahongying University，Ningbo 315175）

1007-1423（2015）10-0063-03

10.3969/j.issn.1007-1423.2015.10.018

吴德堪（1995-），男，浙江永康人，在读本科，研究方向为网络游戏设计与编程

2015-02-05

2015-03-05

以玩家视角为出发点，提出能够解决玩家实际游戏过程中存在多余操作问题的智能装备合成算法。该算法解决目前DOTA游戏中存在的一些问题，将DOTA中复杂的装备系统提炼，并深度考虑DOTA中复杂的游戏环境，最终实现用智能系统执行来代替复杂的游戏操作。并将这一智能合成算法应用在自主研发的实际游戏中，验证算法的可行性。

DOTA装备合成；智能算法；JASS语言

周春良（1982-），男，浙江宁波人，硕士，研究方向为算法设计与分析

In the viewpoint of game players，puts forward intelligent equipment synthesis algorithm to solve the actual game excess operation problems in the process of the game.The algorithm solves some problems in current DOTA game，the complex equipment system in it，and deep consideration in DOTA complex game environment，realizes the use of intelligent system instead of a complex game operation.And applies the intelligent synthesis algorithm in independent research and development of the actual game，verifies the feasibility of the algorithm.