齊彥君，張冰怡，馮志勇

(1.天津大學軟件學院，天津 300072;2.中國民航大學中國民航信息技術科研基地，天津 300300;3.天津大學計算機科學與技術學院，天津 300072)

0 引言

隨著計算機和智能手機的發(fā)展和普及，游戲已經成為一種非常受歡迎的娛樂方式并呈現(xiàn)出爆炸式的增長態(tài)勢。游戲開發(fā)成為一個快速發(fā)展的行業(yè)。游戲開發(fā)的過程中，游戲關卡的設計是游戲開發(fā)的重點。但是如果所有關卡都由設計師逐一設計將花費大量的時間和資金。所以，關卡自動生成技術被應用于游戲關卡的開發(fā)中，大大降低了游戲的開發(fā)成本。

根據(jù)互聯(lián)網消費調研中心發(fā)布的《2011年中國網絡游戲黏著度及壽命調查報告》顯示，游戲用戶黏著度仍然低迷，大部分用戶因游戲缺乏新鮮感而在3個月內流失[1]。出現(xiàn)該現(xiàn)象的原因，主要是因為沒有充分考慮游戲用戶玩游戲時得到的游戲玩法數(shù)據(jù)。數(shù)據(jù)挖掘與數(shù)據(jù)融合同為數(shù)據(jù)處理方法，在手段、功能上各有側重。數(shù)據(jù)挖掘是運用歸納的思想從已有的數(shù)據(jù)中發(fā)現(xiàn)知識;而數(shù)據(jù)融合則是以演繹的思想實現(xiàn)對知識的應用，并獲取新的數(shù)據(jù)[2-3]。本文提出了一種基于結合屬性約簡的數(shù)據(jù)挖掘和數(shù)據(jù)融合的關卡自動生成技術，用于動態(tài)生成游戲關卡，既可以降低游戲的開發(fā)成本，又引入了玩家的游戲玩法數(shù)據(jù)，更容易讓玩家喜歡上該游戲。

1 研究背景

1.1 游戲關卡設計現(xiàn)狀

現(xiàn)有的游戲關卡設計大都是由關卡設計師逐一設計開發(fā)出來的，這需要花費大量的時間和資本。國外的一個著名的關卡設計模型中，提出在關卡設計過程中，藝術學、工程學和設計學起到了非常重要的作用[4]。但是在一個以玩家為最終對象的模型中缺少對玩家在玩游戲時適應程度的分析，因此，需要把玩家的游戲玩法數(shù)據(jù)作為游戲關卡設計的重要參考信息。

1.2 決策樹算法

決策樹算法是數(shù)據(jù)挖掘[5]領域中一個非常重要的研究課題，它是一種以實例為基礎，用于分類、聚類和預測的歸納學習方法。它的功能是根據(jù)研究對象的屬性值和其它約束條件，構造一棵反映目標屬性識別的決策樹，正好可以解決評估玩家對于游戲的難易程度問題，并且多年來數(shù)據(jù)挖掘方面的研究者的研究工作也說明了決策樹算法能很好地用于對目標屬性的識別[6]。決策樹算法發(fā)展至今，已經積累了大量的算法，它們各有優(yōu)勢，各有特點。考慮到系統(tǒng)需要實時生成游戲關卡，ID3算法可以很好地完成游戲難易程度的識別，并且相對比較高效。

ID3分類算法由Quinlan于1986年提出，使用信息增益作為屬性選擇標準，采用一種自頂向下、貪婪的搜索方法[7-8]。首先檢測所有屬性，選擇信息增益值最大的屬性產生決策樹節(jié)點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調用該方法建立決策樹節(jié)點的分支，直到所有子集僅包含同一個類別的數(shù)據(jù)為止，最后得到一顆決策樹，用來對新的測試數(shù)據(jù)進行分類，即用于關卡信息生成模塊[9-10]。

1.3 數(shù)據(jù)融合技術

