游戲開發案例在數據結構教學中的應用實踐

管士亮

文章編號：1672-5913(2009)06-0132-04

摘要：“數據結構”課程是計算機專業最重要的專業基礎課，游戲開發技術是計算機應用技術最前沿的分支之一，實現由基礎到前沿的跨越，是學生的希望所在，也是檢驗教學成功與否的重要指標。本文總結了游戲開發過程中的成功經驗，及時反饋并自覺落實到教學過程中，對教師和學生都是有益的嘗試。

關鍵詞：數據結構；游戲開發；跨越

中圖分類號：G642

文獻標識碼：B

從事“數據結構”教學的教師往往遇到的學生困惑是：數據結構有什么用？數據結構與計算機新技術的開發有什么關系？類似的問題一方面反映了學生對計算機新技術的渴望與困惑；另一方面也反映了“象牙塔”里的學校教育與技術開發市場之間的距離。

毋庸置疑的是，“數據結構”是計算機本科學生最重要的專業基礎課，在游戲編程中扮演著極其重要的角色，而游戲開發技術又是計算機應用技術最前沿的分支之一。本文試圖通過數據結構在游戲開發中的簡單應用來解答學生的困惑，以此拉近學校教育與市場開發之間的距離。本文涉及到數據結構中的鏈表、順序表、棧、隊列、二叉樹及圖的概念，在此不做過多描述，希望讀者閱讀本文前對數據結構有所了解，并且熟悉C/C++語言的各種功能和應用。

1順序表的應用

順序表是數據結構中最簡單、最常用的一種線性表，它的特點是，用一組地址連續的存儲單元依次存儲線性表的元素。磚塊地圖系統中使用的就是這種最簡單的數據結構。這里對磚塊地圖系統做如下規定：構建一個簡單的磚塊地圖系統，視角為俯視90度，并由許多個順序連接的圖塊拼成。

(1) 定義圖塊

struct Plot //定義圖塊結構

{

int Access; //記錄此圖塊是否可以通過

…… //中有每個圖塊的圖片指針 等記錄

};

Access為0時，表示此圖塊不可通過，為1表示能通過。

(2) 定義二維數組存放每個圖塊的值

定義的二維數組為：Plot Map[7][10]。通過循環將此地圖初始化，初始化程序和生成地圖如圖1所示。

for (i=0;i<=6;i++)

for (j=0;j<=9;j++)

scanf(“輸入第%行，第%列初始化值:%d ”&i,&j,&Map [i][j]);

從圖1看出，這個地圖用順序表表示非常直接。當控制人物在其中走動時，對人物將要走到的下一個圖塊進行判斷，看其是否能通過。比如，當人物要走到(2，5)這個圖塊時，用如下判定函數來判斷這個圖塊是否能通過：

x=3;y=5;

int Ispass(x,y)

{

return Map[x,y].Access; //返回圖塊是否 通過的值

}

以上只是簡單的地圖例子，使用順序表也可以表示更為復雜的磚塊地圖。目前流行的整幅地圖中也都要用到大量的順序表，只不過在整幅中進行分塊而已。

2鏈表應用

鏈表的主要優點就是可以方便地進行插入、刪除操作。在游戲開發中，鏈表主要應用在有大規模的刪除和添加操作上。在飛機游戲中，飛機的子彈是要頻繁地出現、消除的，個數也是隨機的。鏈表主要應用在發彈模塊上。在下面的源代碼中，我們就定義了坐標結構和子彈鏈表。

(1) 定義坐標結構

struct Cpiot //定義坐標結構

{

int x; //X軸坐標

int y; //Y軸坐標

};

(2) 定義子彈鏈表

struct Bullet //定義子彈鏈表

{

Cpiotbulletpos; //子彈的坐標

intbulletspd; // 子彈的速度

struct Bullet* next; //指向下 一個子彈

};

(3) 定義飛機類中的子彈

class Cmyplane

