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

【關鍵詞】數(shù)據(jù)結構；數(shù)據(jù)處理；動作響應；規(guī)則實現(xiàn)

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

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

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

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

二、玩家動作響應

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

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

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

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

因為算法要基于特定的存儲結構，所以首先應解決存儲結構的問題。將連連看的界面頂點進行存儲，因為其具有頂點排列具有數(shù)據(jù)結構中二維矩陣的特點，將頂點采用二維矩陣方式的存儲，而不是采用圖的結構存儲。界面中頂點包括圖片頂點和非圖片頂點，對于非圖片頂點二維數(shù)組單元對應值為0；應為圖片的種類的是固定的，給每個種類賦值，值均大于1，每個圖片頂點的二維數(shù)組單元對應的值為其種類的值。由此可以看到，二維矩陣存儲各個頂點信息后，找尋兩個相同圖片可消除的問題就，類似于小老鼠走迷宮的問題。將連連看的連線規(guī)則應用進小老鼠走迷宮的問題，假設選中兩張相同圖片對應的頂點分別是vij和vkl，在找路徑的同時要記錄已經有的折線數(shù)，一旦超出三條就結束查找。改進后算法如下：

將適當?shù)乃惴☉糜谶B連看的規(guī)則中，快速找到最短路徑，并在在隨時消除掉圖片后，更新最短路徑，且部分更新，提高程序的運行速度。由此可見，數(shù)據(jù)結構中的算法可以幫助在游戲實現(xiàn)其規(guī)則的同時降低程序復雜度，提高工作效率，加強了游戲的可玩性。但應用時數(shù)據(jù)結構的算法切忌照搬照抄，必須結合游戲的實際狀況進行選擇、改進，因為最終目的就是要提高游戲的工作效率。

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

參考文獻：

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結構[M].北京：清華大學出版社，1997.

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

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