在游戲關卡設計中，由于需要融合幾個關卡的游戲玩法數(shù)據(jù)，獲取更能代表游戲玩家對游戲的難易程度的數(shù)據(jù)，并不利用數(shù)據(jù)融合技術來直接確定游戲的難易程度。因此，根據(jù)各個不同的數(shù)據(jù)融合算法的特點，選擇D-S證據(jù)理論[11]作為對游戲玩法數(shù)據(jù)進行融合的算法。

2 基于數(shù)據(jù)挖掘和融合技術的游戲關卡生成方法設計

玩家的游戲玩法數(shù)據(jù)(即用戶玩游戲時產生的相關數(shù)據(jù))對玩家和開發(fā)者都有著重要的意義，在這些數(shù)據(jù)中隱藏著游戲設計中可用的規(guī)則知識。研究如何發(fā)現(xiàn)和挖掘游戲玩法數(shù)據(jù)中的規(guī)則知識將會提高游戲的自動化和智能化程度。針對游戲玩法數(shù)據(jù)的特點，利用數(shù)據(jù)挖掘和數(shù)據(jù)融合相結合的技術[12-13]處理游戲玩法數(shù)據(jù)，得到該游戲對于游戲玩家的難易程度，然后利用該信息自動生成設計游戲關卡所需要的數(shù)據(jù)。有效利用這兩種技術，可降低游戲開發(fā)成本并提高游戲的可玩性。

本文提出了一種基于數(shù)據(jù)挖掘和數(shù)據(jù)融合的游戲關卡自動生成方法，該方法的實現(xiàn)流程如圖1所示，主要包括游戲玩法數(shù)據(jù)收集、數(shù)據(jù)預處理、基于信息增益的屬性約簡、決策樹的建立、游戲玩法數(shù)據(jù)的融合、游戲關卡自動生成等。其中，數(shù)據(jù)挖掘過程中提出了一種新的基于信息增益的屬性約簡算法用于去除游戲玩法數(shù)據(jù)中的冗余屬性;數(shù)據(jù)融合過程將對來自于不同關卡的幾條數(shù)據(jù)進行融合，得到新的數(shù)據(jù)，并且再放入訓練數(shù)據(jù)中，使訓練數(shù)據(jù)更完備、更準確，降低了訓練數(shù)據(jù)的模糊性和不確定性，再次進行數(shù)據(jù)挖掘所獲得的決策樹也更為準確。

圖1 系統(tǒng)流程圖

本文以經典的推箱子游戲為例進行實驗，驗證游戲關卡的自動生成方法。

2.1 游戲玩法數(shù)據(jù)的獲取

利用數(shù)據(jù)挖掘從推箱子游戲玩法數(shù)據(jù)中獲取游戲的難易程度的識別情況，首先要對每個關卡中所獲取的信息進行分析，得到與游戲難易程度有關的關卡屬性，同時獲得玩家在玩整個關卡時得到的信息。下面列出了通過分析得到的每一條游戲玩法數(shù)據(jù)的條件屬性及代號:

(1)玩家是否通過該關卡a1;

(2)玩家玩該關卡時使用的步數(shù)a2;

(3)該關卡中箱子的個數(shù)a3;

(4)該關卡中地圖的大小a4;

(5)該關卡中障礙物的個數(shù)a5;

(6)該關卡中箱子的分散度a6(即箱子在關卡中分布的情況)。

另外，需要獲取的目標屬性為:該關卡的難易程度d，分為困難、中等和容易3個等級。

當屬性選擇完成后，就需要按照該屬性表獲取數(shù)據(jù)。對于目標屬性是由玩家在該關卡結束時通過主觀選擇得到的，即在游戲源代碼的基礎上加入一個選擇游戲關卡難易程度的功能;其余屬性則通過向游戲源代碼中加入數(shù)據(jù)獲取模塊的代碼來完成。