{

public:

void AddBullet(struct Bullet*);

//加入子彈的函數，每隔一定時間加彈

void RefreshBullet();

//刷新子彈

privated:

struct Bullet *St_MyBullet;

// 聲明飛機的子彈鏈表

};

在void AddBullet(struct Bullet*)中，只要將一個結點插入鏈表中，并且每隔一段時間加入，就會產生連續發彈的效果。

(4) 加彈函數的主要源代碼

void AddBullet(struct Bullet*)

{

struct Bullet *St_New,*St_Temp;

//定義臨時鏈表

St_New=_StrucHead; //鏈表頭(已初始化)

St_New->(Bullet St_MyBullet *)malloc (sizeof(St_MyBullet));

//分配內存

St_Temp= =_NewBullet; //臨時存值

St_New->next=St_Temp->next;

St_Temp->next=St_New;

}；

(5) 在函數Void RefreshBullet()中，只要將鏈表遍歷一次，就可以實現子彈的數據更新。主要的源代碼如下：

while(St_MyBullet->next!=NULL)

{ // 查找

St_MyBullet->bulletpos.x=bulletspd;

//更新子彈數據

………

St_MyBullet=St_MyBullet->next;

//查找運算

};

3棧和隊列的應用

棧和隊列是兩種特殊的線性結構，在游戲程序開發中，這兩種線性結構一般應用在腳本引擎、操作界面、數據判定中。下面通過一個簡單的腳本引擎函數來介紹棧的應用。隊列和棧的用法很相似，可依此類推，不再舉例。

設置腳本文件的時候，通常會規定一些基本語法，這就需要一個解讀語法的編譯程序。這里列出的是一個語法檢查函數，主要功能是檢查“()”是否配對。實現的基本思想是：規定在腳本語句中可以使用“()”嵌套，則左括號和右括號配對一定是先有左括號，后有右括號，并且在嵌套使用中，左括號允許單個或連續出現，并與將要出現的右括號配對銷解，左括號在等待右括號出現的過程中可以暫時保存起來。當右括號出現后，找不到左括號，則發生不配對現象。從程序實現角度講，左括號連續出現，則后出現的左括號應與最先到來的右括號配對銷解。這種左括號的保存和右括號配對銷解的過程和棧的“后進先出”原則是一致的。我們可以將讀到的左括號壓入設定的棧中，當讀到右括號時，就和棧中的左括號銷解，如果在棧頂彈不出左括號，則表示配對出錯，或者當括號串讀完，棧中仍有左括號存在，也表示配對出錯。大致設計思想如上所述，主要源代碼如下：

(1) struct //定義棧結構

{

int St_Data[100]; //數據段

int St_Top; //通常規定棧底 位置在向量低端

} SeqStack;

(2) int Check(SeqStack *stack)//語法檢查函數

