游戲開發(fā)中常用的數(shù)據(jù)結(jié)構(gòu)淺析

李俊琴

摘要：數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)軟件開發(fā)和應(yīng)用人員必備的專業(yè)基礎(chǔ)。游戲程序是一種復(fù)雜度較高的計(jì)算機(jī)軟件，因此其中的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)非常重要。該文對游戲開發(fā)中常用的方法進(jìn)行總結(jié)，分析了數(shù)組、鏈表、棧、隊(duì)列、樹等等數(shù)據(jù)結(jié)構(gòu)在游戲中的應(yīng)用。

關(guān)鍵詞：游戲開發(fā)；數(shù)據(jù)結(jié)構(gòu)；鏈表

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）27-6483-02

Abstract： Data structure and algorithm is a professional basic ability of computer software development and application of personnel necessary. The game program is a kind of high complexity of computer software， so the data structure design is very important. In this paper， the method commonly used in game development are summarized， analyzed the application of array， linked list， stack， queue， tree data structure in game program.

Key words： game program；data struct； linked list

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式，是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在軟件開發(fā)中，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)合理可以帶來更高的運(yùn)行或者存儲效率。游戲軟件區(qū)別于一般的普通應(yīng)用軟件，它要求響應(yīng)更快速，計(jì)算更精確，通常要組織、管理更多媒體資源。因此數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，在游戲開發(fā)中非常重要。該文從常用的數(shù)據(jù)結(jié)構(gòu)入手，分析它們在游戲開發(fā)中的實(shí)際應(yīng)用。

1 數(shù)組

數(shù)組是最簡單的數(shù)據(jù)結(jié)構(gòu)，很容易理解。在程序設(shè)計(jì)中，常常把具有相同類型的若干變量按數(shù)組的形式組織起來。數(shù)組元素的查找要按照索引順序依次進(jìn)行；根據(jù)已知索引來讀取數(shù)組元素非常方便；插入刪除操作都要維持?jǐn)?shù)組元素原來的約定，因此需要移動較多元素。數(shù)組中的元素也可以是數(shù)組類型，這就構(gòu)成了二維數(shù)組、多維數(shù)組。

數(shù)組的排序有很多算法，因此很多游戲中需要排序的功能就可以由數(shù)組來實(shí)現(xiàn)。例如游戲中的某種分值排行功能、對某種屬性選取最值的功能等，都可以用一維數(shù)組來實(shí)現(xiàn)。

用二維數(shù)組來表示地圖，是目前很多類型游戲設(shè)計(jì)中常用的方法。例如推箱子游戲的地圖、塔防游戲的地圖、酷跑類游戲的地圖、棋盤類游戲的棋盤等等，都可以由二維數(shù)組的方式來實(shí)現(xiàn)。以推箱子游戲?yàn)槔瑘D1是某關(guān)卡的顯示界面，圖2是程序代碼中二維數(shù)組表示的地圖：

如圖1所示，游戲界面中展示出推箱子游戲中所有的元素，包括通道、墻、箱子、人物等等。在游戲進(jìn)行中，玩家按下方向鍵，人物要相應(yīng)地推動箱子并移動，游戲界面要相應(yīng)地變化，這是推箱子游戲應(yīng)該完成的基本功能。使用二維數(shù)組來描述地圖數(shù)據(jù)，可以很好地完成這一功能。如圖2所示，對地圖中所有的元素進(jìn)行分析，可以得到8種類型，由數(shù)字編碼0-7來表示。之后根據(jù)游戲地圖大小，設(shè)計(jì)m行n列的二維數(shù)組，其中各元素就是8種地圖類型的編碼。按照當(dāng)前關(guān)卡初始地圖的樣子，就可以得出如圖2中的原始地圖數(shù)據(jù)。在游戲進(jìn)行中，玩家按鍵導(dǎo)致人物移動后，可以根據(jù)推箱子的游戲邏輯相應(yīng)地修改某些地圖數(shù)據(jù)中的元素，之后游戲按照新的地圖數(shù)據(jù)更新游戲界面即可。需要注意的是，關(guān)卡的原始地圖數(shù)據(jù)不能改變，否則下次游戲無法進(jìn)行，因此在游戲中修改的應(yīng)該是原始地圖的臨時拷貝。

