關(guān)于數(shù)據(jù)結(jié)構(gòu)在游戲程序中的應(yīng)用探討

【摘 要】在軟件開發(fā)中數(shù)據(jù)結(jié)構(gòu)有著提高程序性能的作用，如果將它運(yùn)用于游戲開發(fā)，會(huì)使游戲的性能與運(yùn)行速度得到更大的提高，玩家會(huì)有更好的游戲體驗(yàn)，提高可玩性。本文對(duì)數(shù)據(jù)結(jié)構(gòu)在游戲程序中的應(yīng)用進(jìn)行了簡(jiǎn)單探討，希望給出數(shù)據(jù)結(jié)構(gòu)在網(wǎng)絡(luò)游戲開發(fā)中一種新思路。

【關(guān)鍵詞】數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)處理；動(dòng)作響應(yīng)；規(guī)則實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)現(xiàn)今被廣泛應(yīng)用于系統(tǒng)軟件和普通應(yīng)用軟件開發(fā)。例如計(jì)算機(jī)操作系統(tǒng)中，利用高效的檢索算法及索引技術(shù)，幫助計(jì)算機(jī)完成查找工作。數(shù)據(jù)結(jié)構(gòu)對(duì)于網(wǎng)絡(luò)游戲開發(fā)，其應(yīng)用似乎并不廣泛。數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)就在于提高程序的性能，如果數(shù)據(jù)結(jié)構(gòu)與網(wǎng)絡(luò)游戲很好的結(jié)合起來(lái)，可幫助提高游戲程序的運(yùn)行速度，增強(qiáng)可玩性。

一、數(shù)據(jù)處理

網(wǎng)絡(luò)游戲包括各種大量的數(shù)據(jù)，它們被存放服務(wù)器端的數(shù)據(jù)庫(kù)內(nèi)。當(dāng)某個(gè)玩家成功登錄后，該玩家就會(huì)從服務(wù)器的數(shù)據(jù)庫(kù)里獲得大量有關(guān)其自身的數(shù)據(jù)。玩家獲得的數(shù)據(jù)包括他選擇的角色、當(dāng)前玩到的級(jí)別、已經(jīng)得到的道具、已經(jīng)完成的任務(wù)及將要完成的任務(wù)等等。數(shù)據(jù)信息種類繁多，數(shù)量龐大。為了處理方便，客戶端程序首先應(yīng)該根據(jù)數(shù)據(jù)的種類選擇其合理的數(shù)據(jù)結(jié)構(gòu)進(jìn)行臨時(shí)存儲(chǔ)，便于后續(xù)的數(shù)據(jù)查詢、顯示及上傳。

以玩家道具為例，如果用線性表的結(jié)構(gòu)存儲(chǔ)，就要為每一種道具建立一個(gè)線性表結(jié)構(gòu)，會(huì)占用大量存儲(chǔ)空間，因此，此類數(shù)據(jù)存儲(chǔ)可以采用鏈?zhǔn)酱鎯?chǔ)方式解決。例如劍的種類包括單手劍、雙手劍、魔法劍及細(xì)劍等等，每種劍又會(huì)分為不懂級(jí)別。道具種類及道具之間可以采用樹形結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)，若將所有的劍均采用單鏈表存儲(chǔ)，單鏈表長(zhǎng)度過(guò)長(zhǎng)，關(guān)系混亂，不便于查找。因此在采用鏈?zhǔn)酱鎯?chǔ)同時(shí)，還應(yīng)采用樹形的邏輯結(jié)構(gòu)，因此存儲(chǔ)最終實(shí)現(xiàn)可采用樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的孩子兄弟表示法。樹的根結(jié)點(diǎn)為道具結(jié)點(diǎn)，此節(jié)點(diǎn)不包括任何數(shù)據(jù)，將已經(jīng)獲得的道具種類逐級(jí)分層，例如將劍、弓、魔法藥水等為同一界別；下一級(jí)別各個(gè)種類詳細(xì)劃分，例如劍的下一級(jí)別就包括單手劍、雙手劍、魔法劍及細(xì)劍等等；以此類推，最終的葉子結(jié)點(diǎn)就是某個(gè)具體道具。當(dāng)玩家的某個(gè)角色需要獲得自己的某種道具時(shí)，用遍歷算法，先找到種類，再沿著種類找到所有的道具。當(dāng)添加新道具時(shí)，首先判斷道具是否已經(jīng)在道具樹中，如果已經(jīng)在，那么就在樹中該道具的數(shù)量加上新獲得的數(shù)量；否則，應(yīng)該判斷新道具的種類是否已經(jīng)在樹中，如果在樹中，則將道具放置所屬種類的結(jié)點(diǎn)下面，如果此道具的種類未在樹中存在，則應(yīng)在道具樹的種類層中加入新的種類，在把新道具放到此種類下面，同時(shí)更新服務(wù)器上數(shù)據(jù)庫(kù)的道具信息，保持信息同步。通過(guò)這樣的樹結(jié)構(gòu)，避免了每次玩家的角色瀏覽道具時(shí)都要訪問(wèn)數(shù)據(jù)庫(kù)中數(shù)據(jù)，節(jié)省了時(shí)間，更便于對(duì)道具進(jìn)行分類管理，查找道具的速度也更快。