{

char sz_ch;

int boolean; Push(stack,'# ');

// 壓棧，#為判斷數據

sz_ch=getchar(); //取值

boolean=1;

while(sz_ch!=' '&&boolean)

{

if(sz_ch= ='(')

Push(stack,ch);

if(sz_ch= =')')

if(gettop(stack)= ='#')

//讀棧頂

boolean=0;

else

Pop(stack); //出棧

sz_ch=getchar();

}

if(gettop(stack)!='#') boolean=0;

if(boolean) cout<<"right";

// 輸出判斷信息

else cout＜＜"error";

以上只介紹了腳本的讀取，在下面對圖的應用中，再對腳本結構進行深入的研究。總之，凡在游戲中出現先進后出(棧)、先進先出(隊列)的情況，就可以運用這兩種數據結構，例如《帝國時代》中地表中間的過渡帶。

4二叉樹的應用

樹的應用極其廣泛，二叉樹是樹中的一個重要類型。這里以二叉樹的“判定樹”為例講解二叉樹的應用，描述分類過程和處理判定優化等方面。

在游戲開發中，通常有很多分類判斷。比如：設主角的生命值v，假如在省略其他條件后，有這樣的條件判定：當怪物碰到主角后，怪物的反應遵循如下規則：

根據上述條件，可以用如下普通算法來判定怪物的反應：

if(V<100) state=嘲笑，單挑

elseif(V<200)state=單 挑

elseif(V<300) state=嗜血魔法

elseif(V<500) state=呼喚同伴

elsestate=逃跑

上面的算法適用于大多數情況，但時間性能不高，時間復雜度相對較高。我們可以通過判定樹來提高其時間性能。首先分析主角生命值的通常特點，即預測出每種條件占總條件的百分比，將這些比值作為權值來構造最優二叉樹(哈夫曼樹)，作為判定樹來設定算法。假設這些百分比為：

構造的哈夫曼樹如圖2所示。

對應算法如下：

if(V>=200)&&(V<300) state=嗜血魔法

elseif(V>=300)&&(d<500) state=呼喚同伴

else if(V>=100)&&(V<200) state=單挑

else if(V<100) state =嘲笑，單挑

else state =逃跑

通過計算，兩種算法的效率比例大約是2:3，很明顯，改進的算法在時間性能上提高了不少。一般，在即時戰略游戲中，對此類判定算法會有較高的時間性能要求，可以通過二叉樹對此進行更深入的研究。

5圖的應用

在游戲中，大多數應用圖的地方是路徑搜索，即A*算法。在此以圖的另一種應用為例：在情節腳本中，描述各個情節之間的關系。在游戲中，可能包含很多分支情節，在這些分支情節之間會存在一定的先決條件約束，即有些分支情節必須在其他分支情節完成后方可開始發展，而有些分支情節沒有這樣的約束。通過以上分析，可以用有向圖中的AOV網(Activity On Vertex Network)來描述這些分支情節之間的先后關系。假設有如下的情節：

注意：在AOV網中，不應該出現有向環路，否則，頂點的先后關系就會進入死循環。即情節將不能正確發展，可以采取拓撲排序來檢測圖中是否存在環路。以上情節用圖的形式表現如圖2所示(此圖為有向圖，先后關系顯示在上面的表格中)：

用鄰接矩陣表示此有向圖，代碼片斷如下：

struct Mgraph

{

int Vexs[MaxVex]; //頂點信息

int Arcs[MaxLen][MaxLen]; // 鄰接矩陣

……

};

頂點信息存儲在情節文件中，將給出的情節表示成鄰接矩陣：

0 1 0 0 0

0 0 1 1 0

0 0 0 0 1

0 0 0 0 1

0 0 0 0 0

在此規定，各個情節之間有先后關系，但沒有被玩家發展的，用“1”表示；如果情節被發展，就用“2”表示。比如，當已經發展了遭遇強盜的情節，那么，C1與C2頂點之間的關系就可以用“2”表示，注意，這并不表示C2已經被發展，只是表示C2可以被發展了。

請看下面的代碼：

class CRelation

{

public:

CRelation(char *filename);

//構造函數，將情節信息文件讀入到緩存中

void SetRelation(int ActionRelation);

// 設定此情節已經發展

BOOL SearchRelation(int ActionRelation); // 尋找此情節是否已發展

BOOL SaveBuf(char *filename);

//保存緩存到文件中

……

privated:

char* buf; // 鄰接矩陣的內存緩沖

……

};

在這里，我們將表示情節先后關系的鄰接矩陣放到緩沖內，通過接口函數修改情節關系，在BOOL SearchRelation (int ActionRelation)函數中，我們可以利用廣度優先搜索方法來實現搜索。

我們也可以用鄰接鏈表來表示這個圖，但用鏈表表示會占用更多的內存。鄰接鏈表主要的優點是表示動態的圖，在這里并不適合。

參考文獻：

[1] 錢能. C++程序設計教程[M]. 北京:清華大學出版社.

[2] 嚴蔚敏. 數據結構[M]. 北京:清華大學出版社.

[3] 張福炎. 程序員高級程序員程序設計[M]. 北京:清華大學出版社.