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.