2 鏈表

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表中每一個元素稱為結(jié)點(diǎn)，每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。鏈表由一系列結(jié)點(diǎn)組成，節(jié)點(diǎn)可在需要時動態(tài)生成。由于這些特點(diǎn)，鏈表的查找一定要依節(jié)點(diǎn)次序進(jìn)行；鏈表的插入、刪除操作非常方便；鏈表不需要在一開始就占用很多空間，隨程序運(yùn)行需要動態(tài)創(chuàng)建即可。

在游戲中，很多游戲元素需要頻繁的出現(xiàn)、消除，其個數(shù)是難以預(yù)料的。例如射擊類游戲中出現(xiàn)的敵機(jī)、子彈，消除類游戲中的消除對象以及RPG游戲中出現(xiàn)的電腦角色等等。根據(jù)鏈表在插入、刪除數(shù)據(jù)，可隨程序運(yùn)行動態(tài)創(chuàng)建數(shù)據(jù)的特點(diǎn)，在游戲開發(fā)中常常用鏈表來維護(hù)、管理那些需要頻繁產(chǎn)生、消除的游戲?qū)ο蟆?/p>

以射擊類游戲?yàn)槔?，游戲中可以用鏈表來表示游戲中的敵機(jī)、子彈。在游戲開始時，創(chuàng)建一個敵機(jī)的鏈表、一個子彈鏈表，其中的元素個數(shù)為0，即敵機(jī)個數(shù)為0，子彈個數(shù)為0；隨著游戲時間的推進(jìn)，敵機(jī)出現(xiàn)，程序中創(chuàng)建相應(yīng)的敵機(jī)節(jié)點(diǎn)放入敵機(jī)鏈表；由于敵機(jī)的出現(xiàn)，攻擊的子彈也要相應(yīng)地出現(xiàn)，程序中此時創(chuàng)建相應(yīng)的子彈節(jié)點(diǎn)加入子彈鏈表；當(dāng)攻擊子彈與敵機(jī)發(fā)生碰撞，子彈和敵機(jī)都應(yīng)該消失，此時程序應(yīng)根據(jù)當(dāng)前子彈、敵機(jī)指針，找到鏈表中的相應(yīng)節(jié)點(diǎn)刪除，更新鏈表。如果敵機(jī)、子彈的數(shù)量較多，創(chuàng)建、刪除操作太頻繁，還可以將敵機(jī)、子彈的鏈表分為存活鏈表和死亡鏈表兩種，并在結(jié)點(diǎn)中增加是否存活的屬性。當(dāng)需要刪除敵機(jī)或子彈結(jié)點(diǎn)時，將屬性修改，放入死亡鏈表。當(dāng)需要創(chuàng)建新的敵機(jī)或子彈時，先檢查死亡鏈表中有無節(jié)點(diǎn)，若有，修改屬性插入存活鏈表，反之才會申請內(nèi)存空間，重新創(chuàng)建相應(yīng)結(jié)點(diǎn)；這樣，將死亡的結(jié)點(diǎn)重新利用，大大節(jié)省了游戲在創(chuàng)建、清除方面的開銷。

3 棧和隊(duì)列

棧和隊(duì)列都是操作受限的、特殊的線性表。棧只能在棧頂插入和刪除元素，特點(diǎn)是后進(jìn)先出（LIFO）；隊(duì)列只能在隊(duì)尾插入元素，在隊(duì)頭刪除元素，其特點(diǎn)是先進(jìn)先出（FIFO）。因此，棧和隊(duì)列非常適合用來解決遞歸、排隊(duì)類的問題。

遞歸設(shè)計(jì)在游戲開發(fā)中應(yīng)用很普遍，例如迷宮類游戲、漢諾塔游戲、棋類游戲等。而為了提高效率，減少遞歸函數(shù)的多次調(diào)用，游戲程序中通常利用對棧的操作來代替直接的遞歸函數(shù)設(shè)計(jì)。很多情況下棧和隊(duì)列要結(jié)合使用。