得到的游戲玩法數(shù)據(jù)必須用信息表的形式描述出來，本系統(tǒng)共獲取了1000條數(shù)據(jù)。縱軸表示實例標記，橫軸表示條件屬性和目標屬性，實例標記與屬性的交點就是該條實例在該屬性的值。這樣就可以得到一張包含1000個實例、6個條件屬性和1個目標屬性的信息表。由于原始表格較大，表1是部分樣本的信息。其中，目標屬性中分別用1、2、3來標記容易、中等和困難3類屬性值;條件屬性中分別用1、2來標記通過關卡和未通過關卡兩類屬性值。

表1 原始信息表(只包含部分樣本)

2.2 數(shù)據(jù)預處理

在運用數(shù)據(jù)挖掘技術進行數(shù)據(jù)處理時，要求使用離散的數(shù)據(jù)，因此在進行數(shù)據(jù)處理時首先要進行數(shù)據(jù)的預處理，即數(shù)據(jù)的離散化處理。離散化處理后的數(shù)據(jù)不僅可以使運算量縮減，還能在一定程度上降低噪聲。本文利用布爾邏輯和粗糙集理論相結合的離散化算法[14]對原始數(shù)據(jù)進行離散化處理得到新的信息表，如表2所示。

表2 離散化后的信息表(只包含部分樣本)

2.3 基于信息增益的屬性約簡

數(shù)據(jù)經過預處理后，在作為數(shù)據(jù)挖掘模塊中的訓練數(shù)據(jù)之前，由于所獲得的游戲玩法數(shù)據(jù)的屬性中可能存在與目標屬性無關或冗余的屬性，因此本文提出了一種基于信息增益和屬性相關性的屬性約簡算法。定義屬性相關系數(shù):

其中，Gain(ai)是按屬性ai劃分數(shù)據(jù)集所得的信息增益;Gain(ai，aj)是按屬性ai和aj聯(lián)合劃分數(shù)據(jù)集所得的信息增益。該屬性約簡算法描述如下:

輸入:訓練數(shù)據(jù)T，訓練數(shù)據(jù)屬性集合P。

輸出:處理后的數(shù)據(jù)T'，選擇后的屬性集合P'。

方法:

(1)for屬性集合P的個數(shù)do

(2)計算每個屬性與目標屬性的相關系數(shù)ρ

(3)end for

(4)將ρ按降序排列

(5)for屬性集合P的個數(shù)do

(6)for剩余屬性的個數(shù)do

(7)計算所選屬性與其他屬性的相關性，若ρ(ai，aj)≥ρ(ai，d)，則將屬性aj從P中刪除，直到所有冗余屬性被刪除

(8)end for

(9)end for

由該屬性約簡算法可以得出，關卡地圖的大小屬性a4為系統(tǒng)的冗余屬性，則刪除屬性a4，即把離散化后的信息表中的該屬性對應的列數(shù)據(jù)刪除掉，得到用于決策樹算法的數(shù)據(jù)。

2.4 建立決策樹

在收集的1000條數(shù)據(jù)中，游戲難易程度為“容易”、“中等”、“困難”3類目標的子集數(shù)分別為:S1=260，S2=450，S3=290。首先計算數(shù)據(jù)集S的熵值:

然后計算各個條件屬性的信息增益，以條件屬性“使用的步數(shù)a2”為例，分別計算它為little、center和much三個類別的熵，最終得到條件屬性的信息增益值。

當?shù)貓D大小為little時:

條件屬性地圖大小的信息增益為:

根據(jù)計算地圖大小的信息增益的方法，同理，其他條件屬性的信息增益分別為:

由以上對信息增益的計算結果可見，條件屬性“是否通過該關卡a1”的信息增益最大，因此將該屬性作為決策樹的根結點進行測試;同時根據(jù)該屬性可以將訓練數(shù)據(jù)集分為2個分支。根據(jù)遞歸方法建立決策樹，并對決策樹進行后剪枝，得到最終的決策樹，如圖2所示。

圖2 判定游戲難易程度的決策樹

使用得到的游戲玩法數(shù)據(jù)對決策樹的識別情況進行測試，選取游戲難易程度為容易、中等和困難3個目標屬性值樣本各30個，共90個測試樣本，得到的識別率如表3所示。