二、玩家動(dòng)作響應(yīng)

玩家通過(guò)輸入設(shè)備控制角色動(dòng)作，經(jīng)常同時(shí)控制運(yùn)動(dòng)動(dòng)作和攻擊動(dòng)作。玩家同時(shí)輸入多個(gè)動(dòng)作的速度極快，需要系統(tǒng)快速響應(yīng)。無(wú)論何種動(dòng)作，眾所周知都動(dòng)作都是由線程來(lái)控制，多個(gè)動(dòng)作同時(shí)提交等于向系統(tǒng)提交了多個(gè)線程。玩家希望多個(gè)動(dòng)作能夠同時(shí)運(yùn)行，但對(duì)于系統(tǒng)而言，線程不能同時(shí)運(yùn)行。因?yàn)橄到y(tǒng)響應(yīng)每個(gè)線程的時(shí)間比較短，給玩家的感覺(jué)是同時(shí)響應(yīng)的，實(shí)際上采用的是并發(fā)的方式。合理的安排線程運(yùn)行的順序，便于系統(tǒng)的調(diào)度，角色能夠快速展現(xiàn)玩家輸入的動(dòng)作。可以按照玩家輸入的動(dòng)作到達(dá)系統(tǒng)的時(shí)間為線程排序，用隊(duì)列存儲(chǔ)線程。先到達(dá)的排在隊(duì)頭，后到達(dá)排在隊(duì)尾。隊(duì)列的特征為先進(jìn)先出，因此，用此種結(jié)構(gòu)組織線程的時(shí)候，系統(tǒng)直接調(diào)出隊(duì)頭的線程進(jìn)行運(yùn)行，節(jié)省了查找的時(shí)間。

隨之而來(lái)的問(wèn)題就是采用何種隊(duì)列的存儲(chǔ)結(jié)構(gòu)？如果采用循環(huán)隊(duì)列的結(jié)構(gòu)，就需要預(yù)先知道大概需要的存儲(chǔ)區(qū)大小，但是玩家隨時(shí)都會(huì)輸入新的動(dòng)作，無(wú)法得知所需存儲(chǔ)區(qū)的大小，那么可以采用鏈隊(duì)列來(lái)存儲(chǔ)玩家的動(dòng)作線程更加適合。當(dāng)有新的動(dòng)作來(lái)時(shí)，可以將為其申請(qǐng)任意的空間存儲(chǔ)，只需把地址告知之前的隊(duì)尾，新的動(dòng)作就順利加入了隊(duì)列。

三、規(guī)則實(shí)現(xiàn)