以迷宮類游戲?yàn)槔ǔＧ闆r下用回溯法（試探法）求解。這種方法將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前的候選解不可能是解的時候，就放棄它而選擇下一個候選解。如果當(dāng)前候選解不能滿足求解的要求，則擴(kuò)大候選解的規(guī)模繼續(xù)求解；直到最終成功求解。在回溯法中，放棄當(dāng)前候選解，尋找下一個候選解的過程叫做回溯。擴(kuò)大候選解的規(guī)模并繼續(xù)試探的過程叫做向前試探。用回溯法求解問題時常常使用遞歸方法進(jìn)行試探、回溯，實(shí)際應(yīng)用中使用棧的相應(yīng)操作來完成。例如，在迷宮中某一個特定位置向前試探時，就是將所有可能的下一個位置壓棧；之后依次出棧，對其進(jìn)行檢驗(yàn)；如果是墻壁，不可能是迷宮出口，那么放棄當(dāng)前位置，繼續(xù)出棧檢驗(yàn)；如果當(dāng)前位置是通道但不是出口，那么就將當(dāng)前位置的所有可能的下一個位置入棧；如此循環(huán)，直到棧空或找到迷宮出口。最終的結(jié)果只有兩種：找到迷宮出口；棧空—迷宮沒有出口。

4 樹

樹是一對多的數(shù)據(jù)結(jié)構(gòu)。非空樹只有一個根節(jié)點(diǎn)，而樹中的任意節(jié)點(diǎn)都可以有多個孩子結(jié)點(diǎn)。也就是說，樹中的任意節(jié)點(diǎn)，只可能有一個前驅(qū)，但可能有多個后繼。樹的存儲一般采用鏈?zhǔn)浇Y(jié)構(gòu)，父節(jié)點(diǎn)總是有多個指向子節(jié)點(diǎn)的指針，而子節(jié)點(diǎn)最多有一個指向父節(jié)點(diǎn)的指針。

由于樹結(jié)構(gòu)的特點(diǎn)，它非常適合解決游戲中的分支選擇判斷類問題，例如競猜類游戲。典型的實(shí)現(xiàn)是，用一個二叉樹來保存競猜的數(shù)據(jù)，葉子結(jié)點(diǎn)是競猜結(jié)果，其他節(jié)點(diǎn)都是競猜條件。在游戲過程中，如果當(dāng)前條件滿足，就繼續(xù)沿當(dāng)前結(jié)點(diǎn)的左子樹繼續(xù)競猜；否則沿右子樹繼續(xù)競猜。

除此之外，在一些擁有眾多游戲?qū)ο蟮膱鼍爸?，常使用四叉樹來進(jìn)行管理。例如，在一個游戲場景中有1000個隨機(jī)運(yùn)動的小球，程序需要在游戲的每一幀檢測它們的碰撞信息，之后進(jìn)行下一步處理，如下圖所示。

5 結(jié)束語

數(shù)據(jù)結(jié)構(gòu)在游戲軟件開發(fā)中的應(yīng)用非常廣泛，遠(yuǎn)遠(yuǎn)超過本文所論述的內(nèi)容。好的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，能將游戲軟件中復(fù)雜的功能更簡單更高效地解決，為游戲的核心邏輯、游戲玩法、游戲規(guī)則等提供了很重要的輔助設(shè)計(jì)作用。希望本文淺顯的分析能帶給讀者一些思考，更多地將數(shù)據(jù)結(jié)構(gòu)運(yùn)用到游戲軟件開發(fā)中去。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2011.

[2] [美]拉莫斯. Windows游戲編程大師技巧[M].北京：人民郵電出版社，2011.

[3] 秦海玉.Windows游戲程序設(shè)計(jì)基礎(chǔ)[M].北京：電子工業(yè)出版社，2011.

[4] 王佳婧，馮長寶，孫沫麗.淺談數(shù)據(jù)結(jié)構(gòu)在網(wǎng)絡(luò)游戲程序開發(fā)中的應(yīng)用[J].消費(fèi)電子，2013（6）.

[5] 葛亞平，李春生，王巧玲.數(shù)據(jù)結(jié)構(gòu)在游戲中的應(yīng)用[J].今日科苑，2007（8）.