表3 決策樹的識別率

由表3可得，建立的決策樹可以很好地完成對游戲難易程度的識別。

2.5 游戲玩家數(shù)據(jù)的融合

數(shù)據(jù)融合是指對多組傳感器數(shù)據(jù)進行多級別、多方面、多層次的處理和組合，從而產生新的有意義的信息[15]，這里的傳感器是廣義的，可以指各種數(shù)據(jù)獲取系統(tǒng)和相關數(shù)據(jù)庫等，在本文中指玩家玩每一個關卡所得到的數(shù)據(jù)。

在數(shù)據(jù)融合模塊中，主要的目的就是融合玩家在多個關卡中的數(shù)據(jù)，得出一條新的、可以更有效地代表玩家行為的數(shù)據(jù)。根據(jù)關卡所得到的數(shù)據(jù)的特點，選擇D-S證據(jù)理論作為數(shù)據(jù)融合的算法[11]。由于每一個關卡得到的數(shù)據(jù)不能直接利用數(shù)據(jù)融合算法進行融合，首先，需要對數(shù)據(jù)進行處理:信息增益代表了屬性特征對系統(tǒng)的重要性，因此，系統(tǒng)利用信息增益對關卡數(shù)據(jù)進行處理，定義關卡數(shù)據(jù)為D[n]，數(shù)據(jù)挖掘得到的各屬性的信息增益為Gain[n]，各屬性的最大值為 Max[n]，處理后的關卡數(shù)據(jù)為 Data[n]，那么處理規(guī)則為:

其中，n為屬性的個數(shù)。

然后，利用D-S證據(jù)理論算法對數(shù)據(jù)處理進行融合后得到一條新的更能代表玩家行為的數(shù)據(jù)。最后，把該條數(shù)據(jù)轉換成一條與關卡數(shù)據(jù)格式相同的數(shù)據(jù)，用于關卡信息生成模塊并且把該條數(shù)據(jù)再放入訓練數(shù)據(jù)中以完善訓練數(shù)據(jù)集。

2.6 關卡信息生成模塊

在關卡信息生成模塊中，利用數(shù)據(jù)融合模塊生成的新的關卡數(shù)據(jù)作為決策樹的測試數(shù)據(jù)，從而得到游戲對于玩家的難易度，然后根據(jù)難易度來設置關卡信息。設置的規(guī)則為:如果難易度結果為容易，則提高關卡的難度，即關卡中箱子的個數(shù)和障礙物的個數(shù)都加1;如果難易度結果為中等，則保持關卡的難度，但是要改變關卡的一些數(shù)據(jù)信息，即改變箱子和目的地的位置以及地圖的形狀;如果難易度結果為困難，則降低關卡的難度，即關卡中箱子的個數(shù)和障礙物的個數(shù)都減1。最后，根據(jù)關卡信息自動生成新的更適合玩家的關卡，如圖3所示。

圖3 自動生成的關卡圖

自動生成關卡的原則為:游戲程序中提供沒有箱子、障礙和目的地的關卡形狀模板庫，首先根據(jù)得到的難易度選擇模板，然后根據(jù)關卡信息向關卡模板中放置箱子、障礙物和目的地，最終得到一個新的關卡。

3 實驗結果與分析

為了驗證系統(tǒng)的有效性，本文以經典的推箱子游戲為例進行實驗。關卡數(shù)據(jù)包括7個屬性，通過對部分玩家測試得到了1000條關卡數(shù)據(jù)。對于傳統(tǒng)的游戲中100個關卡都需要關卡設計師逐一設計，會花費大量的時間和資本;而利用本文的關卡自動生成系統(tǒng)，只需提前設計好幾個關卡，其余通過該系統(tǒng)動態(tài)生成，大大降低了開發(fā)時間和成本。

針對游戲的可玩性，本實驗通過對50個玩家進行測試，每個玩家分別玩?zhèn)鹘y(tǒng)的推箱子游戲和基于關卡自動生成系統(tǒng)的推箱子游戲，記錄玩家通過的關卡數(shù)，結果如圖4所示。