不管是何種游戲，游戲規(guī)則是游戲設(shè)計(jì)的核心，游戲規(guī)則的好壞不但會(huì)影響到玩家對(duì)游戲的興趣程度，同樣會(huì)影響到游戲的運(yùn)行速度。制定了好的游戲規(guī)則后，如何實(shí)現(xiàn)就是難題，這就要求為其設(shè)計(jì)性能較好的算法。以連連看游戲?yàn)槔?，兩個(gè)同樣的圖像選擇后滿足三根以內(nèi)折線聯(lián)通就可以消掉。滿足條件的連線方式可能有多種，使用最短路徑連接消除會(huì)大大提高游戲運(yùn)行的速度，關(guān)鍵是如何找到最短路徑？

因?yàn)樗惴ㄒ谔囟ǖ拇鎯?chǔ)結(jié)構(gòu)，所以首先應(yīng)解決存儲(chǔ)結(jié)構(gòu)的問(wèn)題。將連連看的界面頂點(diǎn)進(jìn)行存儲(chǔ)，因?yàn)槠渚哂许旤c(diǎn)排列具有數(shù)據(jù)結(jié)構(gòu)中二維矩陣的特點(diǎn)，將頂點(diǎn)采用二維矩陣方式的存儲(chǔ)，而不是采用圖的結(jié)構(gòu)存儲(chǔ)。界面中頂點(diǎn)包括圖片頂點(diǎn)和非圖片頂點(diǎn)，對(duì)于非圖片頂點(diǎn)二維數(shù)組單元對(duì)應(yīng)值為0；應(yīng)為圖片的種類的是固定的，給每個(gè)種類賦值，值均大于1，每個(gè)圖片頂點(diǎn)的二維數(shù)組單元對(duì)應(yīng)的值為其種類的值。由此可以看到，二維矩陣存儲(chǔ)各個(gè)頂點(diǎn)信息后，找尋兩個(gè)相同圖片可消除的問(wèn)題就，類似于小老鼠走迷宮的問(wèn)題。將連連看的連線規(guī)則應(yīng)用進(jìn)小老鼠走迷宮的問(wèn)題，假設(shè)選中兩張相同圖片對(duì)應(yīng)的頂點(diǎn)分別是vij和vkl，在找路徑的同時(shí)要記錄已經(jīng)有的折線數(shù)，一旦超出三條就結(jié)束查找。改進(jìn)后算法如下：

將適當(dāng)?shù)乃惴☉?yīng)用于連連看的規(guī)則中，快速找到最短路徑，并在在隨時(shí)消除掉圖片后，更新最短路徑，且部分更新，提高程序的運(yùn)行速度。由此可見(jiàn)，數(shù)據(jù)結(jié)構(gòu)中的算法可以幫助在游戲?qū)崿F(xiàn)其規(guī)則的同時(shí)降低程序復(fù)雜度，提高工作效率，加強(qiáng)了游戲的可玩性。但應(yīng)用時(shí)數(shù)據(jù)結(jié)構(gòu)的算法切忌照搬照抄，必須結(jié)合游戲的實(shí)際狀況進(jìn)行選擇、改進(jìn)，因?yàn)樽罱K目的就是要提高游戲的工作效率。

經(jīng)過(guò)上述討論，可以發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)適合于網(wǎng)絡(luò)游戲程序開發(fā)的各個(gè)方面，使用時(shí)應(yīng)靈活多變。如果為了引入某種錯(cuò)誤的數(shù)據(jù)結(jié)構(gòu)，使得程序變得復(fù)雜，反而會(huì)影響游戲的速度，使得玩家對(duì)游戲喪失興趣。例如數(shù)據(jù)的處理應(yīng)先觀察各類數(shù)據(jù)的結(jié)構(gòu)特點(diǎn)及組織規(guī)律，采用合適的邏輯結(jié)構(gòu)以及便于操作的存儲(chǔ)結(jié)構(gòu)。

參考文獻(xiàn)：

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

[2]王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2011.

[3]韋斯（Weiss，M.A.）.數(shù)據(jù)結(jié)構(gòu)與算法分析[M].馮舜璽.北京：機(jī)械工業(yè)出版社，2009.