圖4 實驗結果

圖4中，縱坐標為玩家通過的關卡數(shù)，橫坐標為玩家編號。由圖中數(shù)據(jù)可得，基于關卡自動生成系統(tǒng)的推箱子，更適合玩家的需求。因此，基于數(shù)據(jù)挖掘和數(shù)據(jù)融合的關卡自動生成系統(tǒng)可以有效提高游戲的可玩性。

4 結束語

傳統(tǒng)的推箱子游戲，由于關卡信息是由設計師提前設計好的，所以，游戲開發(fā)花費大量的時間和成本并且可玩性比較差。實驗證明，本文提出的基于結合屬性約簡的數(shù)據(jù)挖掘和數(shù)據(jù)融合技術的場景自動生成系統(tǒng)可以有效降低開發(fā)成本并提高游戲的可玩性。下一步的工作是進一步研究該系統(tǒng)在其他類型游戲中的效果。例如，在《暗黑》的地下城中的某個寶箱所呈現(xiàn)的道具取決于玩家打開寶箱的時間。這種生成技術可以被運用到游戲制作的大部分過程中，如法術制作、道具制作、武器制作、NPC對話系統(tǒng)以及屏幕上呈現(xiàn)的法術效果等。

[1] 王川.2011年中國網絡游戲黏著度及壽命調查報告[EB/OL].http://zdc.zol.com.cn/246/2468679.html，2011-08-31.

[2] 王璿，高社生，趙霞.數(shù)據(jù)挖掘與數(shù)據(jù)融合集成系統(tǒng)模型[J].計算機工程與應用，2006，42(18):181-183.

[3] 何劍斌，鄭啟倫，彭宏.數(shù)據(jù)融合與數(shù)據(jù)挖掘的集成研究[J].計算機工程與應用，2002，38(18):204-206.

[4] Andy Clayton.Introduction to Level Design for PC Games[EB/OL]. http://www.loc.gov/catdir/toc/ecip041/2003006916.html，2007-06-24.

[5] 邢東山，沈鈞毅，宋擒豹.從Web日志中挖掘用戶瀏覽偏愛路徑[J].計算機學報，2003，26(11):1518-1523.

[6] 袁霖，王懷民，尹剛，等.開源環(huán)境下開發(fā)人員行為特征挖掘與分析[J].計算機學報，2010，33(10):1909-1918.

[7] 楊育彬，李寧，張瑤.基于社會網絡可視化分析的數(shù)據(jù)挖掘[J].軟件學報，2008，19(8):1980-1994.

[8] 姜文瑞，王玉英，郝小琪，等.決策樹方法在氣溫預測中的應用[J].計算機應用與軟件，2012，29(8):141-144.

[9] 徐寶文，張衛(wèi)豐.數(shù)據(jù)挖掘技術在Web預取中的應用研究[J].計算機學報，2001，24(4):430-436.

[10] 連一峰，戴英俠，王航.基于模式挖掘的用戶行為異常檢測[J].計算機學報，2002，25(3):325-330.

[11] 張曉明，王航宇，黃達.基于D-S證據(jù)理論的多平臺協(xié)同數(shù)據(jù)融合[J].計算機工程，2007，33(11):242-243，246.

[12] 劉欽啟，馬玉祥，郝紅俠.基于數(shù)據(jù)融合和數(shù)據(jù)挖掘的網絡故障管理系統(tǒng)[J].微電子學與計算機，2006，23(6):74-76，80.

[13] 巫莉莉，徐艾潔，張波，等.基于數(shù)據(jù)融合和數(shù)據(jù)挖掘的網絡教學資源體系[J].重慶工學院學報:自然科學版，2008，22(6):170-172，175.

[14] 程一倫.基于粗糙集的數(shù)據(jù)離散化方法研究[D].長春:吉林大學，2009.

[15] 陳超，李俊，孔德光.基于數(shù)據(jù)融合的源代碼靜態(tài)分析[J].計算機工程，2008，34(20):66-68.